小惠珠哦

这个屌丝很懒，什么也没留下！

热门标签

二叉树的四种遍历详解（先序，中序，后序，层次）_二叉树遍历前序中序后序

作者：小惠珠哦 | 2024-07-02 05:39:34

踩

二叉树遍历前序中序后序

引言：

二叉树的遍历的概念：二叉树遍历是指按照一定的次序访问二叉树中的所有结点，并且每个结点仅被访问一次的过程。它是二叉树最基本的运算，是二叉树中所有其它运算实现的基础。

为了帮助大家理解各类的遍历过程，下面我给出一个二叉树，下面的各类遍历结果都是根据这张图的图片如下：

二叉树的遍历各类过程：

先序中序和后序都是利用递归来实现的。

层次遍历使用队列实现的

1：先序遍历

（1）访问跟结点

（2）先序遍历左子树

（3）先序遍历右子树

图所示的二叉树的先序序列位ABDGCEF。

先序的代码：

先访问根节点再访问左子树后右子树。


//先序遍历
void PreOrder(BTNode* b)
{
	if (b != NULL)
	{
		printf("%c ", b->data);
		PreOrder(b->lchild);
		PreOrder(b->rchild);
	}
	return;
}

2.中序遍历

（1）中序遍历左子树

（2）访问跟结点

（3）中序遍历右子树

图所示的二叉树的中序序列位DGBAECF。

中序的代码：

先访问左子树，再访问根结点，最后是右子树。


//中序遍历
void InOrder(BTNode* b)
{
	if (b != NULL)
	{
		InOrder(b->lchild);
		printf("%c ", b->data);
		InOrder(b->rchild);
	}
	return;
}

3.后续遍历

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根结点

图所示的二叉树的中序序列位GDBEFCA。

后序的代码：

先访问左子树再访问右子树，最后是根结点。


//后序遍历
void PostOrder(BTNode* b)
{
	if (b != NULL)
	{
		PostOrder(b->lchild);
		PostOrder(b->rchild);
		printf("%c ", b->data);
	}
	return;
}

4.层次遍历

（1）访问根节点（第一层）

（2）从左到右访问第二层的所有结点。

（3）从左到右访问第三层的所有结点.....第h层的所有结点。

图所示的二叉树的中序序列位ABCDEFG。

层次的代码：

层次是用队列来实现的下面这个代码只是思路，完整代码后续给出。

那么为什么后想到用队列来实现呢？我们可以观察到，二叉树的层次遍历就是按层次从上到下，每一层从左到右的顺序访问树中的全部结点。故某一层中先访问的结点在下一层中它的孩子也先访问，这样不就和我们的队列特性相符合吗，因此层次遍历算法采用一个队列qu来实现。算法中的队列采用顺序队存储结构。

队列的图片如下：


//层次遍历
typedef struct Node
{
	BTNode* data[MaxSize];
	int front, rear;
}SqQueue;
void LevelOrder(BTNode* b)
{
	BTNode* p=NULL;
	SqQueue* qu;
	qu = InitQueue();
	enQueue(qu, b);
	while (!EmptyQueue(qu))
	{
		deQueue(qu, &p);
		printf("%c ", p->data);
		if (p->lchild != NULL)
			enQueue(qu, p->lchild);
		if (p->rchild != NULL)
			enQueue(qu, p->rchild);
	}
	DestroyQueue(qu);
}

以上便是各类遍历的基本思路，下面我会结合一下运用遍历的例题来帮助大家理解，因为文章篇幅有限，故例题只给出实现函数部分，没有给出主函数，特别说明最后面我会给出一个主函数（非常完整），大家例题中的代码都能带进去运行，方便大家调试理解。由于层次遍历和前面三种遍历实现方法不太一样，故下面的例题会分为，前面三种遍历和层次遍历。

先序中序后序例题：

例题1：

设计一个算法，输出一颗给定二叉树的所有结点。

即输出：GEF结点

对应的函数如下DispLeaf（BTNode*b）

通过判断有无孩子结点来判断他是不是叶子结点（最下面那个结点）,如果不是就递归左右子树找叶子。此题三种遍历都能实现，下面代码是先序遍历，如果把if和DispLeaf(b->lchild);交换就变成中序遍历，同理如果把DispLeaf(b->lchild)和 DispLeaf(b->rchild);同时先上移，这样就变成后序遍历。


void DispLeaf(BTNode* b)//求叶子结点
{
	if (b != NULL)
	{
		if (b->lchild == NULL && b->rchild == NULL)
		{
			printf("%c ", b->data);
		}
		DispLeaf(b->lchild);
		DispLeaf(b->rchild);
	}
 
}

运行结果如下：

例题2：

设计一个算法求二叉树b中第k层的结点个数。

思路如下：函数名为void Lnodenum(BTNode* b, int h, int k, int* n),其中h表示b所指的结点层次，n是引用型参数，由于求第k层的结点个数，在初始调用时，b为根结点指针，h为1，n赋值为0，即调用方式时n=0；Lnodenum(b, 1, k, &t);

采用先序遍历的函数如下，如果想用中序和后序的话按照例题一的修改方法即可。


