講究套路之前，先來回答三個問題。

為什么要打印樹形結(jié)構

樹形結(jié)構是算法里很常見的一種數(shù)據(jù)結(jié)構，從二叉樹到多叉樹，還有很多變種。很多涉及到算法的工作，就需要程序員自己手動實現(xiàn)樹形結(jié)構，但出于結(jié)構本身復雜性，不太容易做對，需要一種調(diào)試工具來檢測正確性。一般的調(diào)試手段無非就是加打印，GDB上斷點，寫測試用例等，但這些局部以及外部的調(diào)試信息對于數(shù)據(jù)結(jié)構的整體把握提供的幫助十分有限，經(jīng)驗不足的程序員甚至可能會迷失在一大片調(diào)試信息的汪洋大海中找不著北。理解算法本身是一回事，自己動手是另一回事了，這跟我們理解算法的思維方式有關——對于數(shù)據(jù)結(jié)構而言，我們的感知是形象化的，比方腦海中自動出現(xiàn)一幅圖，動態(tài)的插入刪除，每個節(jié)點是如何變動的，平衡的時候局部是怎么旋轉(zhuǎn)的等等，對智力正常的人來說不是什么難事。但對機器來說，它要面對的是只是一堆基于狀態(tài)的指令而已，將人的形象思維轉(zhuǎn)化為狀態(tài)機，本身是一件艱難的工作，因為我們很難感知并存儲這么多狀態(tài)，這就需要工具來輔助，最好是畫出整個形狀結(jié)構，以直觀地提醒我們哪里出錯了，所謂“觀其形，見其義”。

我們知道Linux有個tree命令用來打印樹狀目錄列表，可以將某個目錄下的所有文件和子目錄一覽無遺，非常直觀，本文可以說就是為了實現(xiàn)這個效果，并給出源碼實現(xiàn)。

為什么用深度優(yōu)先遍歷

主要是方便輸出。在終端輸出一般都是從左至右，從上到下，對于樹形結(jié)構來說，前者自然表達的是從根節(jié)點到葉子節(jié)點，后者自然表達的是相鄰分支，深度優(yōu)先遍歷符合輸出次序。

實際上廣度優(yōu)先遍歷實現(xiàn)起來更簡單，只要在每一層左端建立一個鏈表頭，將同一層的節(jié)點橫向串聯(lián)起來，從上到下遍歷鏈表頭數(shù)組就可以了。但考慮以下幾點：

• 我們的屏幕沒有這么寬，足以容納整棵樹，而且我們更趨向于縱向滾動瀏覽；
• 層次關系很難表示，光實現(xiàn)對齊就很麻煩；
• 每個節(jié)點需要維護一個額外next指針，如果這不是數(shù)據(jù)結(jié)構本身所需要的成員，對于存儲空間來說是個額外的負擔。

這也說明深度優(yōu)先遍歷第二個優(yōu)點，它的實現(xiàn)對于數(shù)據(jù)結(jié)構本身是非侵入式的。

為什么使用非遞歸遍歷

其實這是一個見仁見智的問題。遞歸還是非遞歸，不過是兩種不同的遍歷形式，不存在絕對的優(yōu)劣，而且一般情況下可以相互補充。我個人選擇非遞歸出于以下幾種因素：

• 避免樹層次過多導致函數(shù)調(diào)用堆棧溢出；
• 避免C語言函數(shù)調(diào)用開銷；
• 所有狀態(tài)可見可控。

當然以上因素并不重要，開心就好。

一切皆套路，不變應萬變

既然本文講究套路，那么干脆現(xiàn)在就把套路給出來好了，偽代碼形式：

/* log對象 */ typedef struct node_backlog {     node指針;     回溯點位置（索引）; };  /* Dump */ void dump(tree) {     從根節(jié)點開始迭代;     初始化log堆棧;     for (; ;) {         if (節(jié)點指針為空) {             從log對象中獲取回溯點位置;             if (不存在，或無效的回溯點) {                 壓?？展?jié)點指針;             } else {                 壓棧當前節(jié)點指針，同時記錄下一個回溯點位置;             }             if (回溯點位置索引為0) {                 輸出層次縮進、畫路徑，打印節(jié)點內(nèi)容;             }             進入下一層;         } else {             if (log堆棧為空) return;             彈出log對象，獲取最近記錄的節(jié)點指針;         }     } } 

簡單吧？而且我敢說，這個套路對于所有樹形結(jié)構都是通用的，只要能夠深度遍歷。

不信我給出三個實戰(zhàn)例子。

目錄樹或字典樹

代碼在gist。這是個MIB樹，是管理網(wǎng)絡節(jié)點（設備）用的。簡要地講，它具有兩重特性：

• 節(jié)點之間的層次嵌套關系，決定了它屬于目錄層次結(jié)構；
• 節(jié)點的key具有公共前綴，使得它也類似于（或可用于）字典結(jié)構。

我們不需要關心其CRUD實現(xiàn)，只需要知道有一棵現(xiàn)成的目錄樹或者字典樹，我們?nèi)绾卧诮K端輸出它的形狀。

