建站
咨詢
售后
建站咨詢
新聞中心
講究套路之前，先來(lái)回答三個(gè)問(wèn)題。
為什么要打印樹形結(jié)構(gòu)
樹形結(jié)構(gòu)是算法里很常見的一種數(shù)據(jù)結(jié)構(gòu)，從二叉樹到多叉樹，還有很多變種。很多涉及到算法的工作，就需要程序員自己手動(dòng)實(shí)現(xiàn)樹形結(jié)構(gòu)，但出于結(jié)構(gòu)本身復(fù)雜性，不太容易做對(duì)，需要一種調(diào)試工具來(lái)檢測(cè)正確性。一般的調(diào)試手段無(wú)非就是加打印，GDB上斷點(diǎn)，寫測(cè)試用例等，但這些局部以及外部的調(diào)試信息對(duì)于數(shù)據(jù)結(jié)構(gòu)的整體把握提供的幫助十分有限，經(jīng)驗(yàn)不足的程序員甚至可能會(huì)迷失在一大片調(diào)試信息的汪洋大海中找不著北。理解算法本身是一回事，自己動(dòng)手是另一回事了，這跟我們理解算法的思維方式有關(guān)——對(duì)于數(shù)據(jù)結(jié)構(gòu)而言，我們的感知是形象化的，比方腦海中自動(dòng)出現(xiàn)一幅圖，動(dòng)態(tài)的插入刪除，每個(gè)節(jié)點(diǎn)是如何變動(dòng)的，平衡的時(shí)候局部是怎么旋轉(zhuǎn)的等等，對(duì)智力正常的人來(lái)說(shuō)不是什么難事。但對(duì)機(jī)器來(lái)說(shuō)，它要面對(duì)的是只是一堆基于狀態(tài)的指令而已，將人的形象思維轉(zhuǎn)化為狀態(tài)機(jī)，本身是一件艱難的工作，因?yàn)槲覀兒茈y感知并存儲(chǔ)這么多狀態(tài)，這就需要工具來(lái)輔助，最好是畫出整個(gè)形狀結(jié)構(gòu)，以直觀地提醒我們哪里出錯(cuò)了，所謂“觀其形，見其義”。
我們知道Linux有個(gè)tree命令用來(lái)打印樹狀目錄列表，可以將某個(gè)目錄下的所有文件和子目錄一覽無(wú)遺，非常直觀，本文可以說(shuō)就是為了實(shí)現(xiàn)這個(gè)效果，并給出源碼實(shí)現(xiàn)。
為什么用深度優(yōu)先遍歷
主要是方便輸出。在終端輸出一般都是從左至右，從上到下，對(duì)于樹形結(jié)構(gòu)來(lái)說(shuō)，前者自然表達(dá)的是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，后者自然表達(dá)的是相鄰分支，深度優(yōu)先遍歷符合輸出次序。
實(shí)際上廣度優(yōu)先遍歷實(shí)現(xiàn)起來(lái)更簡(jiǎn)單，只要在每一層左端建立一個(gè)鏈表頭，將同一層的節(jié)點(diǎn)橫向串聯(lián)起來(lái)，從上到下遍歷鏈表頭數(shù)組就可以了。但考慮以下幾點(diǎn)：
- 我們的屏幕沒(méi)有這么寬，足以容納整棵樹，而且我們更趨向于縱向滾動(dòng)瀏覽；
- 層次關(guān)系很難表示，光實(shí)現(xiàn)對(duì)齊就很麻煩；
- 每個(gè)節(jié)點(diǎn)需要維護(hù)一個(gè)額外next指針，如果這不是數(shù)據(jù)結(jié)構(gòu)本身所需要的成員，對(duì)于存儲(chǔ)空間來(lái)說(shuō)是個(gè)額外的負(fù)擔(dān)。
這也說(shuō)明深度優(yōu)先遍歷第二個(gè)優(yōu)點(diǎn)，它的實(shí)現(xiàn)對(duì)于數(shù)據(jù)結(jié)構(gòu)本身是非侵入式的。
為什么使用非遞歸遍歷
其實(shí)這是一個(gè)見仁見智的問(wèn)題。遞歸還是非遞歸，不過(guò)是兩種不同的遍歷形式，不存在絕對(duì)的優(yōu)劣，而且一般情況下可以相互補(bǔ)充。我個(gè)人選擇非遞歸出于以下幾種因素：
- 避免樹層次過(guò)多導(dǎo)致函數(shù)調(diào)用堆棧溢出；
- 避免C語(yǔ)言函數(shù)調(diào)用開銷；
- 所有狀態(tài)可見可控。
當(dāng)然以上因素并不重要，開心就好。
一切皆套路，不變應(yīng)萬(wàn)變
既然本文講究套路，那么干脆現(xiàn)在就把套路給出來(lái)好了，偽代碼形式：
/* log對(duì)象 */ typedef struct node_backlog { node指針; 回溯點(diǎn)位置（索引）; }; /* Dump */ void dump(tree) { 從根節(jié)點(diǎn)開始迭代; 初始化log堆棧; for (; ;) { if (節(jié)點(diǎn)指針為空) { 從log對(duì)象中獲取回溯點(diǎn)位置; if (不存在，或無(wú)效的回溯點(diǎn)) { 壓?？展?jié)點(diǎn)指針; } else { 壓棧當(dāng)前節(jié)點(diǎn)指針，同時(shí)記錄下一個(gè)回溯點(diǎn)位置; } if (回溯點(diǎn)位置索引為0) { 輸出層次縮進(jìn)、畫路徑，打印節(jié)點(diǎn)內(nèi)容; } 進(jìn)入下一層; } else { if (log堆棧為空) return; 彈出log對(duì)象，獲取最近記錄的節(jié)點(diǎn)指針; } } } 簡(jiǎn)單吧？而且我敢說(shuō)，這個(gè)套路對(duì)于所有樹形結(jié)構(gòu)都是通用的，只要能夠深度遍歷。
不信我給出三個(gè)實(shí)戰(zhàn)例子。
目錄樹或字典樹
代碼在gist。這是個(gè)MIB樹，是管理網(wǎng)絡(luò)節(jié)點(diǎn)（設(shè)備）用的。簡(jiǎn)要地講，它具有兩重特性：
- 節(jié)點(diǎn)之間的層次嵌套關(guān)系，決定了它屬于目錄層次結(jié)構(gòu)；
- 節(jié)點(diǎn)的key具有公共前綴，使得它也類似于（或可用于）字典結(jié)構(gòu)。
我們不需要關(guān)心其CRUD實(shí)現(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--; } } } 代碼不算復(fù)雜，就講幾個(gè)要點(diǎn)
深度優(yōu)先遍歷要利用回溯點(diǎn)，就是走到一個(gè)分支的盡頭后，上溯到原先路過(guò)的某個(gè)位置，從另一個(gè)分支繼續(xù)遍歷，如果回溯到根節(jié)點(diǎn)，就說(shuō)明遍歷結(jié)束了，所以，回溯點(diǎn)是必須要記錄的。問(wèn)題是記錄哪個(gè)位置呢？以二叉樹為例，遍歷了左子樹后，接下來(lái)遍歷的就是右子樹，所以回溯點(diǎn)是右孩子；對(duì)于多叉樹，遍歷第N個(gè)分支后，接下來(lái)要遍歷N+1分支，所以回溯點(diǎn)是N+1；如果遍歷完最后一個(gè)分支，則需要繼續(xù)上溯尋找回溯點(diǎn)了。所以呢，我們就用sub_idx + 1來(lái)記錄回溯點(diǎn)，我們還可以利用這個(gè)屬性做個(gè)分類，值大于等于1時(shí)，回溯點(diǎn)有效，值等于0，回溯點(diǎn)無(wú)效。
關(guān)于log堆棧操作，這里使用了二級(jí)指針的技巧。這個(gè)堆棧十分小巧，所以利用函數(shù)局部變量做存儲(chǔ)也未嘗不可，還有不需要對(duì)外暴露數(shù)據(jù)的好處。那么對(duì)于堆棧指針，就需要傳遞二次指針來(lái)改變它。比如我們看入棧操作：
(*(*top)++) = *nbl; 這是將log對(duì)象拷貝給top指向位置，然后將top指針上移，top和bottom的差值就是堆棧元素的數(shù)目。由于top是二級(jí)指針，所以被賦值的是**top，指針移動(dòng)就是(*top)++。再來(lái)看出棧操作：
return --*top; 先將top下移一個(gè)單位，然后返回所指向的log對(duì)象，也就是*top。
接下來(lái)該深入講解套路了，首先，根節(jié)點(diǎn)設(shè)置成了dummy，這是一個(gè)虛擬節(jié)點(diǎn)，是為了保證最上層只有一個(gè)節(jié)點(diǎn)而使用的編碼技巧，好比tree命令輸出目錄樹總是從當(dāng)前目錄“.”開始。由于第一次進(jìn)入循環(huán)，log堆棧為空，不存在所謂回溯點(diǎn)，我們將回溯位置索引設(shè)為0，這有兩重含義，一來(lái)表示該回溯點(diǎn)無(wú)效或不存在，二來(lái)既然沒(méi)有回溯，那么接下來(lái)就從當(dāng)前節(jié)點(diǎn)的第一個(gè)分支開始遍歷。
然后我們將遍歷過(guò)的節(jié)點(diǎn)壓棧，這里也是有區(qū)分的：如果當(dāng)前是葉子節(jié)點(diǎn)，或者所有分支都遍歷完了，那么應(yīng)該繼續(xù)上溯去尋找回溯點(diǎn)，我們就將回溯點(diǎn)設(shè)為無(wú)效后壓棧；否則就將當(dāng)前節(jié)點(diǎn)設(shè)為回溯點(diǎn)，并記錄位置索引后壓棧。
畫線輸出部分稍后講。我們根據(jù)前面獲取的索引sub_idx進(jìn)入下一層，直到觸底回溯，這時(shí)從log堆棧彈出回溯點(diǎn)，pop有三種情況：由于第一個(gè)壓棧為根節(jié)點(diǎn)，堆棧為空表示回溯到原點(diǎn)，也就標(biāo)志著整個(gè)遍歷結(jié)束，退出循環(huán)；否則查看回溯點(diǎn)是否為NULL，如果空如前所述繼續(xù)上溯；如果存在有效回溯點(diǎn)，則將回溯位置索引取出，繼續(xù)下一輪遍歷循環(huán)。
最后講終端輸出。前面說(shuō)過(guò)每一行從左至右的輸出的是樹的層次遍歷，其實(shí)就是遍歷log堆棧；換行輸出就是樹的分支遍歷，就是每一輪循環(huán)。輸出內(nèi)容主要是三個(gè)符號(hào)：縮進(jìn)、分支和節(jié)點(diǎn)內(nèi)容。我們作如下策略：
- 縮進(jìn)：當(dāng)堆棧里回溯點(diǎn)無(wú)效，則不存在分支，打印空格，八個(gè)字符對(duì)齊；
- 分支：當(dāng)堆棧里回溯點(diǎn)有效，表示存在分支，打印“|”和空格，八個(gè)字符對(duì)齊；
- 節(jié)點(diǎn)：當(dāng)堆棧遍歷到最后一個(gè)元素，表示后面將要輸出節(jié)點(diǎn)內(nèi)容，打印“+---”，八個(gè)字符對(duì)齊，后面跟節(jié)點(diǎn)內(nèi)容。
當(dāng)然你也可以自定義打印策略以便輸出更美觀。好了，說(shuō)了一大堆，看效果吧，運(yùn)行程序，一目了然。
B+樹
代碼在此。B+樹是關(guān)系數(shù)據(jù)庫(kù)常用的底層數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)起來(lái)相當(dāng)恐怖，所幸本文不講這些，這里只是將B+樹作為多叉樹示范如何打印，特別是葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)本身定義不同的情況下。從輸出實(shí)現(xiàn)上我們發(fā)現(xiàn)，log對(duì)象記錄的只是節(jié)點(diǎn)的指針和回溯位置，同數(shù)據(jù)節(jié)點(diǎn)本身沒(méi)有關(guān)系。我們幾乎可以原封不動(dòng)地把上面的代碼搬過(guò)來(lái)，運(yùn)行效果如下：
從形狀上可以看到B+樹的真實(shí)數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)，而且整棵樹是平衡的。
紅黑樹（二叉樹）
代碼在此。理解了多叉樹的實(shí)現(xiàn)，二叉樹不過(guò)是一種特殊簡(jiǎn)化形式罷了。本文挑選了紅黑樹為代表，代碼自己懶得寫了，直接拿Nginx源碼。
觀察得出，二叉樹關(guān)于回溯點(diǎn)的位置其實(shí)只有右邊分支，也就是說(shuō)回溯位置索引只有一個(gè)值，就是1。這樣一來(lái)我們可以做個(gè)簡(jiǎn)化，將左分支索引設(shè)為0表示無(wú)效回溯位置，右分支索引設(shè)為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)對(duì)于二叉樹，右孩子在左孩子的下一行打印，視覺上有點(diǎn)不習(xí)慣是嗎？還好我貼心地將LEFT_INDEX和RIGHT_INDEX交換了一下次序，右孩子就先于左孩子輸出了，這樣一來(lái)你就可以歪著腦袋直觀地看二叉樹了（笑），同時(shí)我們還知道，“翻轉(zhuǎn)”一棵二叉樹是多么容易（笑）。
工欲善其事，必先利其器。學(xué)會(huì)了樹形結(jié)構(gòu)打印工具，針對(duì)這樣的數(shù)據(jù)結(jié)構(gòu)，只有你寫不了的，沒(méi)有你寫不對(duì)的。最后給出一個(gè)思考題：如何用遞歸形式實(shí)現(xiàn)打印樹形結(jié)構(gòu)？（提示：利用參數(shù)傳遞）
參考源碼
目錄樹 B+樹 紅黑樹
名稱欄目：100行C代碼終端打印樹形結(jié)構(gòu)
本文URL：http://www.dlmjj.cn/article/dphopjp.html
