详解二叉树的递归遍历与非递归遍历

二叉树的遍历

所谓二叉树的遍历，是指按某条搜索路径访问树中的每个节点，使得每个节点均被访问一次，而且仅被访问一次。

遍历二叉树需要决定对根节点N、左子树L、右子树R的访问顺序（按照先遍历左子树在遍历右子树的原则），常见的遍历次序有先序（NLR）、中序（LNR）、后序（LRN）三种遍历算法，这也是最常见的二叉树遍历算法。

其中的“序”实际上就是根节点的访问时机。

1. 二叉树的数据结构

typedef struct BTNode{

int data; //保存节点中的值

struct BTNode *lchild; //左孩子指针

struct BTNode *rchild; //右孩子指针

}BTNode，*BiTree；

这里我使用的比较适合基础学者的二叉树的存储结构，不同的存储结构，实现二叉树操作的算法也会不同，因此要根据实际应用场合（树的形态和需要进行的运算）来选择合适的存储结构。

不说废话了，哈哈肯定把你急死了！

2.二叉树的递归遍历

1. 先序遍历

先序遍历（PreOrder）的操作如下：

①首先若二叉树为空，则什么也不做；否则，

访问根节点；
先序遍历左子树；
先序遍历右子树。

对应的递归算法如下：

void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);        //访问跟结点
        PreOrder(T->lchild);    //访问左子树
        PreOrder(T->rchild);    //访问右子树
    }
}

这里举一个例子做说明吧（后面都是使用这个例子），例子二叉树如下：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70

这样一来先序遍历所得到的节点序列为1 2 4 6 3 5.

2. 中序遍历

中序遍历（InOrder）的操作如下：

①首先若二叉树为空，则什么也不做；否则，

中序遍历左子树；
访问根节点；
中序遍历右子树。

对应的递归算法如下：

void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);//递归遍历左子树
        visit(T);//访问根结点
        InOrder(T->lchild);//递归遍历右子树
    }
}

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 3

这样一来中序遍历所得到的节点序列为2 6 4 1 3 5.

3. 后序遍历

后序遍历（PostOrder）的操作如下：

①首先若二叉树为空，则什么也不做；否则，

后序遍历左子树；
后序遍历右子树；
访问根节点。

对应的递归算法如下：

void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);//递归遍历左子树
        PostOrder(T->rchild);//递归遍历左子树
        visit(T);            //访问根结点
    }
}