我有一个用预序遍历表示的二叉树,它看起来像这样:{1 4 6 10 0 0 0 7 0 8 0 0 2 5 0 0 3 9 0 0 0 },其中0表示没有元素的子元素。
如何从这些数据构造原始的二叉树?我试图用递归来解决问题,但是我还没有意识到如何处理节点的正确子节点,因为我无法计算它们在数组中的位置,除非它们有一个叶子作为父节点(叶子后面有两个零,这表示它没有子节点)。
我觉得解决办法应该很简单,但还是看不出来。

最佳答案

像这样简单的事情可能对你有用。您只需要在输入序列的预排序解释中重新构建树。以下代码不会验证输入序列以检查其是否是有效的树表示形式。

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

关于algorithm - 来自指定遍历的二叉树,其中指定了缺席的子级,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/35093006/

10-10 01:03