0

このツリーを考えてみましょう:

           7
         /    \
       /        \
      /          \
     1            9
    /  \         /  \
   0    3       8   10 
       / \
      2   5
         / \
        4   6

順番に：

0、1、2、3、4、5、6、7、8、9、10

予約注文：

7、1、0、3、2、5、4、6、9、8、10

Inorder traversal を実行している間、一番左のノードが最初に特定され、そこから探索が開始されます。しかし、Preorder に関しては、同じロジック (左端の中間ノードと同様) は適用されません。

上記のツリーには、ルート 7 を除いて、中間ノードである 1 と 9 があります。1 は左端の中間ノード、9 は右端の中間ノードです。上記の InOrder に適用されたロジックによると、Preorder トラバーサルはノード 1 から開始されているはずですが、これは一番左の中間ノードですが、そうではないのはなぜですか?

Inorder ではトラバーサルが左端のノードから開始されるのに、PreOrder トラバーサルが左端の中間ノードから開始されないのはなぜですか?

ありがとう、クリス。

4

2 に答える 2

3

Preorder は常に親をその子孫 (つまりその定義) の前に配置するため、ルートから開始する必要があります。必要に応じて、ルートに「最も中間のノード」という用語を使用できます。

preorderの典型的な使い方は、標準の関数表記です:

f(g(x, h(y, z)))

これは、内部ノードに関数名を使用し、変数を葉ノードとして使用する次の式ツリーの事前順序表記です。

      f
      |
      g
     / \
    x   h
       / \
      y   z

一方、+andのような演算子を*使用した通常の表記では、inorderを使用します。

a + b * c

の順序表記です

    +
   / \
  a   *
     / \
    b   c

*より強力に結合する標準的な数学的優先順位規則を使用する+場合

そして、逆ポーランド記法で式を書くことはpostorderの例です。

于 2013-08-29T21:22:06.867 に答える
1

順序: 左サブツリーをトラバースします。現在のノードにアクセスします。右サブツリーをトラバースします。

予約購入: 現在のノードにアクセスします。左サブツリーをトラバースします。右サブツリーをトラバースします。

Postorder: 左サブツリーをトラバースします。右サブツリーをトラバースします。現在のノードにアクセスします。

左のサブツリーが欠落していない限り、Inorder と Preorder に同じノードが存在することはないことに注意してください。

ただし、左サブツリーがある場合は、 Inorder 表現とPostOrder表現で同じノードを持つことができます。

于 2013-08-29T21:45:31.877 に答える