-1

以下のようなツリーがあるとします。

          A                Root Level
        /   \
       /     \
      G       Z            Level 1
     / \     /  \
    /   \   /    \
   C     D  T     J        Level 2

3 つの質問があります。

  • レベル 1 のノードが最初に出力され、次にルート レベル、次にレベル 2 が出力されるように、このツリーをトラバースするにはどうすればよいですか

    G、Z、A、C、D、T、J

  • レベル 1 のノードが最初に出力され、次にレベル 2、次にルート レベルが出力されるように、このツリーをトラバースするにはどうすればよいですか

    G、Z、C、D、T、J、A

  • レベル 2 のノードが最初に出力され、次にレベル 1、次にルート レベルが出力されるように、このツリーをトラバースするにはどうすればよいですか?

    C、D、T、J、G、Z、A

私はウィキペディアで木をたどっていて、かつてインタビューで尋ねられた古い質問を思い出しました。質問は上記の 3 つのいずれかだったと思います (おそらく 1 つ目か 2 つ目)。

4

1 に答える 1

0

Preorder traversal: サブツリーの前にルートにアクセスする 

void preorder( BTREE__NODE_p_t node )
    if ( node != NULL )
        visit( node )
        preorder( node->left )
        preorder( node->right )

順序通りのトラバーサル: サブツリーにアクセスする間にルートにアクセスする

void inorder( BTREE__NODE_p_t node )
    if ( node != NULL )
        inorder( node->left )
        visit( node )
        inorder( node->right )

ポストオーダー トラバーサル: サブツリーにアクセスした後にルートにアクセスする 

void postorder( BTREE__NODE_p_t node )
    if ( node != NULL )
        postorder( node->left )
        postorder( node->right )
        visit( node )

明確にするために、アルゴリズムを一般的なものにしたいのですが、nレベルまたは3つだけに適用するなど、ロジックの点で違いが非常に大きくなります。

于 2012-06-10T21:21:15.113 に答える