二叉樹中的最低公共祖先，閱讀輸入和算法

Question

我是受訓者，並有一個問題，我無法單獨解決這個問題。所以請幫助我。我發現很多主題，但我找不到解決方案。 我剛開始學習C＃，我不知道如何做到這一點。我知道這是一項簡單的工作，但我真的需要理解並解決它。我嘗試做一些事情，但它只是一些代碼。我用一些值做了我的二叉樹，有一個節點類和打印方法。
請告訴我如何編寫一個可以從控制檯讀取樹的代碼，因爲我不想要任何hardcorde。然後如何找到一個最低的共同祖先 - 我看到了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; 
     } 
    } 

拜託，我真的需要每一個連接這樣理解如果你能爲我解釋並提供幫助，請給我。

Answer 1

所以這裏是我的二進制樹代碼。

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; 
     }   
    } 

「謝謝你！」