#define OID_MAX_LEN  64  struct node_backlog {     /* node to be backlogged */     struct mib_node *node;     /* the backtrack point, next to the orignal sub-index of the node, valid when >= 1, invalid == 0 */     int next_sub_idx; };  static inline void nbl_push(struct node_backlog *nbl, struct node_backlog **top, struct node_backlog **bottom) {     if (*top - *bottom< OID_MAX_LEN) {         (*(*top)++) = *nbl;     } }  static inline struct node_backlog * nbl_pop(struct node_backlog **top, struct node_backlog **bottom) {     return *top > *bottom? --*top : NULL; }  void mib_tree_dump(void) {     int level = 0;     oid_t id = 0;     struct mib_node *node = *dummy_root;      struct node_backlog nbl, *p_nbl = NULL;     struct node_backlog *top, *bottom, nbl_stack[OID_MAX_LEN];      top = bottom = nbl_stack;      for (; ;) {         if (node != NULL) {             /* Fetch the pop-up backlogged node's sub-id. If not backlogged, set 0. */             int sub_idx = p_nbl != NULL ? p_nbl->next_sub_idx : 0;             /* Reset backlog for the node has gone deep down */             p_nbl = NULL;              /* Backlog the node */             if (is_leaf(node) || sub_idx + 1 >= node->sub_id_cnt) {                 nbl.node = NULL;                 nbl.next_sub_idx = 0;             } else {                 nbl.node = node;                 nbl.next_sub_idx = sub_idx + 1;             }             nbl_push(*nbl, *top, *bottom);             level++;              /* Draw lines as long as sub_idx is the first one */             if (sub_idx == 0) {                 int i;                 for (i = 1; i < level; i++) {                     if (i == level - 1) {                         printf("%-8s", "+-------");                     } else {                         if (nbl_stack[i - 1].node != NULL) {                             printf("%-8s", "|");                         } else {                             printf("%-8s", " ");                         }                     }                 }                 printf("%s(%d)\n", node->name, id);             }              /* Go deep down */             id = node->sub_id[sub_idx];             node = node->sub_ptr[sub_idx];         } else {             p_nbl = nbl_pop(*top, *bottom);             if (p_nbl == NULL) {                 /* End of traversal */                 break;             }             node = p_nbl->node;             level--;         }     } } 

代碼不算復雜，就講幾個要點

深度優(yōu)先遍歷要利用回溯點，就是走到一個分支的盡頭后，上溯到原先路過的某個位置，從另一個分支繼續(xù)遍歷，如果回溯到根節(jié)點，就說明遍歷結(jié)束了，所以，回溯點是必須要記錄的。問題是記錄哪個位置呢？以二叉樹為例，遍歷了左子樹后，接下來遍歷的就是右子樹，所以回溯點是右孩子；對于多叉樹，遍歷第N個分支后，接下來要遍歷N+1分支，所以回溯點是N+1；如果遍歷完最后一個分支，則需要繼續(xù)上溯尋找回溯點了。所以呢，我們就用sub_idx + 1來記錄回溯點，我們還可以利用這個屬性做個分類，值大于等于1時，回溯點有效，值等于0，回溯點無效。

關于log堆棧操作，這里使用了二級指針的技巧。這個堆棧十分小巧，所以利用函數(shù)局部變量做存儲也未嘗不可，還有不需要對外暴露數(shù)據(jù)的好處。那么對于堆棧指針，就需要傳遞二次指針來改變它。比如我們看入棧操作：

(*(*top)++) = *nbl; 

這是將log對象拷貝給top指向位置，然后將top指針上移，top和bottom的差值就是堆棧元素的數(shù)目。由于top是二級指針，所以被賦值的是**top，指針移動就是(*top)++。再來看出棧操作：

return --*top; 

先將top下移一個單位，然后返回所指向的log對象，也就是*top。

接下來該深入講解套路了，首先，根節(jié)點設置成了dummy，這是一個虛擬節(jié)點，是為了保證最上層只有一個節(jié)點而使用的編碼技巧，好比tree命令輸出目錄樹總是從當前目錄“.”開始。由于第一次進入循環(huán)，log堆棧為空，不存在所謂回溯點，我們將回溯位置索引設為0，這有兩重含義，一來表示該回溯點無效或不存在，二來既然沒有回溯，那么接下來就從當前節(jié)點的第一個分支開始遍歷。

然后我們將遍歷過的節(jié)點壓棧，這里也是有區(qū)分的：如果當前是葉子節(jié)點，或者所有分支都遍歷完了，那么應該繼續(xù)上溯去尋找回溯點，我們就將回溯點設為無效后壓棧；否則就將當前節(jié)點設為回溯點，并記錄位置索引后壓棧。

