为什么使用非递归遍历

　　其实这是一个见仁见智的问题。递归还是非递归，不过是两种不同的遍历形式，不存在绝对的优劣，而且一般情况下可以相互补充。我个人选择非递归出于以下几种因素：

　　避免树层次过多导致函数调用堆栈溢出； 避免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;