バイナリ ツリー事前順序 traversal_javascript スキルのための非再帰アルゴリズムの具体的な実装

int PreOrderTraverseNonRecursiveEx(const BiTree &T, int ( *VisitNode) (TElemType データ))
{
if (T == NULL)
{
return -1;
}

BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);

while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
} > Pop(&S, (SElemType*)&pBiNode)
}
if (pBiNode->rchild == NULL); 🎜> {
Pop(&S, (SElemType*)&pBiNode); // この時点でスタックが空の場合は問題があります
}
pBiNode = pBiNode->rchild;
}

return 0;
}

注: 1) ここではスタック構造が使用されています。上記の

シーケンシャル構造で保存されたスタック

を参照してください。

BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);

while (!IsStackEmpty(S)) {

GetTop(S, (SElemType*)&pBiNode);
while (pBiNode)
{
VisitNode(pBiNode->data );

pBiNode = pBiNode->lchild;

Push (&S, (SElemType)pBiNode) , (SElemType*)&pBiNode);
}
if ( !IsStackEmpty(S)); 🎜> {
Pop(&S, (SElemType*)&pBiNode);
pBiNode = pBiNode-> rchild;
Push(&S, (SElemType)pBiNode);
}
}

0 を返す;
}

これは次のようになります。最初にルート ノードをプッシュし、次に左側のサブツリーが空かどうかを判断し、空でない場合はスタックにプッシュします。そうでない場合は、while ループを終了した後、NULL ノードをポップします。スタックを調べ、現在のスタックが空かどうかを判断します。空でない場合は、スタックをポップして親ノードを取得します。次に、右側の子を判断し、右側の子ノードをプッシュして、右側の左側の子かどうかを判断します。サブツリーは空なので、ループを続行します。

ここには 2 つの無駄な場所があります。1 つは空の子ノードをスタックにプッシュすること、もう 1 つは GetTop を頻繁に使用してスタックの最上位要素を取得することです

ここで、最初に設計したアルゴリズムに戻りますが、たまたま NULL ポインターや空の子ノードがプッシュされていませんが、出力は完了していません。ここでは、スタックを判断するときにそれを追加することを考えます。現時点では、次のように、左側のサブツリー ノードが表示されず、右側のサブツリー ノードが表示されないという問題が発生しないように、ノードが NULL であっても問題ありません。

これを最初の while ループに追加すると、テスト ケースはバイナリ ツリーの事前順序トラバーサルと似ています。前のセクションのバイナリ ツリーの例を次のようにテストします:

この時点での入力データは 12 34 0 0 78 0 0 のままです。テスト結果は次のとおりです。

--- BiTree ---
BiTree ノード データを入力してください:
12
BiTree ノード データを入力してください:
34
BiTree ノード データを入力してください:
0
BiTree ノード データを入力してください:
0
BiTree ノード データを入力してください:
78
BiTree ノード データを入力してください:
0
BiTree ノード データを入力してください:
0
12 34 78

これではテストとしては十分ではありません。次のバイナリ ツリーを見てみましょう

このときの入力データは、12 34 24 0 0 50 0 0 78 37 0 0 0 となるはずです。テスト結果は次のとおりです。

--- BiTree ---

BiTree ノード データを入力してください:
12
BiTree ノード データを入力してください:
34
BiTree ノード データを入力してください:
24
BiTree ノード データを入力してください:
0
BiTree ノード データを入力してください:
0
BiTree ノード データを入力してください:
50
BiTree ノード データを入力してください:
0
BiTree ノード データを入力してください:
0
BiTree ノード データを入力してください:
78
BiTree ノード データを入力してください:
37
BiTree ノード データを入力してください:
0
BiTree ノード データを入力してください:
0
BiTree ノード データを入力してください:
0
12 34 24 50 78 37

事前順序トラバーサルからも、それが正確であることがわかります。また、これらのアルゴリズムは、事前順序トラバーサルのみに適用されるものではありません。上記のアルゴリズムで訪問などを削除し、適切な場所に追加すれば完了です