【C语言 数据结构】二叉树的遍历

文章目录

• 遍历二叉树
• • 先序遍历
  • • 递归先序遍历二叉树
    • 非递归先序遍历二叉树
  • 中序遍历
  • • 递归中序遍历二叉树
    • 非递归中序遍历二叉树
  • 后序遍历
  • • 递归后序遍历二叉树
    • 非递归后序遍历二叉树
  • 层次遍历
• 线索二叉树
• • • 层次遍历顺序二叉树
    • 层次遍历链式二叉树

遍历二叉树

先序遍历

所谓先序遍历二叉树，指的是从根结点出发，按照以下步骤访问二叉树的每个结点：

• 访问当前结点；

• 进入当前结点的左子树，以同样的步骤遍历左子树中的结点；

• 遍历完当前结点的左子树后，再进入它的右子树，以同样的步骤遍历右子树中的结点；

先序遍历这棵二叉树的过程是：

访问根节点 1；进入 1 的左子树，执行同样的步骤：访问结点 2；进入 2 的左子树，执行同样的步骤：访问结点 4；结点 4 没有左子树；结点 4 没有右子树；进入 2 的右子树，执行同样的步骤：访问结点 5；结点 5 没有左子树；结点 5 没有右子树；进入 1 的右子树，执行同样的步骤：访问结点 3；进入 3 的左子树，执行同样的步骤：访问结点 6；结点 6 没有左子树；结点 6 没有右子树；进入 3 的右子树，执行同样的步骤：访问结点 7；结点 7 没有左子树；结点 7 没有右子树； 

1 2 4 5 3 6 7

递归先序遍历二叉树

观察整个先序遍历二叉树的过程会发现，访问每个结点的过程都是相同的，可以用递归的方式实现二叉树的先序遍历。

对于顺序表存储的二叉树，递归实现先序遍历二叉树的 C 语言代码为：

