从inorder和preorder遍历重构二叉树 [英] Reconstructing binary tree from inorder and preorder traversals

问题描述

我编写了以下代码，用于从其inorder和preorder遍历构造树。它看起来对我来说是正确的，但它产生的最终树不具有与它构建的输出相同的顺序输出。谁能帮我找到这个函数的缺陷？

I have written the following code for constructing a tree from its inorder and preorder traversals. It looks correct to me but the final tree it results in does not have the same inorder output as the one it was built from. Can anyone help me find the flaw in this function?

public btree makeTree(int[] preorder, int[] inorder,  int left,int right)
{
    if(left > right)
        return null;

    if(preIndex >= preorder.length)
        return null;

    btree tree = new btree(preorder[preIndex]);
    preIndex++;

    int i=0;
    for(i=left; i<= right;i++)
    {
        if(inorder[i]==tree.value)
            break;

    }


        tree.left = makeTree(preorder, inorder,left, i-1);
        tree.right = makeTree(preorder, inorder,i+1, right );

    return tree;

}

注意：preIndex是在函数外声明的静态。

Note: preIndex is a static declared outside the function.

推荐答案

in = {1,3,2,5}; pre = {2,1,5,3};

我手工构建树有些困难。 pre 显示 2 必须是根，显示 {1,3}是左子树的节点， {5} 是正确的子树：

I've some difficulties constructing the tree 'by hand'. pre shows that 2 must be the root, in shows that {1,3} are nodes of the left subtree, {5} is the right subtree:

      2
     / \
    /   \
  {1,3} {5}

但是知道这一点， 3 不能是 pre 因为它显然是左子树的元素和我们有一个正确的子树。这些树的有效前序遍历是 {2,1,3,5} 或 {2,3,1,5} 。但是 {2,1,5,3} 是不可能的。

But knowing this, 3 can't be the last element in pre because it is clearly an element of the left subtree and we have a right subtree. Valid preorder traversals for these trees are {2,1,3,5} or {2,3,1,5}. But {2,1,5,3} is impossible.

也许这个方法中没有bug但是在您的算法中创建inorder和preorder遍历。或者，可能是，你在[] 和 pre [] 中随机选择了的值？

Maybe the bug is not in this method but in your algorithm to create inorder and preorder traversals. Or, could it be, that you chose the values for in[] and pre[] randomly?

这篇关于从inorder和preorder遍历重构二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！