0

以下に示す二分木を前提として、関数A（root）が呼び出されたと仮定して、以下に示す二分木のノードにアクセスする順序を決定します。ツリーノードとポインタが次のように定義されていると仮定します。rootが60を含むノードへのポインタであると仮定し ます。この問題に対する私の答えを以下に示します。それが正しいか？私は何を間違えましたか？

                                   60
                                 /    \
                                30     90
                               /  \   / 
                              5   38  77
                               \  /  / \
                               8 32 62  88



struct treeNode{
  int data;
  struct treeNode *left, *right:
  {

struct treeNode *tree_ptr;

void A(struct treeNode *node_ptr){
    if (node_ptr != NULL){
    printf(“%d ,”,node_ptr->data);
    B(node_ptr->left);
    B(node_ptr->right);
   }   
}

void B(struct treeNode *node_ptr){
    if (node_ptr != NULL) {
    A(node_ptr->left);
    printf(“%d ,”,node_ptr->data);
    A(node_ptr->right);
   }
 }

回答： void Aでは、最初にnode_ptr->データを出力して、60が出力されるように指示します。次に、関数はB（node_ptr-> left）を呼び出し、次にB内でAが呼び出され（node_ptr-> left）、5であるデータを出力します。 。次に、A（node_ptr-> right）が呼び出され、Aに戻り、そのデータを印刷して、8が印刷されるようにします。次に何をすべきかよくわかりませんが、論理的には30を印刷するのは理にかなっていますが、ptrが8から30になる方法がわかりません。同じパターンで続行すると、38が印刷され、32が印刷されます。右のサブツリーの場合...9077 62 88

4

4 に答える 4

1

上記のトレースは、プレオーダーまたはインオーダーのいずれについても正しいものではありません。

于 2011-03-28T08:59:36.530 に答える
1

まず、コードに大量のエラーがあります。私はそれがもっとこのようであるべきだと思います：

struct treeNode{
  int data;
  struct treeNode *left, *right;
}

treeNode *tree_ptr;

void A(treeNode *node_ptr){
    if (node_ptr != NULL){  /// this could be just if(node_ptr)
        printf(“%d ,”,node_ptr->data);
        B(node_ptr->left);
        B(node_ptr->right);
    }   
}

void B(treeNode *node_ptr){
    if (node_ptr != NULL) {
        A(node_ptr->left);
        printf(“%d ,”,node_ptr->data);
        A(node_ptr->right);
    }
}

また、2 つの異なるトラバーサル アルゴリズムを混在させています。A()予約注文、B()注文中です。お互いではなく、自分自身を呼び出す必要がありますA()。( 、などB()の代わりに実際の変数/関数名を使用するもう 1 つの理由。)AB

于 2010-12-14T21:11:47.470 に答える
1

時間をかけて完全な実行スタックを書き出すだけです。このような：

A(60)
  printf
  B(30)
    A(5)
      ...
    printf
    A(38)
      ...
  B(90)
    ...

(ツリーの残りの部分は、読者への演習として残されています。)

次に、上から下に進み、printf ステートメントの結果を書き留めます。

于 2010-12-14T21:14:18.883 に答える
1

Aは順序通りのトラバーサルBですが、 は順序通りのトラバーサルです。

印刷の順序を理解する簡単な方法は、ノード自体にどのようにアクセスするかを調べることです。私は通常、ツリーの外側にアウトラインを描きます (ルートから始めて、最初にトラバースしているサブツリーに基づいて左または右に移動します)。事前注文トラバーサルを行っている場合、ノードの外側に沿って移動するたびにノードを出力します。順序通りのトラバーサルを行っている場合、ノードの下に移動したときにのみノードを出力します(これは順序通りのトラバーサルを見ると理にかなっています。葉を最初に出力することになるためです。それらは移動する最初のノードです)。輪郭を描くときの下）。注文後のトラバーサルを行っている場合、ノードの内側に沿って移動する場合にのみノードを出力します。

アップデート

5 と 8 の後に 30 が出力される理由は、純粋な事前注文トラバーサルを実行していないためです。あなたは予約注文と順番通りのトラバーサルの間を行き来しています。

順序を理解する簡単な方法は、コードをたどる際にコードが通過するステップを実際に書き留めることです (情報をまとめるために、私はペン/鉛筆と紙をよく使用します)。たとえば、次のようにコール スタックを書き出すことができます。

A(60)
  printf(60)
  call B(60.left)
    B(30)
      call A(30.left)
        A(5)
          printf(5)
          call B(5.left)
            B(null)
          call B(5.right)
            B(8)
              call A(8.left)
                A(null)
              printf(8)
              call A(8.right)
                A(null)
      printf(30)
      call A(30.right)
        A(38)
        ...

ノードが出力される順序と、さらに重要なことに、なぜ 8 の出力から 30 の出力に「ジャンプ」するのかを簡単に確認できます (1 つの再帰呼び出しが終了し、1 レベル戻っています)。

于 2010-12-14T21:15:18.850 に答える