void PreOrderTraverse(BiTree T, int p_node) {//根节点的值不为 0，证明二叉树存在if (T[p_node]) {printf("%d ", T[p_node]);//先序遍历左子树if ((2 * p_node + 1 < NODENUM) && (T[2 * p_node + 1] != 0)) {PreOrderTraverse(T, 2 * p_node + 1);}//最后先序遍历右子树if ((2 * p_node + 2 < NODENUM) && (T[2 * p_node + 2] != 0)) {PreOrderTraverse(T, 2 * p_node + 2);}}}

对于链表存储的二叉树，递归实现先序遍历二叉树的 C 语言代码为

void PreOrderTraverse(BiTree T) {//如果二叉树存在，则遍历二叉树if (T) {printf("%d",T->data); //调用操作结点数据的函数方法PreOrderTraverse(T->lchild);//访问该结点的左孩子PreOrderTraverse(T->rchild);//访问该结点的右孩子}}

非递归先序遍历二叉树

我们知道，递归的底层实现借助的是栈存储结构。所谓先序遍历二叉树的非递归方式，其实就是自己创建一个栈，模拟递归的过程实现二叉树的先序遍历。

对于顺序表存储的二叉树，非递归实现先序遍历二叉树的 C 语言代码为：

//全局变量，记录栈顶的位置int top = -1;//前序遍历使用的入栈函数void push(BiTree a, int elem) {a[++top] = elem;}//弹栈函数void pop() {if (top == -1) {return;}top--;}//拿到栈顶元素int getTop(BiTree a) {return a[top];}//先序遍历顺序表中的完全二叉树void PreOrderTraverse(BiTree Tree) {//模拟栈，记录入栈结点所在顺序表中的下标int ad[NODENUM] = { 0 };int p;//根节点所在的顺序表下标先入栈push(ad,0);//直到栈中为空while (top != -1){//取出一个下标p = getTop(ad);pop(ad);//判断当前下标是否超出结点的总数while (p < NODENUM){//输出 p 下标处存储的结点值printf("%d ", Tree[p]);//找到该结点的右孩子，该它的数组下标入栈if ((2 * p + 2 < NODENUM) && (Tree[2 * p + 2] != 0)) {push(ad, 2 * p + 2);}//找到 p 下标结点的左孩子，并继续遍历p = 2 * p + 1;}}}

对于链表存储的二叉树，非递归实现先序遍历二叉树的 C 语言代码为：

//全局变量，记录栈顶的位置int top = -1;//前序遍历使用的进栈函数void push(BiTree* a, BiTree elem) {a[++top] = elem;}//弹栈函数void pop() {if (top == -1) {return;}top--;}//拿到栈顶元素BiTNode* getTop(BiTree* a) {return a[top];}//先序遍历二叉树void PreOrderTraverse(BiTree Tree) {BiTNode* a[20];//定义一个顺序栈BiTNode* p;//临时指针push(a, Tree);//根结点进栈while (top != -1) {p = getTop(a);//取栈顶元素pop();//弹栈while (p) {printf("%d ", p->data);//调用结点的操作函数//如果该结点有右孩子，右孩子进栈if (p->rchild) {push(a, p->rchild);}p = p->lchild;//一直指向根结点最后一个左孩子}}}

中序遍历

二叉树的中序遍历，指的是从根结点出发，按照以下步骤访问二叉树中的每个结点：

• 先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；

• 访问当前结点；

• 最后进入当前结点的右子树，以同样的步骤遍历右子树中的结点。

中序遍历这棵二叉树的过程是：

进入结点 1 的左子树，访问左子树中的结点；进入结点 2 的左子树，访问左子树中的结点；试图进入结点 4 的左子树，但该结点没有左子树；访问结点 4；试图进入结点 4 的右子树，但该结点没有右子树；访问结点 2；进入结点 2 的右子树，访问右子树中的结点；试图进入结点 5 的左子树，但该结点没有左子树；访问结点 5；试图进入结点 5 的右子树，但该结点没有右子树；访问结点 1；进入结点 1 的右子树，访问右子树中的结点；进入结点 3 的左子树，访问左子树中的结点；试图进入结点 6 的左子树，但该结点没有左子树；访问结点 6；试图进入结点 6 的右子树，但该结点没有右子树；访问结点 3；进入结点 3 的右子树，访问右子树中的结点；试图进入结点 7 的左子树，但该结点没有左子树；访问结点 7；试图进入结点 7 的右子树，但该结点没有右子树；

最终，中序遍历图 1 中的二叉树，访问各个结点的顺序是：

4 2 5 1 6 3 7

递归中序遍历二叉树

对于顺序表存储的二叉树，递归实现中序遍历的 C 语言程序为：

void INOrderTraverse(BiTree T, int p) {//递归遍历左子树if (((2 * p + 1) < NODENUM) && (T[2 * p + 1] != 0)) {INOrderTraverse(T, 2 * p + 1);}//访问当前结点printf("%d ", T[p]);//递归遍历右子树if (((2 * p + 2) < NODENUM) && (T[2 * p + 2] != 0)){INOrderTraverse(T, 2 * p + 2);} }

对于链表存储的二叉树，递归实现中序遍历的 C 语言程序为：

void INOrderTraverse(BiTree T) {if (T) {INOrderTraverse(T->lchild);//遍历当前结点的左子树printf("%d ",T->data); //访问当前结点INOrderTraverse(T->rchild);//遍历当前结点的右子树}}

非递归中序遍历二叉树

递归的底层实现借助的是栈存储结构，因此我们可以自己模拟出一个栈结构，以非递归的方式实现二叉树的中序遍历。

非递归中序遍历一棵树二叉树，具体有两种实现方案：

• 方案一：从根结点开始，不断地遍历当前结点的左子树并将该结点压入栈中，直至不再有左子树。然后从栈顶取出一个结点并访问它，然后将它的右孩子压入栈中，继续以同样的方式遍历它的右子树；

• 方案二：和方案一唯一的不同之处在于，压入栈中的只会是每个结点的左孩子，右孩子不需要入栈。

对于顺序表存储的二叉树，以上两种方案对应的 C 语言程序分别是：

//全局变量，记录栈顶的位置int top = -1;//前序遍历使用的入栈函数void push(BiTree a, int elem) {a[++top] = elem;}//弹栈函数void pop() {if (top == -1) {return;}top--;}//拿到栈顶元素int getTop(BiTree a) {return a[top];}//方案1void InOrderTraverse1(BiTree Tree) {//模拟栈，记录入栈结点所在顺序表中的下标int ad[NODENUM] = { 0 };int p;push(ad, 0);//根节点的数组下标入栈//直至栈为空，中序遍历才结束while (top != -1) {//不断的将各个结点的左孩子入栈while ((p = getTop(ad)) < NODENUM) {if (Tree[p] == 0) {break;}push(ad, 2 * p + 1);}pop();//栈顶的下标肯定超出了 NODENUM 指定范围，直接弹出//不再有左子树之后，访问当前结点，并将其右子树入栈if (top != -1) {p = getTop(ad);pop();printf("%d ", Tree[p]);push(ad, p * 2 + 2);}}}//方案2void InOrderTraverse2(BiTree Tree) {//模拟栈，记录入栈结点所在顺序表中的下标int ad[NODENUM] = { 0 };int p = 0;while (p < NODENUM || top != -1) {//将每个结点的左孩子入栈if (p < NODENUM && Tree[p] != 0) {push(ad, p);p = p * 2 + 1;}else{//如果栈空，则中序遍历结束if (top == -1) {break;}//访问该结点，并将其右孩子的下标赋值给 p，继续遍历右子树p = getTop(ad);pop();printf("%d ", Tree[p]);p = p * 2 + 2;}}}

对于链表存储的二叉树，以上两种方案对应的 C 语言程序分别是：

//全局变量，表示栈顶int top = -1;//前序和中序遍历使用的进栈函数void push(BiTNode** a, BiTNode* elem) {a[++top] = elem;}//弹栈函数void pop() {if (top == -1) {return;}top--;}//查看栈顶元素BiTNode* getTop(BiTNode** a) {return a[top];}//方案1void InOrderTraverse1(BiTree Tree) {BiTNode* a[20];//定义一个顺序栈BiTNode* p;//临时指针push(a, Tree);//根结点进栈while (top != -1) {//top!=-1说明栈内不为空，程序继续运行while ((p = getTop(a)) && p) {//取栈顶元素，且不能为NULLpush(a, p->lchild);//将该结点的左孩子进栈，如果没有左孩子，NULL进栈}pop();//跳出循环，栈顶元素肯定为NULL，将NULL弹栈if (top != -1) {p = getTop(a);//取栈顶元素pop();//栈顶元素弹栈printf("%d ", p->data);push(a, p->rchild);//将p指向的结点的右孩子进栈}}}//方案2void InOrderTraverse2(BiTree Tree) {BiTNode* a[20];//定义一个顺序栈BiTNode* p;//临时指针p = Tree;//当p为NULL或者栈为空时，表明树遍历完成while (p || top != -1) {//如果p不为NULL，将其压栈并遍历其左子树if (p) {push(a, p);p = p->lchild;}//如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树else {p = getTop(a);pop();printf("%d ", p->data);p = p->rchild;}}}

后序遍历

后序遍历二叉树，指的是从根结点出发，按照以下步骤访问树中的每个结点：

• 优先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；

• 如果当前结点没有左子树，则进入它的右子树，以同样的步骤遍历右子树中的结点；

• 直到当前结点的左子树和右子树都遍历完后，才访问该结点。

后序遍历这棵二叉树的过程是：

从根节点 1 出发，进入该结点的左子树；进入结点 2 的左子树，遍历左子树中的结点：进入结点 4 的左子树，但该结点没有左孩子；进入结点 4 的右子树，但该结点没有右子树；访问结点 4；进入结点 2 的右子树，遍历右子树中的结点：进入结点 5 的左子树，但该结点没有左孩子；进入结点 5 的右子树，但该结点没有右孩子；访问结点 5；访问结点 2；进入结点 1 的右子树，遍历右子树中的结点：进入结点 3 的左子树，遍历左子树中的结点：进入结点 6 的左子树，但该结点没有左孩子；进入结点 6 的右子树，但该结点没有右子树；访问结点 6；进入结点 3 的右子树，遍历右子树中的结点：进入结点 7 的左子树，但该结点没有左孩子；进入结点 7 的右子树，但该结点没有右孩子；访问结点 7；访问结点 3；访问结点 1。

最终，后序遍历图 1 中的二叉树，访问各个结点的顺序是：

4 5 2 6 7 3 1

递归后序遍历二叉树

后序遍历二叉树，最常用的实现方式就是递归。

对于顺序表存储的二叉树，递归实现后序遍历的 C 语言程序为：

void PostOrderTraverse(BiTree T, int p) {if ((p * 2 + 1 < NODENUM) && (T[p * 2 + 1] != 0)) {PostOrderTraverse(T, 2 * p + 1);}if ((p * 2 + 2 < NODENUM) && (T[p * 2 + 2] != 0)) {PostOrderTraverse(T, 2 * p + 2);}printf("%d ", T[p]);}

对于链表存储的二叉树，递归实现后序遍历的 C 语言程序为：

void PostOrderTraverse(BiTree T) {if (T) {PostOrderTraverse(T->lchild);//遍历左孩子PostOrderTraverse(T->rchild);//遍历右孩子printf("%d ", T->data);}}

非递归后序遍历二叉树

递归的底层实现过程是借助栈存储结构完成的，因此我们可以手动模拟一个栈结构，实现二叉树的后序遍历。

后序遍历是在遍历完当前结点的左右孩子之后才访问该结点，所以需要在当前结点进栈时为其配备一个标志位。当遍历该结点的左孩子时，设置当前结点的标志位为 0；当要遍历该结点的右孩子时，设置当前结点的标志位为 1，进栈。

这样当遍历完该结点的左右子树并将其弹栈时，查看该结点标志位的值：如果是 0，表示该结点的右孩子还没有遍历；如果是 1，说明该结点的左右孩子都遍历完成，可以访问此结点。

对于顺序表存储的二叉树，非递归实现后序遍历的 C 语言程序为：

#include #define NODENUM 7#define ElemType int//自定义 BiTree 类型，表示二叉树typedef ElemType BiTree[NODENUM];int top = -1;//表示栈顶typedef struct SNode {int p; //结点所在顺序表的下标int tag; //标记值}SNode;//存储二叉树void InitBiTree(BiTree T) {ElemType node;int i = 0;printf("按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:");while (scanf("%d", &node)){T[i] = node;i++;}}// 弹栈函数void pop() {if (top == -1) {return;}top--;}//入栈void push(SNode* a, SNode sdata) {a[++top] = sdata;}void PostOrderTraverse(BiTree Tree) {SNode a[20] = {0};//定义一个顺序栈int tag; //记录结点的标记位SNode sdata;int p = 0;while (p < NODENUM || top != -1) {//压入结点的左子树while (p < NODENUM && Tree[p] != 0) {sdata.p = p;sdata.tag = 0;push(a, sdata);p = p * 2 + 1;//继续遍历左孩子}//取栈顶元素sdata = a[top];pop();p = sdata.p;tag = sdata.tag;//如果tag==0，说明该结点还没有遍历它的右孩子if (tag == 0) {sdata.p = p;sdata.tag = 1;push(a,sdata);p = p * 2 + 2;//继续遍历右子树}//如果取出来的栈顶元素的tag==1，说明此结点左右子树都遍历完了，可以访问该结点了else{printf("%d ", Tree[p]);p = NODENUM;//重置 p 的值，防止下次进入第一个循环}}}int main() {BiTree T = { 0 };InitBiTree(T);PostOrderTraverse(T);return 0;}

运行结果为：

按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:1 2 3 4 5 6 7 #
4 5 2 6 7 3 1

对于链表存储的二叉树，非递归实现后序遍历的 C 语言程序为：

#include #include #define TElemType intint top = -1;//表示栈顶typedef struct BiTNode {TElemType data;//数据域struct BiTNode* lchild, * rchild;//左右孩子指针}BiTNode, * BiTree;//后序遍历非递归算法typedef struct SNode {BiTree p;int tag;}SNode;void CreateBiTree(BiTree* T) {int num;scanf("%d", &num);//如果输入的值为 0，表示无此结点if (num == 0) {*T = NULL;}else{//创建新结点*T = (BiTree)malloc(sizeof(BiTNode));(*T)->data = num;CreateBiTree(&((*T)->lchild));//创建该结点的左孩子CreateBiTree(&((*T)->rchild));//创建该结点的右孩子}}//弹栈函数void pop() {if (top == -1) {return;}top--;}//入栈void push(SNode* a, SNode sdata) {a[++top] = sdata;}//后序遍历二叉树void PostOrderTraverse(BiTree Tree) {SNode a[20];//定义一个顺序栈BiTNode* p = NULL;//临时指针int tag; //记录结点的标记位SNode sdata;p = Tree;while (p || (top != -1)) {while (p) {//为该结点入栈做准备sdata.p = p;sdata.tag = 0;//由于遍历是左孩子，设置标志位为0push(a, sdata);//压栈p = p->lchild;//以该结点为根结点，遍历左孩子}sdata = a[top];//取栈顶元素pop();//栈顶元素弹栈p = sdata.p;tag = sdata.tag;//如果tag==0，说明该结点还没有遍历它的右孩子if (tag == 0) {sdata.p = p;sdata.tag = 1;push(a, sdata);//更改该结点的标志位，重新压栈p = p->rchild;//以该结点的右孩子为根结点，重复循环}//如果取出来的栈顶元素的tag==1，说明此结点左右子树都遍历完了，可以访问该结点了else {printf("%d ", p->data);p = NULL;}}}//后序遍历二叉树，释放树占用的内存void DestroyBiTree(BiTree T) {if (T) {DestroyBiTree(T->lchild);//销毁左孩子DestroyBiTree(T->rchild);//销毁右孩子free(T);//释放结点占用的内存}}int main() {BiTree Tree;CreateBiTree(&Tree);PostOrderTraverse(Tree);DestroyBiTree(Tree);return 0;}

层次遍历

线索二叉树

我们知道，树是有层次的，比如：

上面这棵树一共有 3 层，根结点位于第一层，以此类推。

所谓层次遍历二叉树，就是从树的根结点开始，一层一层按照从左往右的次序依次访问树中的结点。

二叉树的存储方式有两种，分别是顺序表和链表。对于顺序表存储的二叉树，层次遍历是很容易实现的，因为二叉树中的结点本就是一层一层存储到顺序表中的。唯一需要注意的是，顺序表存储的只能是完全二叉树，普通二叉树必须先转换成完全二叉树后才能存储到顺序表中，因此在实现层次遍历的时候，需要逐个对顺序表中存储的结点进行甄别。

层次遍历用链表存储的二叉树，可以借助队列存储结构实现，具体方案是：

• 将根结点入队；

• 从队列的头部提取一个结点并访问它，将该结点的左孩子和右孩子依次入队；

• 重复执行第 2 步，直至队列为空；

假设将图 1 中的二叉树存储到链表中，那么层次遍历的过程是：

根结点 1 入队（1）；根结点 1 出队并访问它，然后将 1 的左孩子 2 和右孩子 3 依次入队（3, 2）；将结点 2 出队并访问它，然后将 2 的左孩子 4 和右孩子 5 依次入队（5,4,3）；将结点 3 出队并访问它，然后将 3 的左孩子 6 和右孩子 7 依次入队（7,6,5,4）；根结点 4 出队并访问它，然后将 4 的左孩子（无）和右孩子（无）依次入队（7,6,5）；将结点 5 出队并访问它，然后将 5 的左孩子（无）和右孩子（无）依次入队（7,6）；将结点 6 出队并访问它，然后将 6 的左孩子（无）和右孩子（无）依次入队（7）；将结点 7 出队并访问它，然后将 6 的左孩子（无）和右孩子（无）依次入队（）；队列为空，层次遍历结束。

层次遍历顺序二叉树

#include #define NODENUM 7 //二叉树中结点的个数#define ElemType int//自定义 BiTree 类型，表示二叉树typedef ElemType BiTree[NODENUM];//顺序表存储二叉树void InitBiTree(BiTree T) {ElemType node;int i = 0;printf("按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:");while (scanf("%d", &node)){T[i] = node;i++;}}//层次遍历二叉树void LevelOrderTraverse(BiTree T) {int j;//从根结点起,层次遍历二叉树for (j = 0; j < NODENUM; j++) {//只访问非空结点if (T[j] != 0) {printf("%d ", T[j]);}}}int main() {int res;BiTree T = { 0 };InitBiTree(T);LevelOrderTraverse(T);return 0;}

运行结果为：

按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:1 2 3 4 5 6 7 #
1 2 3 4 5 6 7

层次遍历链式二叉树

#include #include #define TElemType int#define NODENUM 7//初始化队头和队尾指针开始时都为0int front = 0, rear = 0;typedef struct BiTNode {TElemType data;//数据域struct BiTNode* lchild, * rchild;//左右孩子指针}BiTNode, * BiTree;//以先序遍历的方式存储二叉树到链表中void CreateBiTree(BiTree* T) {int num;scanf("%d", &num);//如果输入的值为 0，表示无此结点if (num == 0) {*T = NULL;}else{//创建新结点*T = (BiTree)malloc(sizeof(BiTNode));(*T)->data = num;CreateBiTree(&((*T)->lchild));//创建该结点的左孩子CreateBiTree(&((*T)->rchild));//创建该结点的右孩子}}//入队函数void EnQueue(BiTree* a, BiTree node) {if (rear == NODENUM) {printf("队列已满，入队失败\n");exit(0);}a[rear++] = node;}//出队函数BiTNode* DeQueue(BiTNode** a) {if (front == rear) {printf("队列为空，出队失败\n");exit(0);}return a[front++];}//层次遍历二叉树void LevelOrderTraverse(BiTree T) {//如果二叉树存在，才进行层次遍历if (T) {BiTree a[20] = { 0 };BiTree p = NULL;p = T;//根结点入队EnQueue(a, p);//重复执行，直至队列为空while (front < rear){//从队列取出一个结点p = DeQueue(a);//访问当前结点printf("%d ", p->data);//将当前结点的左右孩子依次入队if (p->lchild) {EnQueue(a, p->lchild);}if (p->rchild) {EnQueue(a, p->rchild);}}} }//后序遍历二叉树，释放树占用的内存void DestroyBiTree(BiTree T) {if (T) {DestroyBiTree(T->lchild);//销毁左孩子DestroyBiTree(T->rchild);//销毁右孩子free(T);//释放结点占用的内存}}int main() {BiTree Tree;CreateBiTree(&Tree);LevelOrderTraverse(Tree);DestroyBiTree(Tree);return 0;}

运行结果：

1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
1 2 3 4 5 6 7