作者：解学武

链式存储结构存储的二叉树，对树中结点进行逐个遍历时，由于是非线性结构，需要找到一种合适的方式遍历树中的每个结点。

递归思想遍历二叉树

之前讲过，树是由根结点和子树部分构建的，对于每一棵树来说，都可以分为 3 部分：左子树、根结点和右子树。所以，可以采用递归的思想依次遍历每个结点。

根据访问结点时机的不同，分为三种遍历方式：

• 先访问根结点，再遍历左右子树，称为“先序遍历”；
• 遍历左子树，之后访问根结点，然后遍历右子树，称为“中序遍历”；
• 遍历完左右子树，再访问根结点，称为“后序遍历”。

三种方式唯一的不同就是访问结点时机的不同，给出一个二叉树，首先需要搞清楚三种遍历方式下访问结点的顺序。
图2 中，箭头线条的走势为遍历结点的过程：

先序遍历是只要线条走到该结点的左方位置时，就操作该结点。所以操作结点的顺序为：
中序遍历是当线条越过结点的左子树，到达该结点的正下方时，才操作该结点。所以操作结点的顺序为：
后序遍历是线条完全走过结点的左右子树，到达该结点的右方范围时，就开始操作该结点。所以操作结点的顺序为：

三种遍历方式的完整代码实现

#include <stdio.h>
#include <string.h>
#define TElemType int
//构造结点的结构体
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
  
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}

//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){
    printf("%d ",elem->data);
}
//先序遍历
void PreOrderTraverse(BiTree T){
    if (T) {
        displayElem(T);//调用操作结点数据的函数方法
        PreOrderTraverse(T->lchild);//访问该结点的左孩子
        PreOrderTraverse(T->rchild);//访问该结点的右孩子
    }
    //如果结点为空，返回上一层
    return;
}
//中序遍历
void INOrderTraverse(BiTree T){
    if (T) {
        INOrderTraverse(T->lchild);//遍历左孩子
        displayElem(T);//调用操作结点数据的函数方法
        INOrderTraverse(T->rchild);//遍历右孩子
    }
    //如果结点为空，返回上一层
    return;
}
//后序遍历
void PostOrderTraverse(BiTree T){
    if (T) {
        PostOrderTraverse(T->lchild);//遍历左孩子
        PostOrderTraverse(T->rchild);//遍历右孩子
        displayElem(T);//调用操作结点数据的函数方法
    }
    //如果结点为空，返回上一层
    return;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("前序遍历: \n");
    PreOrderTraverse(Tree);
    printf("\n中序遍历算法: \n");
    INOrderTraverse(Tree);
    printf("\n后序遍历: \n");
    PostOrderTraverse(Tree);
}

运行结果：

总结

由于二叉树就是由根结点和左右子树构成的，所以很容易想到使用递归的思想。而递归算法的低层实现实际上使用的是栈的数据结构，所以二叉树的先序、中序和后序遍历同样可以使用非递归的算法实现。

非递归算法的具体实现可以查看下一节的内容。

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。