バイナリツリーのための非再帰的ポストオーダートラバーサルアルゴリズムの詳細な説明_JavaScriptスキル

事前順序、中間順序、事後順序の非再帰的走査の中で、事後順序が最も厄介です。スタック上のノードへのポインタだけを保持する場合は、いくつかの追加情報が必要です。スタックの真ん中に格納されます。
多くの方法がありますが、ここでは 1 つだけを紹介します。まずスタック ノードのデータ構造を定義します

コードをコピーします コードは次のとおりです。

typedef struct{Node * p; ;}SNode //Node は二分木のノード構造です。 rvisited==1 は、p が指すノードの右のノードが訪問されたことを意味します。

lastOrderTraverse(BiTree bt){
//まず、ルートノードから開始して左下に進み、最後まで進み、パス上のすべてのノードをスタックにプッシュします。
p = bt; パス
bt = bt.lchild;
}

//次にループに入ります

while(!Stack.empty()){ //スタックが空でない限り

sn = Stack.getTop() // sn が最上位ノードですスタックの

//任意のノード N に左の子がある限り、N がスタックにプッシュされた後、N の左の子もスタックにプッシュされる必要があることに注意してください (これはアルゴリズムの後半に反映されます)。スタックの一番上にある要素を取得すると、この要素には左の子がないか、左の子がアクセスされたかのいずれかであることが確認できるため、現時点では左の子については気にしません。正しい子のことだけを気にします。

//その右側の子が訪問されているか、要素に右側の子がない場合、事後走査の定義に従って、この時点でこのノードにアクセスできます。

if(!sn.p.rchild || sn.rvisited){

p = Pop();
visit(p);
}
else //その右の子であれば Itは存在し、 rvisited は 0 です。これは、その右の子がこれまでに触れられていないことを意味するため、その右の子を処理します。
{
//この時点で、右の子ノードから開始して左下まで最後まで進み、このパス上のすべてのノードをスタックにプッシュする必要があります。

// もちろん、ノードをスタックにプッシュする前に、ノードの rvisited を 1 に設定する必要があります。これは、ノードの右の子をスタックにプッシュするということは、その右の子がその前に訪問されることを意味するためです (これは理解しやすいですが、なぜなら、訪問時には常にスタックの最上位から要素を取得するからです)。次に要素がスタックの一番上にあるとき、その右側の子が訪問されているはずであることがわかります。そのため、ここでは rvisited を 1 に設定できます。

sn.rvisited = 1;

// 左下に移動し、パス上のすべての要素をスタックにプッシュします
p = sn.p.rchild;

while(p != 0){

Push(p, 0 ) ;
p = p.lchild;
}
}//このラウンドのループは終了しました。スタックにプッシュされたばかりのノードについては心配する必要はありません。これらのノードを大事にしてください。
}
}