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

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

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

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

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

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

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

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

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

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