2

Binary Tree に次の値 ({18, 26, 52, 78, 45, 16, 67, 58, 73, 11}) を入力すると、次のツリーが表示されます。

二分木の画像

PreOrder トラバーサルと InOrder トラバーサルの両方が期待どおりに機能します。しかし、PostOrder (PO) に関しては、私が思っていたものとは違うものを受け取っています。

私が理解しているように、PO は最初に左のサブツリーを検索し、次に右のサブツリーを検索し、最終的にノード (ルート ノードで終了) を検索します。

このツリーを介して PO をトラバースすると、{11, 16, 45, 58, 73, 67, 78, 52, 26, 18} という結果になります。この結果の背後にあるロジックを書き出すと、次のようになります。ルートから開始し、完全に左に進むと、最初のノードである 11 になります。その後、1 レベル上に移動し、その親 (16) を取得します。ルートに到達するまでこれを続けます (これは leftChild ではないため含まれません)。この最初の左側のサブツリーを通過したら、右側のレベルを下って、そこで leftChilds をチェックします。何もない場合は、45 を見つける別のレベルに移動します。

この時点で、{11, 16, 45} のリストがあります。これを続けて、結果の次の値である 58 になります。これが私の混乱の原因です。次に取得する値は、予想される 67 とは対照的に、73 です。別の leftChild (その親) が見つかると、なぜ 73 にジャンプするのでしょうか?

次のコードは、PostOrder のツリーをトラバースします。

public void postorderTraversal(){
    postorderHelper(root);
}

private void postorderHelper(Node node){
    if(node != null){
        postorderHelper(node.getLeftNode());
        postorderHelper(node.getRightNode());
        System.out.print(node.getData() + " ");
    }
}

これは、値が 73 のノードが parentNode の前に処理されるためだと思いますが (左右が上位の優先度)、45-52-78 の三角形ではなぜそうではないのでしょうか?

4

1 に答える 1

4

これは、値が 73 のノードが parentNode の前に処理されるためだと思いますが (左右が優先)、なぜ 45-52-78 の三角形に当てはまらないのでしょうか?

それは、45 が 78 よりも前に来て、78 が 52 よりも前に来るという点です。

左の兄弟は、常に親の前に訪問される右の兄弟よりも先に訪問されます。それらの間で他に何が訪問されるかは、左右の兄弟が持つ子供に依存します。

ツリートラバーサルに関するウィキペディアのページでは、次のように説明されています。

空でないバイナリ ツリーをポストオーダーでトラバースするには、各ノードで次の操作を再帰的に実行します。

  • 左のサブツリーをトラバースします。
  • 右のサブツリーをトラバースします。
  • ルートにアクセスします。

したがって、すべての子にアクセスした場合にのみノードにアクセスし、右のサブツリーの前に常に左のサブツリーにアクセスします。結果のすべてがこれに沿っています。

于 2013-01-03T14:18:06.447 に答える