Binary Search Tree trong C# Thực hiện

Question

class Node 
{ 
    public int data; 
    public Node left, right; 

    public Node(int data) 
    { 
     this.data = data; 
     left = null; 
     right = null; 

    } 
} 

class BinaryTreeImp 
{ 
    Node root; 
    static int count = 0; 

    public BinaryTreeImp() 
    { 
     root = null; 

    } 
    public Node addNode(int data) 
    { 
     Node newNode = new Node(data); 

     if (root == null) 
     { 
      root = newNode; 

     } 
     count++; 
     return newNode; 


    } 

    public void insertNode(Node root,Node newNode) 
    { 
     Node temp; 
     temp = root; 

     if (newNode.data < temp.data) 
      { 
       if (temp.left == null) 
       { 
        temp.left = newNode; 

       } 

       else 
       { 
        temp = temp.left; 
        insertNode(temp,newNode); 

       } 
      } 
      else if (newNode.data > temp.data) 
      { 
       if (temp.right == null) 
       { 
        temp.right = newNode; 

       } 

       else 
       { 
        temp = temp.right; 
        insertNode(temp,newNode); 
       } 
      } 
     } 


    public void displayTree(Node root) 
    { 
     Node temp; 
     temp = root; 

     if (temp == null) 
      return; 
      displayTree(temp.left); 
      System.Console.Write(temp.data + " "); 
      displayTree(temp.right); 


    } 

    static void Main(string[] args) 
    { 
     BinaryTreeImp btObj = new BinaryTreeImp(); 
     Node iniRoot= btObj.addNode(5); 


     btObj.insertNode(btObj.root,iniRoot); 
     btObj.insertNode(btObj.root,btObj.addNode(6)); 
     btObj.insertNode(btObj.root,btObj.addNode(10)); 
     btObj.insertNode(btObj.root,btObj.addNode(2)); 
     btObj.insertNode(btObj.root,btObj.addNode(3)); 
     btObj.displayTree(btObj.root); 

     System.Console.WriteLine("The sum of nodes are " + count); 
     Console.ReadLine(); 

    } 
} 

Đây là mã cho mã implementation.The hoạt động tốt nhưng nếu trong hàm displayTree, tôi thay thế nó với

public void displayTree(Node root) 
{ 
    Node temp; 
    temp = root; 

    while(temp!=null) 
    { 
     displayTree(temp.left); 
     System.Console.Write(temp.data + " "); 
     displayTree(temp.right); 
    } 

} 

một vòng lặp vô hạn là do. Tôi không hiểu những gì đang gây ra điều này. Ngoài ra tôi muốn biết nếu có một cách tốt hơn để thực hiện một BST trong C#.

Answer 1

Tôi không chắc chắn lý do tại sao bạn cần vòng lặp này, nhưng việc trả lời câu hỏi của bạn:

while(temp!=null) 
{ 
    displayTree(temp.left); 
    System.Console.Write(temp.data + " "); 
    displayTree(temp.right); 
} 

mã này kiểm tra nếu temp không phải là null, nhưng nó sẽ không bao giờ trở thành vô giá trị, gây bên vòng lặp bạn hành động chỉ trên các lá của nhiệt độ. Đó là lý do tại sao bạn có một vòng lặp vô hạn.

Answer 2

Bạn không cần một vòng lặp while cũng không một biến temp, chúng ta hãy đệ quy làm việc cho bạn:

public void displayTree(Node root) 
{ 
    if(root == null) return; 

    displayTree(root.left); 
    System.Console.Write(root.data + " "); 
    displayTree(root.right); 
} 

Answer 3

tạm thời được thiết lập để rễ ngay từ đầu, và sau đó giá trị của nó không bao giờ thay đổi

gì về viết lại chức năng của bạn như

public void displayTree(Node root) 
{ 
    if (root == null) 
     return; 
    displayTree(root.left); 
    Console.Write(...); 
    displayTree(root.right); 
} 

Answer 4

thử này

 public void displayTree(Node root) 
    { 
     Node temp; 
     temp = root; 

     if (temp != null) 
     { 
      displayTree(temp.left); 
      Console.WriteLine(temp.data + " "); 
      displayTree(temp.right); 

     } 
    } 

Answer 5

Tôi chỉ nghĩ rằng bạn cũng có thể sử dụng đệ quy cho hàm cộng. Nó có thể trông giống như thế này

 private void Add(BinaryTree node, ref BinaryTree rootNode) 
    { 
     if (rootNode == null) 
     { 
      rootNode = node; 
     } 
     if (node.value > rootNode.value) 
     { 
      Add(node, ref rootNode.right); 
     } 
     if (node.value < rootNode.value) 
     { 

     Add(node, ref rootNode.left); 
     } 
    } 

Answer 6

Xem https://msdn.microsoft.com/en-us/library/ms379572%28v=vs.80%29.aspx. Xem mã ví dụ trong phần "Traversing the Nodes of a BST"

Ngoài ra ... đừng quên xem SortedDictionary, v.v. Họ có thể có BST mà bạn cần tất cả đã sẵn sàng! https://msdn.microsoft.com/en-us/library/f7fta44c.aspx