我是实习生,有一个问题,我无法独自解决这个问题。所以请帮助我。我找到了很多主题,但我找不到解决方案。我刚开始学习 C#,但我不知道该怎么做。我知道这是一项简单的工作,但实际上我需要理解和解决它。我尝试做一些事情,但它只是一些代码。我用一些值做了我的二叉树,有一个节点类和打印方法。
请告诉我如何编写可以从控制台读取树的代码,因为我不想有任何硬密码。然后如何找到一个最低的共同祖先 - 我看到了 BFS 和 DFS 算法,所以也许我可以找到一些东西,但我不确定。
我已经读了很多关于这个的东西,但我无法解释很多事情。她这是我的代码:
class Program
{
static void Main(string[] args)
{
var binatyTree = new BinaryTree<int>(1,
new BinaryTree<int>(2,
new BinaryTree<int>(4),
new BinaryTree<int>(5)),
new BinaryTree<int>(3,
new BinaryTree<int>(6,
new BinaryTree<int>(9),
new BinaryTree<int>(10)),
new BinaryTree<int>(7))
);
Console.WriteLine("Binary Tree:");
binatyTree.Print();
}
}
我的二叉树和打印方法:
public class BinaryTree<T>
{
public T Value { get; set; }
public BinaryTree<T> LeftChildren { get; set; }
public BinaryTree<T> RightChildren { get; set; }
public BinaryTree(T value, BinaryTree<T> leftChildren = null, BinaryTree<T> rightChildren = null)
{
this.Value = value;
this.LeftChildren = leftChildren;
this.RightChildren = rightChildren;
}
public void Print (int indent = 0)
{
Console.Write(new string (' ', 2*indent));
Console.WriteLine(this.Value);
if (this.LeftChildren != null)
{
this.LeftChildren.Print(indent + 1);
}
if (this.RightChildren != null)
{
this.RightChildren.Print(indent + 1);
}
}
我的类节点:
class Node
{
private int data;
private Node left;
private Node right;
public Node(int data = 0)
{
this.data = 0;
left = null;
right = null;
}
}
所以请我真的需要了解每一个连接,所以如果你能为我解释和帮助,请。
这是我的二叉树代码。
using System;
namespace MyBinaryTree
{
// Creates a binary tree
// Finds the lowest common ancestor in a binary tree
class МainSolution
{
static void Main(string[] args)
{
// Initialises binary tree view
var btView = new ViewBinaryTree();
btView.BinaryTreeView();
// Initialises new binary tree
BinarySearchTree tree = new BinarySearchTree();
// Reads the desired number of nodes
Console.Write("Enter how many nodes you want: ");
int number = int.Parse(Console.ReadLine());
Console.WriteLine();
// Reads the nodes' values
for (int i = 1; i <= number; i++)
{
Console.Write($"Enter name of {i} node: ");
string nodeName = Console.ReadLine().ToUpper();
tree.Insert(nodeName);
}
// Lowest common ancestor - reads the two required values
// Checks the values
// Prints the lowest common ancestor
bool isValid = true;
while (isValid)
{
Console.WriteLine();
Console.Write("Please enter the first node value: ");
string nameOne = Console.ReadLine().ToUpper();
Console.Write("Please enter the second node value: ");
string nameTwo = Console.ReadLine().ToUpper();
if (tree.Find(nameOne) == true && tree.Find(nameTwo) == true)
{
Console.WriteLine();
var result = tree.SearchLCA(tree.root, nameOne, nameTwo);
Console.WriteLine($"Lowest common ancestor: {result} ");
Console.WriteLine();
isValid = false;
}
else
{
Console.WriteLine();
Console.WriteLine("Please enter a valid name!");
}
}
}
}
}
创建类节点:
// Creates the node structure
class Node
{
public string Data { get; set; }
public Node RightChild { get; set; }
public Node LeftChild { get; set; }
public Node(string data, Node left = null, Node right = null)
{
this.Data = data;
this.LeftChild = left;
this.RightChild = right;
}
}
这是我的逻辑
// Creates a binary tree.
class BinarySearchTree
{
public Node root; // Creates a root node.
public BinarySearchTree()
{
this.root = null;
}
// Adds a node in the binary tree.
public void Insert(string inputValue)
{
Node newNode = new Node(inputValue); // Creates a new node.
if (root == null) // If the tree is empty, inserts the new node as root
{
root = newNode;
return;
}
//Determins where to place the new node in the binary tree.
Node current = root;
Node parent = null;
while (true)
{
parent = current;
if (inputValue.CompareTo(current.Data) < 0)
{
current = current.LeftChild;
if (current == null)
{
parent.LeftChild = newNode;
return;
}
}
else
{
current = current.RightChild;
if (current == null)
{
parent.RightChild = newNode;
return;
}
}
}
}
// Checks if the node exists in the binary tree
public bool Find(string inputValue)
{
Node current = root;
while (current != null)
{
if (current.Data.Equals(inputValue))
{
return true;
}
else if (current.Data.CompareTo(inputValue) > 0)
{
current = current.LeftChild;
}
else
{
current = current.RightChild;
}
}
return false;
}
// Creates a method to find the lowest common ancestor(LCA).
public object SearchLCA(Node searchTree, string compareValue1, string compareValue2)
{
if (searchTree == null)
{
return null;
}
if (searchTree.Data.CompareTo(compareValue1) > 0 && searchTree.Data.CompareTo(compareValue2) > 0)
{
return SearchLCA(searchTree.LeftChild, compareValue1, compareValue2);
}
if (searchTree.Data.CompareTo(compareValue1) < 0 && searchTree.Data.CompareTo(compareValue2) < 0)
{
return SearchLCA(searchTree.RightChild, compareValue1, compareValue2);
}
return searchTree.Data;
}
}
"谢谢!">