如何创建一个二叉树 [英] How to create a binary tree

问题描述

我不是说二叉搜索树.

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

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.

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

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

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

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.

因此表示和层序遍历在这里非常容易.

so representation and level order traversal is very easy here.

但我认为，in order, post-order, pre-order 很难.

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

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

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.

推荐答案

如果我没理解错的话，你想从一个数组创建一个二叉树

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

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

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

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

这篇关于如何创建一个二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！