篇一：二叉树-遍历终极版

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

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