1

一般的なツリー (最初の子、次の兄弟表記) とバイナリ ツリーを深さ優先でトラバースするための再帰関数を実装するように求められました。

関数は、最後にアクセスしたときにノードを出力する必要があります。たとえば、下のツリーの場合、ノードは次の順序で出力されます。二分木の機能は実行したと思いますが、一般的な機能は実行できませんでした。

二分木のための私のコードは次のとおりです。

void PostOrder(node* root) {
    if (root == NULL)
        return;
    else { 
          PostOrder(root->left); 
          PostOrder(root->right);
          printf(‘%c’, root->key); 
    } 
}

誰でも助けることができますか？

4

1 に答える 1

1

最初の子と次の兄弟の 2 つのポインターを持つ典型的な「バイナリ ツリーとして表される一般的なツリー」のように聞こえます。各子に下向きの矢印と右向きの矢印がある、標準のバイナリ ツリーとしてツリーを描くことができます。

あなたのコメントで説明されているツリーは次のようになっていると思います。

a
|
V
b ------------> c
|               |
V               V
d --> e --> f   g
                |
                V
                h --> i

ツリーの各ノードで、次のことを行います。

  1. 最初の子を処理して、最初にすべての子孫を出力します (下向き矢印に従います)。
  2. 次に、ノードの値を出力します
  3. 次に、兄弟を処理します (右矢印に従います)。

これを上記のツリーに適用すると、次のようになります。

GeneralTreePostOrder(a) ->
    GeneralTreePostOrder(b) ->   # Follow child pointer
        GeneralTreePostOrder(d) ->   # Follow child pointer
            # No children
            print d
            GeneralTreePostOrder(e) ->   # Follow sibling pointer
                 # No children
                 print e
                 GeneralTreePostOrder(f) ->   # Follow sibling pointer
                     # No children
                     print f
                     # No more siblings
        print b
        GeneralTreePostOrder(c) ->   # Follow sibling pointer

など、印刷しd e f h i g c aます。

一般ツリー用の新しい関数を作成します (NBprintfは二重引用符で囲まれた書式文字列を使用する必要があります):

void GeneralTreePostOrder (node* root) {
    if (root == NULL)
        return;
    else {
         GeneralTreePostOrder (root->left); // Process children
         printf ("%c", root->key); 
         GeneralTreePostOrder (root->right); // Process siblings
    } 
}
于 2012-12-02T22:14:51.483 に答える