為什么使用非遞歸遍歷

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

　　避免樹層次過多導致函數調用堆棧溢出； 避免C語言函數調用開銷； 所有狀態可見可控。

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

　　一切皆套路，不變應萬變

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

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

　　簡單吧無限層次樹形筆記本 ？而且我敢說，這個套路對于所有樹形結構都是通用的，只要能夠深度遍歷。

　　不信我給出三個實戰例子。

　　目錄樹或字典樹

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

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

　　我們不需要關心其CRUD實現，只需要知道有一棵現成的目錄樹或者字典樹，我們如何在終端輸出它的形狀。

　　#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--; } } }

　　代碼不算復雜無限層次樹形筆記本，就講幾個要點

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

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

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

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

　　return --*top;