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

前の記事では、二分木の再帰的走査アルゴリズムについて説明しました (二分木のルート優先 (事前順序) 走査の改良) この記事では主に非再帰について説明します。スタック構造を使用した二分木のアルゴリズム

ルートトラバーサルによって得られた非再帰アルゴリズムのアイデアは次のように要約されます:

1) スタックにプッシュします。主に最初にヘッド ノードをスタックにプッシュし、次にこのノードにアクセスします

2) 一方、左側の子にノードがなくなるまで現在のノードをループします

3) ノードの右側の子が true の場合は 1) に進み、トラバースを続行します。それ以外の場合は、現在のノードを終了して親ノードに移動し、1) に進みます。

まず、このアイデアに準拠したアルゴリズムを見てみましょう:

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

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) ここではスタック構造が使用されています。上記の

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

を参照してください。

2) ここでノードを保存する際に、ノードのアドレスであるポインタを保存し、popする際にポインタを使用するため、&pBiNodeが取られ、pBiNodeではありません。ポインタの使用方法については、ご自身で考えてください。BiTNode *pBiNode が最も分かりやすく、BiTree pBiNode に定義すると理解しやすくなります。

上記のアルゴリズムは実際には間違っています。なぜ？ ここをずっとチェックしていたら、この間無限ループが発生していて、左のサブツリーから抜けた後に右のサブツリーが表示されない場合もあったのですが、最後に最初のwhile判定条件を修正しました。ポップした後、スタックが空であっても正しいサブツリーが存在する場合は、続行できません。後で説明しますが、ここでは null ポインタがプッシュされていません。プッシュの例を見てください。次のように、ヌル ポインターは主に左側のサブツリーが空のときにスタックにプッシュされます。

コードをコピー

コードは次のとおりです。

int PreOrderTraverseNonRecursive(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)) {

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 であっても問題ありません。

コードをコピー コードは次のとおりです:

//非再帰的事前順序走査バイナリ ツリーの
int PreOrderTraverseNonRecursiveEx(const BiTree &T,
int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return - 1;
}
BiTNode *pBiNode = T;

SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);

while ( !IsStackEmpty(S) || pBiNode) //主な変更はこの文です

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

これを最初の 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

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