0

ウィキペディアで次の写真を見つけました。ここに画像の説明を入力

写真の下のテキストによると、順序は次のとおりです。A、B、C、D、E、F、G、H、I

AFの順番はわかりますが、最後の3つのノードの順番がわかりません。H、I、Gのはずじゃないの？2回目の遭遇で内部ノードをリストし、1回目に去ることになっていたと思いましたか?

編集: 写真の木が二分木ではなく一般的な木である場合、私の注文は正しいでしょうか? (そのため、G には、右ノードとヌル左ノードではなく、ノードが 1 つしかありません。)

4

3 に答える 3

4

残念ながらウィキペディアは正しいです！

詳細なアルゴリズム

inorder_traversal(node)
{
    if(node!=NULL)
       {
           inorder_traversas(node->left);                          
           print(node->data);         //you overlooked this statement on reaching G
           inorder_traversal(node->right);              
       }
}

どこでポイントを逃していますか/間違った方向に進んでいますか?

F から G に到達すると、NULL である G の左の子に入ろうとしました (つまりinorder_traversal(node->left)、アルゴリズムがチェックし、G の左の子が NULL であるため、ステートメントは失敗しましたif(node!=NULL) 。その後、再び G に戻ります。その後、あなたは そこに Gを出力するprintステートメント - その print ステートメントを見落とした後、 node->right が NULL かどうかをチェックする次のステートメントにジャンプしました - null ではないことがわかりました (I に移動しました)。I を直接印刷し、その左の子をチェックしました。左の子Hがそこにあったので、それを印刷してからI に戻りました- 親、その右の子は null でした。したがって、ウィキペディアは正しいです。

inorder traversal をテストするためのヒント : 入力データとして整数 (または通常は数値) を受け入れるバイナリ ツリーを作成します。inorder 方式でトラバースすると、数字は昇順で出力されます。

于 2015-07-21T19:49:44.240 に答える
1

ウィキペディアで言及されている答えは正しいです。AFわかるって言ってたから、Gからもらおう。

順序通りのトラバーサルは、左 - 親 - 右のシリーズに従います。したがって、F がトラバースされ、アルゴリズムが F の右の子に移動すると、最初に G に遭遇し、次に G の左の子を見つけようとします。G の左の子は null であるため、何も出力されず、親に移動します。 、つまり G; したがって、G が印刷されます。ここで、G の右の子である I に進みます。次に、I の左の子である H を見つけて出力します。次に、親である I に戻り、それを出力します。次に、I の右側にトラバースし、それが null であることを検出します。すべてのノードがトラバースされたので、アルゴリズムは終了します。したがって、次数は GHI です。

于 2015-07-21T15:11:02.930 に答える
0

順序通りのトラバーサルは次のように機能します。

1- print the left sub tree.
2- print the root.
3- print the right sub tree

あなたが提供した例では：

1- the left sub-tree of `G` is empty, so we do not print any thing.
2- we print the node `G`.
3- finally we print the right sub-tree of `G`
于 2015-07-21T15:09:20.270 に答える