如何创建二叉树

Question

我不是指二进制搜索树.

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

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

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

因此,表示和级别顺序遍历在这里非常容易.

但我认为,有序,下订单,预订很难.

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

Answer 1

如果我理解正确,您希望从数组创建二叉树

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

这应该预先填充值为1 - 5的二叉树,如下所示:

    1
   / \
  2   3
 / \
4   5

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

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

Answer 2

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

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

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

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

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