128

最近、私の人生でBSTを多用している間、インオーダートラバーサル以外のものを使用することを考えたことさえありませんでした（プログラムをプレオーダー/ポストオーダートラバーサルを使用するように適応させることがいかに簡単かを認識し、知っています）。

これに気付いたとき、私は古いデータ構造の教科書をいくつか引き出し、事前注文と事後注文のトラバーサルの有用性の背後にある理由を探しましたが、彼らはあまり言いませんでした。

プレオーダー/ポストオーダーを実際に使用する場合の例をいくつか挙げてください。順序よりも意味があるのはいつですか？

4

6 に答える 6

170

プレオーダー、インオーダー、およびポストオーダートラバーサル戦略を使用する場合

バイナリツリーのプレオーダー、インオーダー、ポストオーダーをどのような状況で使用するかを理解する前に、各トラバーサル戦略がどのように機能するかを正確に理解する必要があります。例として次のツリーを使用します。

ツリーのルートは7、左端のノードは0、右端のノードは10です。

ここに画像の説明を入力してください

事前注文トラバーサル：

概要：ルート（7）で始まり、右端のノード（10）で終わります。

トラバーサルシーケンス：7、1、0、3、2、5、4、6、9、8、10

インオーダートラバーサル：

概要：左端のノード（0）で始まり、右端のノード（10）で終わります。

トラバーサルシーケンス：0、1、2、3、4、5、6、7、8、9、10

注文後のトラバーサル：

概要：左端のノード（0）で始まり、ルート（7）で終わります。

トラバーサルシーケンス：0、2、4、6、5、3、1、8、10、9、7

プレオーダー、インオーダー、ポストオーダーのいずれを使用するのですか？

プログラマーが選択するトラバーサル戦略は、設計されているアルゴリズムの特定のニーズによって異なります。目標は速度です。したがって、必要なノードを最速で提供する戦略を選択してください。

  1. 葉を検査する前に根を探索する必要があることがわかっている場合は、すべての葉の前にすべての根に遭遇するため、 事前注文を選択します。

  2. ノードの前にすべての葉を探索する必要があることがわかっている場合は、葉を探すために根を調べる時間を無駄にしないため、ポストオーダーを選択します。

  3. ツリーがノードに固有のシーケンスを持っていることがわかっていて、ツリーを元のシーケンスにフラット化する場合は、順序どおりのトラバーサルを使用する必要があります。ツリーは、作成されたのと同じ方法で平坦化されます。プレオーダーまたはポストオーダートラバーサルは、ツリーを作成に使用されたシーケンスに巻き戻さない場合があります。

プレオーダー、インオーダー、ポストオーダー（C ++）の再帰的アルゴリズム：

struct Node{
    int data;
    Node *left, *right;
};
void preOrderPrint(Node *root)
{
  print(root->name);                                  //record root
  if (root->left != NULL) preOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists
}

void inOrderPrint(Node *root)
{
  if (root.left != NULL) inOrderPrint(root->left);   //traverse left if exists
  print(root->name);                                 //record root
  if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists
}

void postOrderPrint(Node *root)
{
  if (root->left != NULL) postOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists
  print(root->name);                                   //record root
}
于 2013-07-15T16:05:21.077 に答える
63

先行予約：ツリーのコピーを作成するために使用されます。たとえば、ツリーのレプリカを作成する場合は、ノードを事前順序トラバーサルを使用して配列に配置します。次に、配列内の値ごとに新しいツリーで挿入操作を実行します。元のツリーのコピーが作成されます。

順序付け:: BSTで降順ではない順序でノードの値を取得するために使用されます。

事後注文::葉から根への木を削除するために使用されます

于 2017-02-27T03:12:25.500 に答える
28

ツリーの階層形式を線形形式で単純に印刷したい場合は、おそらくプレオーダートラバーサルを使用します。例えば：

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G
于 2012-02-26T20:44:09.787 に答える
4

事前注文と事後注文は、それぞれトップダウンとボトムアップの再帰的アルゴリズムに関連しています。与えられた再帰的アルゴリズムを二分木に反復的に書きたい場合、これは基本的に行うことです。

さらに、事前注文と事後注文のシーケンスが一緒になって手元のツリーを完全に指定し、コンパクトなエンコーディングを生成することを確認します（少なくともまばらなツリーの場合）。

于 2012-02-27T17:51:44.160 に答える
3

この違いが実際の役割を果たしているのを目にする場所はたくさんあります。

私が指摘する素晴らしいものの1つは、コンパイラーのコード生成です。次のステートメントについて考えてみます。 

x := y + 32

そのためのコードを生成する方法は、（もちろん）最初にyをレジスターにロードし、32をレジスターにロードし、次に2つを追加する命令を生成するためのコードを生成することです。何かを操作する前にレジスターに何かがなければならないので（仮定しましょう、常に定数オペランドを実行できますが、何でも）、この方法で実行する必要があります。

一般に、この質問に対する答えは基本的にこれに還元されます。データ構造のさまざまな部分の処理間に何らかの依存関係がある場合、違いは本当に重要です。これは、要素を印刷するとき、コードを生成するとき（外部状態が違いを生むので、もちろんこれも一元的に表示できます）、または最初に処理される子に応じて計算を含む構造に対して他のタイプの計算を行うときに表示されます。 。

于 2012-02-26T20:45:59.537 に答える
0

順序：解析ツリーは演算子の優先順位に従うため、任意の解析ツリーから元の入力文字列を取得します。最も深いサブツリーが最初にトラバースされました。したがって、親ノードの演算子は、サブツリーの演算子よりも優先順位が低くなります。

于 2021-08-12T07:06:28.247 に答える