来自 pre-order 遍历的二叉树，没有指定 children

Question

我有一个用pre-order遍历表示的二叉树，它看起来像这样：{1 4 6 10 0 0 0 7 0 8 0 0 2 5 0 0 3 9 0 0 0 }，其中0表示缺少child个元素。

如何根据这些数据构建原始二叉树？我试图用递归解决问题，但我还没有意识到如何处理正确的 children 节点，因为我无法计算它们在数组中的位置，除非它们有叶子作为 parent（叶子后面有两个零的情况，表示它没有children）。

我觉得解决方案应该很简单，但还是看不出来。

Answer 1

像这样简单的方法可能适合您。您只需要在输入序列的预序解释中重新构建树。以下代码不验证输入序列以检查是否是有效的树表示。

struct BTNode {
    int data;
    BTNode* left;
    BTNode* right;
}

BTNode* BuildTree(int* sequence, int& pos) {
    int value = sequence[pos++];
    if (value == 0)
        return nullptr;
    BTNode* node = new BTNode;
    node->data = value;
    node->left = BuildTree(sequence, pos);
    node->right = BuildTree(sequence, pos);
    return node;
}

来自 pre-order 遍历的二叉树，没有指定 children

binary tree from pre-order traversal with absent children specified

algorithm

tree

binary-tree

preorder