3

インオーダートラバーサルとプレオーダートラバーサルからツリーを構築するために、次のコードを記述しました。私には正しいように見えますが、結果として得られる最終的なツリーには、それが構築されたものと同じ順序の出力がありません。誰かが私がこの関数の欠陥を見つけるのを手伝ってもらえますか？

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は、関数の外部で宣言された静的なものです。

4

1 に答える 1

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

「手で」ツリーを構築するのにいくつかの困難があります。がルートでなければならないことをpre示し、{1,3} が左サブツリーのノードであることを示し、右サブツリーであることを示します。2in{5}

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

しかし、これを知っている3と、最後の要素になることはできません。preなぜなら、それは明らかに左のサブツリーの要素であり、右のサブツリーがあるからです。これらの木の有効な事前順序トラバーサルは{2,1,3,5}または{2,3,1,5}です。でも{2,1,5,3}無理です。

おそらく、バグはこのメソッドではなく、inorder および preorder トラバーサルを作成するアルゴリズムにあります。それとも、 と の値をランダムに選択したのin[]でしょpre[]うか?

于 2010-07-15T08:24:21.293 に答える