我编写了以下代码,用于根据中序和先序遍历构造树。在我看来,它是正确的,但它生成的最终树没有与其构建的树相同的有序输出。谁能帮我找出这个函数的缺陷吗?
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 是在函数外部声明的静态变量。
in = {1,3,2,5}; pre = {2,1,5,3};
我在“手工”构建树时遇到一些困难。pre
表明2
一定是根,in
表明 {1,3} 是左子树的节点,{5}
是右子树:
2
/ \
/ \
{1,3} {5}
但知道这一点,3
不能是最后一个元素pre
因为它显然是左子树的元素and我们有一个右子树。这些树的有效前序遍历是{2,1,3,5}
or {2,3,1,5}
. But {2,1,5,3}
是不可能的。
也许错误不在这个方法中,而是在您创建中序和先序遍历的算法中。或者,您可能选择了以下值:in[]
and pre[]
随机?
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)