畫線輸出部分稍后講。我們根據(jù)前面獲取的索引sub_idx進入下一層，直到觸底回溯，這時從log堆棧彈出回溯點，pop有三種情況：由于第一個壓棧為根節(jié)點，堆棧為空表示回溯到原點，也就標志著整個遍歷結(jié)束，退出循環(huán)；否則查看回溯點是否為NULL，如果空如前所述繼續(xù)上溯；如果存在有效回溯點，則將回溯位置索引取出，繼續(xù)下一輪遍歷循環(huán)。

最后講終端輸出。前面說過每一行從左至右的輸出的是樹的層次遍歷，其實就是遍歷log堆棧；換行輸出就是樹的分支遍歷，就是每一輪循環(huán)。輸出內(nèi)容主要是三個符號：縮進、分支和節(jié)點內(nèi)容。我們作如下策略：

• 縮進：當堆棧里回溯點無效，則不存在分支，打印空格，八個字符對齊；
• 分支：當堆棧里回溯點有效，表示存在分支，打印“|”和空格，八個字符對齊；
• 節(jié)點：當堆棧遍歷到最后一個元素，表示后面將要輸出節(jié)點內(nèi)容，打印“+---”，八個字符對齊，后面跟節(jié)點內(nèi)容。

當然你也可以自定義打印策略以便輸出更美觀。好了，說了一大堆，看效果吧，運行程序，一目了然。

<center></center>

B+樹

代碼在此。B+樹是關系數(shù)據(jù)庫常用的底層數(shù)據(jù)結(jié)構，實現(xiàn)起來相當恐怖，所幸本文不講這些，這里只是將B+樹作為多叉樹示范如何打印，特別是葉子節(jié)點和非葉子節(jié)點本身定義不同的情況下。從輸出實現(xiàn)上我們發(fā)現(xiàn)，log對象記錄的只是節(jié)點的指針和回溯位置，同數(shù)據(jù)節(jié)點本身沒有關系。我們幾乎可以原封不動地把上面的代碼搬過來，運行效果如下：

</center> </center>

從形狀上可以看到B+樹的真實數(shù)據(jù)都存儲在葉子節(jié)點，而且整棵樹是平衡的。

紅黑樹（二叉樹）

代碼在此。理解了多叉樹的實現(xiàn)，二叉樹不過是一種特殊簡化形式罷了。本文挑選了紅黑樹為代表，代碼自己懶得寫了，直接拿Nginx源碼。

觀察得出，二叉樹關于回溯點的位置其實只有右邊分支，也就是說回溯位置索引只有一個值，就是1。這樣一來我們可以做個簡化，將左分支索引設為0表示無效回溯位置，右分支索引設為1表示有效回溯位置，代碼可以這樣寫：

#define RBTREE_MAX_LEVEL   64 #define RBTREE_LEFT_INDEX  0 #define RBTREE_RIGHT_INDEX 1  void rbtree_dump(struct rbtree *tree) {     int level = 0;     struct rbnode *node = tree->root, *sentinel = tree->sentinel;     struct node_backlog nbl, *p_nbl = NULL;     struct node_backlog *top, *bottom, nbl_stack[RBTREE_MAX_LEVEL];      top = bottom = nbl_stack;      for (; ;) {         if (node != sentinel) {             /* Fetch the pop-up backlogged node's sub-id. If not backlogged, set 0. */             int sub_index = p_nbl != NULL ? p_nbl->next_sub_idx : RBTREE_LEFT_INDEX;             /* backlog should be reset since node has gone deep down */             p_nbl = NULL;              /* Backlog the node */             if (is_leaf(node, sentinel) || sub_index == RBTREE_RIGHT_INDEX) {                 nbl.node = sentinel;                 nbl.next_sub_idx = RBTREE_LEFT_INDEX;             } else {                 nbl.node = node;                 nbl.next_sub_idx = RBTREE_RIGHT_INDEX;             }             nbl_push(&nbl, &top, &bottom);             level++;              /* Draw lines as long as sub_idx is the first one */             if (sub_index == RBTREE_LEFT_INDEX) {                 /* Print intent, branch and node content... */             }              /* Move down according to sub_idx */             node = sub_index == RBTREE_LEFT_INDEX ? node->left : node->right;         } else {             /* Pop up the node backlog... */         }     } } 

讓我們看一看輸出效果……等等，我們發(fā)現(xiàn)對于二叉樹，右孩子在左孩子的下一行打印，視覺上有點不習慣是嗎？還好我貼心地將LEFT_INDEX和RIGHT_INDEX交換了一下次序，右孩子就先于左孩子輸出了，這樣一來你就可以歪著腦袋直觀地看二叉樹了（笑），同時我們還知道，“翻轉(zhuǎn)”一棵二叉樹是多么容易（笑）。

<center></center>

工欲善其事，必先利其器。學會了樹形結(jié)構打印工具，針對這樣的數(shù)據(jù)結(jié)構，只有你寫不了的，沒有你寫不對的。最后給出一個思考題：如何用遞歸形式實現(xiàn)打印樹形結(jié)構？（提示：利用參數(shù)傳遞）

參考源碼

目錄樹 B+樹 紅黑樹