二分木反復アルゴリズム

バイナリ ツリーの事前順序、イン順序、および事後順序のトラバーサルは、アルゴリズムとデータ構造における基本的な問題です。再帰バイナリ ツリー トラバーサル アルゴリズムは、再帰の典型的な応用です。

バイナリ ツリー ノードが次のように定義されていると仮定します。

構造体ノード{
 int値;
    ノード *左;
    ノード *右;
 }

 void inorder_traverse(ノード *ノード) {
 if (NULL != ノード->left) {
        ノードを左にトラバースします。
    }
    何かを実行します(ノード);
 if (NULL != node->right) {
        ノードを右にトラバースします。
    }
 }

事前順序トラバーサル アルゴリズムと事後順序トラバーサル アルゴリズムは似ています。

ただし、トラバーサル アルゴリズムだけでは不十分です。多くのアプリケーションでは、トラバーサル自体を抽象化する必要もあります。合計関数があると仮定すると、リンクリスト、配列、バイナリツリーなどのさまざまなデータ構造に適用できると期待されます。この時点で、イテレータの概念を抽象化し、イテレータを介してアルゴリズムとデータ構造を分離して、一般的なアルゴリズムをさまざまな種類のデータ構造に適用できるようになります。合計関数は次のように定義できます。

 int sum(イテレータ it)

線形構造として、リンクリストの反復子の実装は非常に単純で直感的ですが、バイナリツリーの反復子の実装はそれほど簡単ではありません。再帰トラバーサルを反復子に直接変換することはできません。その理由は、バイナリ ツリーの再帰トラバーサルが呼び出しスタック上でコンパイラによって自動的に実行され、プログラマーがこのプロセスを十分に制御できないためです。この場合、コールスタック全体のプッシュとポップを自分で制御できれば、制御の目的は達成されるのではないでしょうか。まず、二分木走査の非再帰アルゴリズムを見てみましょう。

 void inorder_traverse_nonrecursive(ノード *ノード) {
    スタックスタック;
する{
 // ノードは現在処理中のサブツリーを表し、左の子をスタックの層ごとに下に押し下げます。これは再帰アルゴリズムの左サブツリーの再帰に対応します。  
 while (NULL != ノード) {
            スタックをプッシュします(ノード)。
            ノード = ノード->左;
        }
する{
            ノード *top = stack.top();
            stack.pop(); // 再帰アルゴリズムの関数戻り値に対応して、スタックの先頭をポップアップします 
            何かする(トップ);
 if (NULL != top->right) {
                node = top->right; //現在のサブツリーを、再帰アルゴリズムの右サブツリー再帰に対応する、走査したノードの右の子に設定します。  
壊す;
            }
        }
スタックが空である間
    }
スタックが空である間
}

スタックベースの非再帰アルゴリズムを通じて、トラバーサル プロセスを制御できるようになりました。次に、これをイテレータとしてカプセル化する方法を検討します。 ここで重要なのは、トラバーサル プロセスがスタックの状態によって表されることを理解することです。したがって、反復子にはスタック構造が含まれている必要があり、各反復プロセスはスタックに対する操作であることは明らかです。イテレータ インターフェースが次のとおりであると仮定します。

クラスイテレータ{
公共：
仮想ノード* next() = 0;
 };

以下は、バイナリ ツリーの順序付きトラバーサル反復子の実装です。

クラスInorderIterator:パブリックイテレータ {
公共：
        ノードの順序を反復するノード *node) {
            ノード *current = ノード;
 while (NULL != 現在) {
                mStack.push(現在のスタック);
                current = current->left;
            }
        }
仮想ノード* next() {
 (mStack.empty())の場合{
 NULLを返します。
            }
            ノード *top = mStack.top();
            mStack.pop();
 if (NULL != top->right) {
                ノード *current = top->right;
 while (NULL != 現在) {
                    mStack.push(現在のスタック);
                    current = current->left;
                }
            }
先頭に戻る;
         }
プライベート：
        std::stack<Node*> mStack;
 };

次に、このイテレータ実装の時間と空間の複雑さを見てみましょう。明らかに、スタックは最大ですべてのノードを格納する必要があるため、その空間計算量は O(n) です。時間の複雑さはどうでしょうか? next() の呼び出しでは最大 n 回のスタック操作が実行され、トラバーサル プロセス全体で next() を n 回呼び出す必要があるため、反復子全体の時間計算量は O(n^2) になりますか?答えはノーです!各ノードは 1 回だけプッシュおよびポップされるため、反復プロセス全体の時間計算量は依然として O(n) です。実際、これは再帰的トラバーサルの時間と空間の複雑さとまったく同じです。

コード実行の順序を制御するためにスタックを明示的に使用するほかに、yield セマンティクスをサポートする言語 (C#、Python など) ではより直接的なアプローチがあります。以下は、yield に基づいたバイナリ ツリーの順序付きトラバーサルの Python 実装です。

 // パイソン 
 def inorder(t):
 tの場合:
 inorder(t.left)内のxの場合:
            収量 x
        利回りt.ラベル
x が inorder(t.right) 内にある場合:
            収量 x

yield と return の違いに関する一般的な説明は、yield が戻ると、システムは関数呼び出しの状態を保持し、次に関数が呼び出されたときに、最後の実行ポイントから実行を継続するというものです。これは、スタック セマンティクスとはまったく異なるプロセス制御セマンティクスです。 Python のインタープリタは C で書かれていますが、C は yield セマンティクスをサポートしていません。では、インタープリタはどのようにして yield をサポートするのでしょうか? 再帰的トラバーサルを反復的トラバーサルに変換する上記の経験から、Python インタープリターが yield コードに何らかの変換を加えたに違いないと推測できたと思います。再帰を非再帰に変換できた場合は、yield コードを非 yield コードに変換するコンパイラーを作成してもよいでしょう。

オリジナルリンク: http://coolshell.cn/articles/9886.html