C# 如何创建一个二叉树

How to create a binary tree

提问by Tom

I did'nt mean binary search tree.

我不是说二叉搜索树。

for example, if I insert values 1,2,3,4,5 in to a binary search tree the inorder traversal will give 1,2,3,4,5 as output.

例如，如果我将值 1,2,3,4,5 插入到二叉搜索树中，中序遍历将给出 1,2,3,4,5 作为输出。

but if I insert the same values in to a binary tree, the inorder traversal should give 4,2,5,1,3 as output.

但是如果我将相同的值插入到二叉树中，中序遍历应该给出 4,2,5,1,3 作为输出。

Binary tree can be created using dynamic arrays in which for each element in index n, 2n+1 and 2n+2 represents its left and right childs respectively.

可以使用动态数组创建二叉树，其中对于索引 n、2n+1 和 2n+2 中的每个元素分别表示其左孩子和右孩子。

so representation and level order traversal is very easy here.

所以在这里表示和级别顺序遍历非常容易。

but I think, in-order,post-order,pre-order is difficult.

但我认为，在订单，后订单，预购很难。

my question is how can we create a binary tree like a binary search tree. ie. have a tree class which contains data, left and right pointers instead of arrays. so that we can recursively do traversal.

我的问题是我们如何创建像二叉搜索树这样的二叉树。IE。有一个包含数据、左右指针而不是数组的树类。这样我们就可以递归地进行遍历。

回答by unwind

The tree class declaration part is, certainly, not the difficulty here. You basically stated exactly how to declare it, in the question:

树类声明部分当然不是这里的难点。您在问题中基本上准确地说明了如何声明它：

class BinaryTree
{
private:
    int data;
    BinaryTree *left, *right;
};

This supports various forms of traversal, like so:

这支持各种形式的遍历，如下所示：

void Inorder(const BinaryTree *root)
{
  if(root == 0)
    return;
  Inorder(root->left);
  printf("now at %d\n", root->data);
  Inorder(root->right);
}

You should be able to deduce pre- and post-order traversals from that. In a real implementation, the tree would probably be templated to store random data, the traversal routines would be more general (with a user-data input, or perhaps user-supplied per-node callback, or whatever), of course.

您应该能够从中推断出前序和后序遍历。在实际实现中，树可能会被模板化以存储随机数据，当然，遍历例程会更通用（使用用户数据输入，或者用户提供的每个节点回调，或其他）。

回答by Tom

Since I have not received any answers to the question which I asked, I will post my own implementaion of the binary tree using arrays. now I know that array implementaion is easier than i thought ,but still i dont know how to implement the same using linked lists.

由于我没有收到我提出的问题的任何答案，我将使用数组发布我自己的二叉树实现。现在我知道数组实现比我想象的要容易，但我仍然不知道如何使用链表实现相同的。

the code is in c#

代码在 c# 中

  class BinaryTree
    {
        private static int MAX_ELEM = 100;      //initial size of the array
        int lastElementIndex;
        int?[] dataArray;

        public BinaryTree()
        {
            dataArray = new int?[MAX_ELEM];
            lastElementIndex = -1;
        }

        //function to insert data in to the tree
        //insert as a complete binary tree
        public void insertData(int data)
        {
            int?[] temp;
            if (lastElementIndex + 1 < MAX_ELEM)
            {
                dataArray[++lastElementIndex] = data;
            }
            else
            {  //double the size of the array on reaching the limit
                temp = new int?[MAX_ELEM * 2];
                for (int i = 0; i < MAX_ELEM; i++)
                {
                    temp[i] = dataArray[i];
                }
                MAX_ELEM *= 2;
                dataArray = temp;
                dataArray[++lastElementIndex] = data;
            }
        }

        //internal function used to get the left child of an element in the array
        int getLeftChild(int index) {
            if(lastElementIndex >= (2*index+1))
                return (2*index + 1);
            return -1;
        }

        //internal function used to get the right child of an element in the array
        int getRightChild(int index) {
            if(lastElementIndex >= (2*index+2))
                return (2*index + 2);
            return -1;
        }
        //function to check if the tree is empty
        public bool isTreeEmpty() {
            if (lastElementIndex == -1)
                return true;
            return false;
        }

        //recursive function for inorder traversal
        public void traverseInOrder(int index) {
            if (index == -1)
                return;
            traverseInOrder(getLeftChild(index));
            Console.Write("{0} ", dataArray[index]);
            traverseInOrder(getRightChild(index));
        }

        //recursive function for preorder traversal
        public void traversePreOrder(int index) {
            if (index == -1)
                return;
            Console.Write("{0} ", dataArray[index]);
            traversePreOrder(getLeftChild(index));
            traversePreOrder(getRightChild(index));
        }

        //recursive function for postorder traversal
        public void traversePostOrder(int index) {
            if (index == -1)
                return;
            traversePostOrder(getLeftChild(index));
            traversePostOrder(getRightChild(index));
            Console.Write("{0} ", dataArray[index]);
        }

        //function to traverse the tree in level order
        public void traverseLevelOrder()
        {
            Console.WriteLine("\nPrinting Elements Of The Tree In Ascending Level Order\n");
            if (lastElementIndex == -1)
            {
                Console.WriteLine("Empty Tree!...press any key to return");
                Console.ReadKey();
                return;
            }
            for (int i = 0; i <= lastElementIndex; i++)
            {
                Console.Write("{0} ", dataArray[i]);
            }
            Console.WriteLine("\n");
        }


    }

回答by Patrick McDonald

If I understand you correctly, you want to create a binary tree from an array

如果我理解正确，您想从数组创建二叉树

int[] values = new int[] {1, 2, 3, 4, 5};
BinaryTree tree = new BinaryTree(values);

this should prepopulate the binary tree with the values 1 - 5 as follows:

这应该使用值 1 - 5 预填充二叉树，如下所示：

    1
   / \
  2   3
 / \
4   5

this can be done using the following class:

这可以使用以下类来完成：

class BinaryTree
{
    int value;
    BinaryTree left;
    BinaryTree right;

    public BinaryTree(int[] values) : this(values, 0) {}

    BinaryTree(int[] values, int index)
    {
        Load(this, values, index);
    }

    void Load(BinaryTree tree, int[] values, int index)
    {
        this.value = values[index];
        if (index * 2 + 1 < values.Length)
        {
            this.left = new BinaryTree(values, index * 2 + 1);
        }
        if (index * 2 + 2 < values.Length)
        {
            this.right = new BinaryTree(values, index * 2 + 2);
        }
    }
}

回答by Paul Suart

If you're after source for a comprehensive BinaryTree implementation you can learn from have a look at The C5 Generic Collection Library.

如果您正在寻找全面的 BinaryTree 实现的源代码，您可以从查看C5 通用集合库中学习。

回答by user1997925

  class BstNode
    {
        public int data;
        public BstNode(int data)
        {
            this.data = data;
        }
        public BstNode left;
        public BstNode right;
    }
    class Program
    {
        public static BstNode Insert(BstNode root, int data)
        {
            if (root == null) root = new BstNode(data);
            else if (data <= root.data) root.left = Insert(root.left, data);
            else if (data > root.data) root.right = Insert(root.right, data);

            return root;
        }

public static void Main(string[] args)
        {
            // create/insert into BST
            BstNode Root = null;
            Root = Insert(Root, 15);
            Root = Insert(Root, 10);
            Root = Insert(Root, 20);
            Root = Insert(Root, 8);
            Root = Insert(Root, 12);
            Root = Insert(Root, 17);
            Root = Insert(Root, 25);
         }

}