如何实现二叉树的终极版遍历？

本文共计403个文字，预计阅读时间需要2分钟。

对二叉树的遍历，最经典的就是递归遍历。对于二叉树的非递归遍历，尽管知道一些，但不太熟悉。尤其是后继的非递归遍历实现，比较麻烦。上网查询了一下，果然如此。

对于二叉树的遍历，最熟悉的就是递归遍历了，对二叉树的非递归遍历大致知道一些，但是不太熟悉，尤其是后续非递归遍历的实现，一直比较懵逼，于是上网查询了一下，果然大神无处不在，那个后序遍历的双栈法，简直让人拍案叫绝，下面总结下。

1、先序遍历

先序遍历即顺序为：根节点->左节点->右节点

递归版:

void xianxu(struct node *root)//先序遍历 { struct node *p; p = root; if(p != NULL) { printf("%d", root->data); xianxu(root->lc); xianxu(root->rc); } }

2、中序遍历

中序遍历的顺序是：左节点、根节点、右节点

递归版：

void zhongxu(struct node *root) { struct node *p; p = root; if(p != NULL) { zhongxu(root->lc); printf("%d", root->data); zhongxu(root->rc); } }

3、后序遍历

后序遍历的顺序是：左节点、右节点、根节点

递归版：

void houxu(struct node *root) { struct node *p; p = root; if(p != NULL) { houxu(root->lc); houxu(root->rc); printf("%d", root->data); } }