二叉搜索樹在C＃實現

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

    } 
} 

這是implementation.The代碼的代碼工作正常，但如果在displayTree功能，我用

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

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

} 

更換一個無限循環引起的。我不明白是什麼導致了這一點。我還想知道是否有更好的方式在C＃中實現BST。

Answer 1

我不知道爲什麼你需要這個循環，但回答你的問題：

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

此代碼檢查是否temp不null，但它永遠不會變成零，導致內循環您行動只有在溫度的葉子上。這就是爲什麼你有一個infinit循環。

Answer 2

你並不需要一個while循環也不是temp變量，讓遞歸爲你做的工作：

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

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

Answer 3

溫度在開始時設置爲root，並且它的價值不會改變

後

怎麼樣重寫你的功能

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

Answer 4

試試這個

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

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

     } 
    } 

Answer 5

我只是在想，你也可以使用遞歸的add函數。它可能看起來像這樣

 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

請參閱https://msdn.microsoft.com/en-us/library/ms379572%28v=vs.80%29.aspx。 請參閱「遍歷BST的節點」一節中的示例代碼

另外...不要忘記查看SortedDictionary等。他們可能有BST，您需要準備好去！ https://msdn.microsoft.com/en-us/library/f7fta44c.aspx