Самый низкий общий предк в двоичном дереве, прочитайте ввод и алгоритм

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

мой класс Node:

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!"); 
       } 
      } 
     } 
    } 
} 

Создание класса Node:

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

"Спасибо!"