-1

如果我有一棵树，如下所示：

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

我有三个问题：

  • 如何遍历这棵树，以便首先打印级别 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

我正在浏览维基百科上的树遍历，并记得我曾经在一次采访中被问到的一个老问题。我相信问题是上述三个中的一个（很可能是第一个或第二个）。

4

1 回答 1

0

前序遍历：在子树之前访问根 

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 回答