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

我被要求实现一个递归函数来遍历一般树（第一个子，下一个同级符号）和二叉树。
该函数应在上次访问该节点时打印该节点。例如，对于下面的树，应按以下顺序打印节点。
我想我已经完成了二叉树的功能，但是我不能完成一般的功能：
这是我的二叉树代码：

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

有人能帮忙吗？

最佳答案

听起来像是一个典型的“一般树，表示为二叉树”，有两个指针：第一个子树和下一个兄弟树。我们可以将树绘制为标准的二叉树，每个子树都有一个下箭头和一个右箭头。
我认为你在评论中描述的树是这样的：

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

您希望在树的每个节点上：
首先打印所有子体，方法是处理第一个子体（跟随下箭头）。
然后打印节点的值
然后处理同级（跟随右箭头）。
把这个应用到上面的树上，我们得到：

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。
为常规树编写新函数（N.B.printf应使用双引号格式字符串）：

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

关于c - 以深度优先顺序递归遍历一般树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13671959/