void Lnodenum(BTNode* b, int h, int k, int* n)
{
	if (b == NULL)
	{
		return;
	}
	else if (h == k)
	{
		if(b->data!=' ') *n = *n + 1;		
		return;
	}
	else if (h < k)
	{
		Lnodenum(b->lchild, h + 1, k, n);//特别注意不要&n
		Lnodenum(b->rchild, h + 1, k, n);
	}
}

运行结果如下：

对照上面给出的二叉树的图大家可以试试。

对应的main函数。

直接将上面的两个函数加进去即可，其中CreateBTree和DispBTree在我的上一篇文章二叉树的基本运算中已经讲的很清楚了，如果有朋友们不是很清楚的话，可以去上一篇文章看看，写的很详细哦。


#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
#define MaxSize 100
typedef struct node
{
	struct node* lchild, * rchild;
	ElemType data;
}BTNode;
BTNode* CreateBTree(char* str)
{
	BTNode* SqStack[MaxSize];
	BTNode* b;
	BTNode* p = NULL;
	b = NULL;
	int top = -1;
	char ch;
	int j = 0;
	ch = str[j];
	int k = 0;
	while (ch != '\0')
	{
		switch (ch)
		{
		case '(':k = 1; top++; SqStack[top] = p; break;
		case ')':top--; break;
		case ',':k = 2; break;
		default:
		{
			p = (BTNode*)malloc(sizeof(BTNode));
			p->data = ch;
			p->lchild = p->rchild = NULL;
			if (b == NULL)
			{
				b = p;
			}
			else
			{
				switch (k)
				{
				case 1:SqStack[top]->lchild = p; break;
				case 2:SqStack[top]->rchild = p; break;
				}
			}
		}
		}
		j++;
		ch = str[j];
	}
	return b;
}
void DispBTree(BTNode* b)
{
	if (b != NULL)
	{
		printf("%c", b->data);
		if (b->lchild != NULL || b->rchild != NULL)
		{
			printf("(");
			DispBTree(b->lchild);
			if (b->rchild != NULL) printf(",");
			DispBTree(b->rchild);
			printf(")");
		}
	}
 
}
 
 
int main()
{
	char str[] = "A(B(D( ,G)),C(E,F))";
	BTNode* b = CreateBTree(str);
	//DispLeaf(b);
	int t = 0;
	Lnodenum(b, 1, 3, &t);
	printf("%d", t);
	//DispBTree(b);
	return 0;
}

层次遍历例题：

设计一个算法将二叉树按层次遍历输出：

层次遍历过程是先将根结点进队，在队不空是循环：出队一个结点p并访问它，若它有左孩子，将左孩子进队：若它有右孩子，将有孩子进队。如此操作，直到队空为止。次过程称为基本层次遍历过程，对应的算法代码如下。本身代码不多主要是实现队列挺麻烦的（这就是为什么c语言没有别的语言效率那么高的原因，别的语言有的自带队列）。


#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef char ElemType;
#define MaxSize 100
typedef struct node
{
	struct node* lchild;
	struct node* rchild;
	ElemType data;
}BTNode;
typedef struct 
{
	BTNode* data[MaxSize];
	int front, rear;
}SqQueue;
//基本层次遍历算法
SqQueue* InitQueue()
{
	SqQueue* obj = (SqQueue*)malloc(sizeof(SqQueue));
	obj->front = obj->rear = -1;
	return obj;
}
bool enQueue(SqQueue* qu, BTNode* b)
{
	qu->rear++;
	qu->data[qu->rear] = b;
	return true;
}
bool EmptyQueue(SqQueue* qu)
{
	return (qu->front == qu->rear);
}
bool deQueue(SqQueue* qu, BTNode** b)
{
	qu->front++;
	*b = qu->data[qu->front];
	return true;
}
void DestroyQueue(SqQueue* qu)
{
	free(qu);
}
void LevelOrder(BTNode* b)
{
	BTNode* p = NULL;
	SqQueue* qu;
	qu = InitQueue();
	enQueue(qu, b);
	while (!EmptyQueue(qu))
	{
		deQueue(qu, &p);
		printf("%c ", p->data);
		if (p->lchild != NULL)
			enQueue(qu, p->lchild);
		if (p->rchild != NULL)
			enQueue(qu, p->rchild);
	}
	DestroyQueue(qu);
}
BTNode* CreateBTree(char str[])
{
	BTNode* b = (BTNode*)malloc(sizeof(BTNode));
	BTNode* St[MaxSize];
	b = NULL;
	BTNode* p = NULL;
	int top = -1;
	char ch;
	int j = 0;
	ch = str[j];
	int k;
	while (ch != '\0')
	{
		switch (ch)
		{
		case '(':top++; St[top] = p; k = 1; break;
		case ')':top--; break;
		case ',':k = 2; break;
		default:
		{
			p = (BTNode*)malloc(sizeof(BTNode));
			p->data = ch;
			p->lchild = p->rchild = NULL;
			if (b == NULL)
			{
				b = p;
			}
			else
			{
				switch (k)
				{
				case 1:St[top]->lchild = p; break;
				case 2:St[top]->rchild = p; break;
				}
			}
		}
		}
		j++;
		ch = str[j];
	}
	return b;
}
int main()
{
	char str[] = "A(B(D( ,G)),C(E,F))";
	BTNode* b = CreateBTree(str);
	LevelOrder(b);
}

以上便是先序中序后序层次遍历的算法及例题。文章到这也就到了尾声啦，感谢观看声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】