1

これはかなり単純な質問です。ツリーを表現するとき、どの方法 (ポスト オーダー、イン オーダー、プレ オーダー) であっても、葉は常に同じ順序で表示されることに気付きました。右。

ちょっと気になったのですが、何か理由があるのでしょうか？

私はそれらを研究し始めたばかりで、これを思いつきました。

編集。：

私はこのような木を持っています：

        A
    B       C
  D       E   F

リーフ ノードは、D、E、および F です。

予約注文は次のとおりです: A、B、D、C、E、F

順番は、D、B、A、E、C、F です。

ポストオーダーは次のとおりです: D、B、E、F、C、A

リーフ ノードは、選択した順序に関係なく、常に左から右に表示されます。問題は、なぜこのようになっているのかということです。これらのノードがこの順序で表示されるために、これらのノードに与えられた用途は何ですか。

私は、これらの種類のツリーが再帰的な手順の表現として使用されていることを読んでいるので、右の葉ノードは左葉ノードが発生した後に現れるケースであり、それが後で表現に現れる理由だと思いますか?

4

3 に答える 3

1

これらのすべてのトラバーサル: プレオーダー、インオーダー、およびポストオーダーのトラバーサルは、深さ優先のトラバーサルです。それらのすべてで、左ノードは右ノードの前に処理されます (ルートのみが振動します)。

Preorder :  <ROOT>  LEFT   RIGHT
Inorder  :  LEFT   <ROOT>  RIGHT
Postorder:  LEFT    RIGHT <ROOT>

これらのトラバーサルのそれぞれで、最終的には左から右に移動しています。

したがって、リーフ ノードは常に同じ順序で、つまり 3 つのトラバーサルすべてで順番に表示されます。

上記のソリューションには、ルートからの距離が異なる葉に関するポイントがありました。次の例に対して検証しました。

ここに画像の説明を入力

PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3
InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11
PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8

この場合でも順序付けは成り立ちます

目的: 左右パターンの結果のように見えます。

于 2014-03-25T00:26:29.647 に答える