22

二分木（BSTではない）の順序通りのトラバーサル（パンケーキとも呼ばれます）について、少し前に受講した学術コースからの次のテキストがあります。

順序付けされたツリー トラバーサル

木の外側に線を引きます。ルートの左側から始めて、ツリーの外側を一周し、ルートの右側で終了します。できるだけ木に近づきますが、木を横切らないでください。(ツリー — その枝とノード — を堅固な障壁と考えてください。) ノードの順序は、この線がその下を通過する順序です。ノードの「下」に移動するタイミングがわからない場合は、常に「左側」のノードが最初に来ることを覚えておいてください。

使用した例を次に示します (以下のツリーとは少し異なります)。

木 1

しかし、Google で検索すると、矛盾する定義が表示されます。たとえば、ウィキペディアの例:

ツリー定義

順序付けされたトラバーサル シーケンス: A、B、C、D、E、F、G、H、I (leftchild、rootnode、right node)

しかし、定義＃1（の私の理解）によれば、これは

A, B, D, C, E, F, G, I, H

どの定義が正しいか誰でも明確にできますか? どちらも異なるトラバーサル メソッドを記述している可能性がありますが、たまたま同じ名前を使用しています。査読済みの学術論文が間違っているとは信じられませんが、確信は持てません。

4

14 に答える 14

37

描画での私の悪い試みでは、ここにそれらがどのように選ばれるべきかを示す順序があります。 代替テキスト

描画されている線の真上にあるノードを選択します。

于 2009-01-28T01:04:07.480 に答える
26

定義は忘れて、アルゴリズムを適用する方がはるかに簡単です。

void inOrderPrint(Node root)
{
  if (root.left != null) inOrderPrint(root.left);
  print(root.name);
  if (root.right != null) inOrderPrint(root.right);
}

たったの3行です。事前注文と事後注文の順序を並べ替えます。

于 2009-01-28T01:52:43.230 に答える
4

注意深く読むと、最初の「定義」はルートの左側から開始することを示しており、ノードの順序はノードの下を通過するときに決定されることがわかります。したがってB、最初のノードではありません。に向かう途中で左から通過しA、最初に下を通過した後、上に移動して 下Aを通過します。したがって、両方の定義で同じ結果が得られるようです。 B

于 2009-01-28T01:04:01.783 に答える
2

個人的には、この講義はとても役に立ちました。

于 2010-07-05T00:12:50.043 に答える
1

どちらの定義でも同じ結果が得られます。最初の例の文字にだまされないでください-パスに沿って数字を見てください。2番目の例では、パスを示すために文字を使用しています。おそらく、それがあなたを失望させているのです。

たとえば、最初のツリーのアルゴリズムを使用して2番目のツリーがどのようにトラバースされるかを示す例の順序では、「B」の後に「D」を配置しますが、の左側の子ノードがまだ存在するため、配置しないでください。 Dが利用可能です（そのため、最初の項目には「この行がその下を通過する順序」と記載されています。

于 2009-01-28T01:17:36.750 に答える
1

aルートを持つ最初の二分木は、正しく構築されていない二分木だと思います。

ツリーのすべての左側がルートより小さく、ツリーのすべての右側がルート以上になるように実装してみてください。

于 2010-08-04T00:48:03.583 に答える
1

適切なトラバーサルは次のようになります: リーフ ノード (ルート ノードではない) で可能な限り左側

左ルート右

ABヌル

CDE

ヌル FG

ハイヌル

F はルートまたはレフトです。よくわかりません

于 2012-05-19T12:47:44.137 に答える
1

これは遅いかもしれませんが、後で誰にとっても役立つ可能性があります..ダミーまたはヌルノードを無視する必要はありません.たとえば、ノードGには左ヌルノードがあります..このヌルノードを考慮すると、すべてがうまくいきます..

于 2011-12-22T11:19:15.323 に答える
0

ウィキで言及されているように、私によると、順序通りのトラバーサルのシーケンスは左-ルート-右です。

A、B、C、D、E、Fまで、あなたはすでに理解していると思います。ルート F の後、次のノードは G であり、ルール (left-root-right) に従って null-g-right に従って、左ノードではなく右ノードを持ちます。現在、私は G の右側のノードですが、左側のノードがあるため、トラバーサルは GHI になります。正解です。

お役に立てれば。

于 2010-03-03T18:42:21.437 に答える
0

しかし、定義＃1（の私の理解）によれば、これは

A, B, D, C, E, F, G, I, H

残念ながら、あなたの理解は間違っています。

ノードに到着したら、現在のノードを見る前に利用可能な左側のノードに降りる必要があります。次に、利用可能な右側のノードを調べます。C の前に D を選択した場合、最初に左側のノードに降りませんでした。

于 2009-01-28T01:38:19.780 に答える
0

インライン ツリー トラバーサルの場合、トラバーサルの順序は左ノード右であることに注意する必要があります。競合している上の図の場合、左にあるリーフ (子) ノードを読み取る前に親ノードを読み取ると、エラーが発生します。

適切なトラバーサルは次のようになります: リーフ ノード (A) で可能な限り左に移動し、親ノード (B) に戻り、右に移動しますが、D にはその左側に子があるため、再び下に移動し (C)、上に戻ります。 C の親 (D) へ、D の右の子 (E) へ、ルート (F) に逆戻り、右の葉 (G) に移動、G の葉に移動しますが、左の葉ノードがあるため、そこに移動します (H) 、親 (I) に戻ります。

上記のトラバーサルは、ノードを括弧内にリストしたときにノードを読み取ります。

于 2010-05-18T03:18:04.143 に答える
-2

予約注文の場合は正解、注文注文の場合は正しくありません

于 2014-02-25T17:35:26.143 に答える