![cover](https://img-blog.csdnimg.cn/7b5be789bcd3407680b65430028405de.png)
【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];
}
//方案1
void 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);
}
}
}
//方案2
void 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];
}
//方案1
void InOrderTraverse1(BiTree Tree) {
BiTNode* a[20];//定义一个顺序栈
BiTNode* p;//临时指针
push(a, Tree);//根结点进栈
while (top != -1) {//top!=-1说明栈内不为空,程序继续运行
while ((p = getTop(a)) && p) {//取栈顶元素,且不能为NULL
push(a, p->lchild);//将该结点的左孩子进栈,如果没有左孩子,NULL进栈
}
pop();//跳出循环,栈顶元素肯定为NULL,将NULL弹栈
if (top != -1) {
p = getTop(a);//取栈顶元素
pop();//栈顶元素弹栈
printf("%d ", p->data);
push(a, p->rchild);//将p指向的结点的右孩子进栈
}
}
}
//方案2
void 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 <stdio.h>
#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 <stdio.h>
#include <stdlib.h>
#define TElemType int
int 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;//由于遍历是左孩子,设置标志位为0
push(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 <stdio.h>
#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 <stdio.h>
#include <stdlib.h>
#define TElemType int
#define NODENUM 7
//初始化队头和队尾指针开始时都为0
int 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
更多推荐
所有评论(0)