二叉树遍历原理

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

这里有两个关键词：访问和次序。

二叉树遍历方法

二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为四种：

前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如下图所示，遍历的顺序为：ABDGH-CEIF。

image-20200505135509292

中序遍历

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如下图所示，遍历的顺序为：GDHBAE-ICF

image-20200505140905627

后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如下图所示，遍历的顺序为：GHDBIEFCA。

image-20200505141053542

层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如下图所示，遍历的顺序为：ABCDEFGHI。

image-20200505141148660

遍历算法

前序遍历

二叉树的定义是用递归的方式，所以，实现遍历算法也可以采用递归，而且极其简洁明了。先来看看二叉树的前序遍历算法。代码如下：

/* 二叉树的前序遍历递归算法 */
void PreOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    /* 显示结点数据，可以更改为其他对结点操作 */
    printf("%c", T->data);          
    /* 再先序遍历左子树 */
    PreOrderTraverse(T->lchild);    
    /* 最后先序遍历右子树 */
    PreOrderTraverse(T->rchild);    
}

假设我们现在有如图这样一棵二叉树T。这树已经用二叉链表结构存储在内存当中。

image-20200505142125526

那么当调用PreOrderTraverse(T)函数时，我们来看看程序是如何运行的。

1．调用PreOrderTraverse(T)，T根结点不为null，所以执行printf，打印字母A，如下图所示。

image-20200505142205451

2．调用PreOrderTraverse(T->lchild);访问了A结点的左孩子，不为null，执行printf显示字母B，如下图所示。

image-20200505142259653

3．此时再次递归调用PreOrderTraverse(T->lchild);访问了B结点的左孩子，执行printf显示字母D，如下图所示。

image-20200505142335624

4．再次递归调用PreOrderTraverse(T->lchild);访问了D结点的左孩子，执行printf显示字母H，如下图所示。

image-20200505142406346

5．再次递归调用PreOrderTraverse(T->lchild);访问了H结点的左孩子，此时因为H结点无左孩子，所以T==null，返回此函数，此时递归调用PreOrderTraverse(T->rchild);访问了H结点的右孩子，printf显示字母K，如下图所示。

image-20200505142436063

6．再次递归调用PreOrderTraverse(T->lchild);访问了K结点的左孩子，K结点无左孩子，返回，调用PreOrderTra-verse(T->rchild);访问了K结点的右孩子，也是null，返回。于是此函数执行完毕，返回到上一级递归的函数（即打印H结点时的函数），也执行完毕，返回到打印结点D时的函数，调用PreOrderTraverse(T->rchild);访问了D结点的右孩子，不存在，返回到B结点，调用PreOrderTra-verse(T->rchild);找到了结点E，打印字母E，如下图所示。

image-20200505142618231

7．由于结点E没有左右孩子，返回打印结点B时的递归函数，递归执行完毕，返回到最初的PreOrderTraverse，调用PreOrderTra-verse(T->rchild);访问结点A的右孩子，打印字母C，如下图所示。

image-20200505142648325

8．之后类似前面的递归调用，依次继续打印F、I、G、J，步骤略。

综上，前序遍历这棵二叉树的节点顺序是：AB-DHKECFIGJ。

中序遍历

/* 二叉树的中序遍历递归算法 */
void InOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    /* 中序遍历左子树 */
    InOrderTraverse(T->lchild);    
    /* 显示结点数据，可以更改为其他对结点操作 */
    printf("%c", T->data);         
    /* 最后中序遍历右子树 */
    InOrderTraverse(T->rchild);    
}

换句话说，它等于是把调用左孩子的递归函数提前了，就这么简单。我们来看看当调用InOrder-Traverse(T)函数时，程序是如何运行的。

1．调用InOrderTraverse(T)，T的根结点不为null，于是调用InOrderTraverse(T->lchild);访问结点B。当前指针不为null，继续调用InOrderTraverse(T->lchild);访问结点D。不为null，继续调用InOrderTraverse(T->lchild);访问结点H。继续调用InOrderTraverse(T->lchild);访问结点H的左孩子，发现当前指针为null，于是返回。打印当前结点H，如下图所示。

image-20200505143604527

2．然后调用InOrderTraverse(T->rchild);访问结点H的右孩子K，因结点K无左孩子，所以打印K，如下图所示。

image-20200505143642203

3．因为结点K没有右孩子，所以返回。打印结点H函数执行完毕，返回。打印字母D，如下图所示。

image-20200505143707975

4．结点D无右孩子，此函数执行完毕，返回。打印字母B，如下图所示。

image-20200505143738162

5．调用InOrderTraverse(T->rchild);访问结点B的右孩子E，因结点E无左孩子，所以打印E，如下图所示。

image-20200505143915885

6．结点E无右孩子，返回。结点B的递归函数执行完毕，返回到了最初我们调用In-OrderTraverse的地方，打印字母A，如下图所示。

image-20200505144302914

7．再调用InOrderTraverse(T->rchild);访问结点A的右孩子C，再递归访问结点C的左孩子F，结点F的左孩子I。因为I无左孩子，打印I，之后分别打印F、C、G、J。步骤省略。

综上，中序遍历这棵二叉树的节点顺序是：HKDBEAIFCGJ。

后序遍历

/* 二叉树的后序遍历递归算法 */
void PostOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    /* 先后序遍历左子树 */
    PostOrderTraverse(T->lchild);    
    /* 再后序遍历右子树 */
    PostOrderTraverse(T->rchild);    
    /* 显示结点数据，可以更改为其他对结点操作 */
    printf("%c", T->data);           
}

如下图所示，后序遍历是先递归左子树，由根结点A→B→D→H，结点H无左孩子，再查看结点H的右孩子K，因为结点K无左右孩子，所以打印K，返回。

image-20200505144528020

最终，后序遍历的结点的顺序就是：KHDEB-IFJGCA。