1

列挙子のメソッド MoveNext に問題があります。二分探索木のイテレータが必要です。列挙子のコンストラクターで、ノードをツリーのルートに初期化します。Current は、次の項目のために返すようにした値です。メソッド moveNext のこのコードは、間違った値を返します。

public bool MoveNext()
    {

        if (Current == null)
            Current = node.Value;
        else if (node.Left != null)
        {
            node = node.Left;
            Current = node.Value;
        }
        else if (node.Right != null)
        {
            node = node.Right;
            Current = node.Value;
        }
        else
        {
            node.Value = Current;
            do
            {
                if (node.Parent == null)
                    return false;
                node = node.Parent;
            } while (node.Right == null);
            Current = node.Value;
        }
        return true;

    }
4

4 に答える 4

2

そのコードにはいくつかの問題があります。まず、else-branch で、ツリー内のノードの値を変更していますCurrent = node.Value;。おそらくnode.Value = Current;.

ただし、それは主な問題ではありません。あなたのイテレータは、非常に簡単に無限ループに陥ります。すべてが下にたどるのに妥当に見えます。葉ノードまで一番左のパスをたどります。

次に、子を持つ祖先ノードが見つかるまでバックトラックしRight、そのノードの値を生成します。ただし、この値は途中でイテレータによってすでに返されています。また、どの道をたどったか覚えていないため、次のステップでは、必然的に前と同じ道を再びたどり、その後再び戻って、というように無限に続きます。

これを修正するには、バックトラックするときに親ノードで停止しないでください。次のパスの最初のステップをすでに実行してください。これが常にRight何らかのノードの子であることは事実ですが、最初のRight祖先の子であるとは限りません。これは、すでにその分岐から遡っている可能性があるためです。

要約すると、これ以上下に行けない場合は、1 レベル上に戻ります。LeftまたはRight子ノードから来ているかどうかを確認します。左側から来た場合は、右側にある場合は下に移動し、Currentその値に設定します。そうでない場合、またはすでに正しい子供から来ている場合は、別のレベルを上に再帰します。

于 2013-10-27T11:19:11.943 に答える