以深度優先的順序遞歸遍歷一般樹

Question

我被要求實現遍歷一般樹（第一個孩子，下一個兄弟符號）和二進制樹的深度優先順序的遞歸函數。

函數應該在節點上次訪問它時打印節點。例如，對於下面的樹，節點應按以下順序打印。 我想，我也做了功能二叉樹，但我不能這樣做，一般一個：

這裏是我的二叉樹代碼：

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

誰能幫助？

Answer 1

這聽起來像是一個典型的「二叉樹表示的一般樹」，有兩個指針：第一個孩子和下一個兄弟姐妹。我們可以將樹繪製爲標準的二叉樹，每個孩子都有一個向下的前導箭頭和一個向右的前導箭頭。

我想在您的評論中描述的樹是這個樣子：

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。

編寫一個新的功能，對於一般樹（注：printf應該使用雙引號的格式字符串）：

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