c - 以深度优先顺序递归遍历一般树

Question

我被要求实现一个递归函数，用于按深度优先顺序遍历一般树(第一个 child ，下一个兄弟符号)和二叉树。

该函数应在上次访问该节点时打印该节点。例如，对于下面的树，节点应按以下顺序打印。 我想我已经完成了二叉树的功能，但我无法完成一般的功能:

这是我的二叉树代码:

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

有人能帮忙吗？

Answer 1

这听起来像是典型的“用二叉树表示的一般树”，有两个指针:第一个 child 和下一个兄弟。我们可以将这棵树画成标准的二叉树，每个 child 都有一个向下的箭头和一个向右的箭头。

我认为您评论中描述的树看起来像这样:

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

您希望在树的每个节点处:

1. 首先打印所有后代，通过处理第一个 child (按照向下箭头)。
2. 然后打印节点的值
3. 然后处理 sibling (按照右箭头)。

将其应用于上面的树，我们得到:

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。

为通用树编写一个新函数(注意 printf 应该使用双引号格式字符串):

void GeneralTreePostOrder (node* root) {
    if (root == NULL)
        return;
    else {
         GeneralTreePostOrder (root->left); // Process children
         printf ("%c", root->key); 
         GeneralTreePostOrder (root->right); // Process siblings
    } 
}