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

    }
}

这是实现的代码。代码工作正常，但如果在 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。

4

7 回答 7

5

我不确定你为什么需要这个循环，但回答你的问题：

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

此代码检查 if tempis not null，但它永远不会变为 null，因为在循环内您只对 temp 的叶子起作用。这就是为什么你有一个无限循环。

于 2012-04-28T18:53:01.620 回答
5

您不需要 while 循环或temp变量，让递归为您完成工作：

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

    displayTree(root.left);
    System.Console.Write(root.data + " ");
    displayTree(root.right);
}
于 2012-04-28T18:56:33.197 回答
0

temp 在开始时设置为 root，之后它的值永远不会改变

将您的功能重写为怎么样

public void displayTree(Node root)
{
     if (root == null)
       return;
     displayTree(root.left);
     Console.Write(...);
     displayTree(root.right);
}
于 2012-04-28T18:58:30.043 回答
0

试试这个

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

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

        }
    }
于 2013-06-04T12:54:23.417 回答
0

我只是在想你也可以对 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);
        }  
    }
于 2014-10-24T12:37:28.837 回答
0

请参阅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

于 2015-07-06T19:23:17.280 回答
0

完整的二叉搜索树...用代码检查树是否平衡

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace BinarySearchTree
{

    public class Node
    {
        public Node(int iData)
        {
            data = iData;
            leftNode = null;
            rightNode= null;
        }
        public int data{get; set;}
        public Node leftNode{get; set;}
        public Node rightNode{get; set;}
    };
    public class Program
    {
        public static Node root = null;
        public static void Main(string[] args)
        {
            //Your code goes here
            Console.WriteLine("Hello, world!");
            root = new Node(20);
            InsertNode(root, new Node(10));
            InsertNode(root, new Node(15));
            InsertNode(root, new Node(13));
            InsertNode(root, new Node(11));
            InsertNode(root, new Node(12));
            InsertNode(root, new Node(25));
            InsertNode(root, new Node(22));
            InsertNode(root, new Node(23));
            InsertNode(root, new Node(27));
            InsertNode(root, new Node(26));


           if(CheckIfTreeIsBalanced(root))
           {
                Console.WriteLine("Tree is Balanced!");
           }
           else
           {
               Console.WriteLine("Tree is Not Balanced!");
           }
            PrintTree(root);
        }


        public static void PrintTree(Node root)
        {
           if(root == null) return;        
           Node temp = root;

           PrintTree(temp.leftNode);
           System.Console.Write(temp.data + " "); 
           PrintTree(temp.rightNode);

        }

        public static bool CheckIfTreeIsBalanced(Node root)
        {
            if(root != null)
            {
                if(root.leftNode != null && root.rightNode!= null)
                {
                    if(root.leftNode.data < root.data && root.rightNode.data > root.data)
                    {
                        return CheckIfTreeIsBalanced(root.leftNode)&&CheckIfTreeIsBalanced(root.rightNode);
                    }
                    else
                    {
                        return false;
                    }
                } 
                else if(root.leftNode != null)
                {
                    if(root.leftNode.data < root.data)
                    {
                        return CheckIfTreeIsBalanced(root.leftNode);
                    }
                    else
                    {
                        return false;
                    }
                }
                else if(root.rightNode != null)
                {
                    if(root.rightNode.data > root.data)
                    {
                        return CheckIfTreeIsBalanced(root.rightNode);
                    }
                    else
                    {
                        return false;
                    }
                }
            }
             return true;
        }

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

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

                }

                else
                {
                    temp = temp.leftNode;
                    InsertNode(temp,newNode);

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

                }

                else 
                {
                    temp = temp.rightNode;
                    InsertNode(temp,newNode);
                }
            }
        }

    }
}

输出 ：

Hello, world!
Tree is Balanced!
10 11 12 13 15 20 22 23 25 26 27
于 2018-08-23T13:11:08.020 回答