二叉搜索树在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