c语言 数据结构二叉树 层次遍历 简单上手代码

2023-10-10 13:28:49 浏览数 (1)

首先，想如何层次的遍历一个二叉树呢？简单思路分为如下几步：

1.要先创建一个二叉树。（二叉树建立可参考上一篇博客）

2.采用队列思想，先进先出。也就是说先要创建一个队列。

3.首先根入队，然后出队，再入队它的左右孩子，然后左孩子出队，再入队左孩子的左右孩子，再出队右孩子，加入右孩子没有左右孩子为空，就什么就不用干，继续出队左孩子的左右孩子，直到所有元素都出完队时，遍历也就结束了。

代码：

1.定义变量

代码语言：javascript复制
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct TreeNode
{
	int data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;              //定义树
typedef struct QueueNode
{
	TreeNode* node;
	struct QueueNode* pre;
	struct QueueNode* next;
};                    // 定义队

2.创建一棵树

不再详细解释，如果不会看上一篇博客二叉树代码实现。

代码语言：javascript复制
void creatTree(TreeNode** t,int* index,char* data)
{
char ch;
ch = data[*index];
(*index)  ;
if (ch == '#')
*t = NULL;
else
{
*t = (TreeNode*)malloc(sizeof(TreeNode));
assert(*t);
(*t)->data = ch;
creatTree(&((*t)->lchild), index, data);
creatTree(&((*t)->rchild), index, data);
}
}

3.初始化队

代码语言：javascript复制
QueueNode* initQueue()
{
QueueNode* Q = (QueueNode*)malloc(sizeof(QueueNode));
assert(Q);
Q->node = NULL;
Q->next =Q;
Q->pre = Q;
return Q;
}
//采用循环双链表队列模式，其它链表也可

4.入队操作

代码语言：javascript复制
void enQueue(QueueNode* Q,TreeNode* data)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    assert(newnode);
	newnode->node = data;
	newnode->pre= Q;
	newnode->next = Q;
	Q->pre->next = newnode;
	Q->pre = newnode;
}

5.判断队列是否为空函数

代码语言：javascript复制
int is_emepty(QueueNode* Q)
{
	if (Q->next == NULL)
		return 0;
	else
		return 1;
}

6.出队操作

代码语言：javascript复制
QueueNode* deQueue(QueueNode* Q)
{
	if (is_emepty(Q) == 0)
		return NULL;
	else
	{
		QueueNode* node = Q->next;
		Q->next->next->pre = Q;
		Q->next = Q->next->next;
		return node;
	}
}

7.层次循环遍历，打印结果

代码语言：javascript复制
void levelTraverse(QueueNode* Q, TreeNode* T)
{
	enQueue(Q, T);   
	while (is_emepty(Q))
	{
		QueueNode* node = deQueue(Q);
		printf("%c ", node->node->data);
		if (node->node->lchild)
			enQueue(Q, node->node->lchild);
		if (node->node->rchild)
			enQueue(Q, node->node->rchild);
	}
}

7.先序遍历，对比结果

代码语言：javascript复制
void preOrder(TreeNode* t)
{
	if (t == NULL)
		return;
	else
	{
		printf("%c", t->data);
		preOrder(t->lchild);
		preOrder(t->rchild);
	}
}

8.主函数调用

代码语言：javascript复制
int main()
{
	TreeNode* t;
	char data[100];
	int index = 0;
	gets_s(data);
	creatTree(&t, &index, data);
	preOrder(t);
	printf("n");
	QueueNode* q = initQueue();
	levelTraverse(q, t);
	return 0;
}

9.结果展示

代码语言：javascript复制
ab##c##
abc
a b c
D:VStest.2树Debug树.exe (进程 7660)已退出，代码为 -1073741819。
按任意键关闭此窗口. . .
代码语言：javascript复制
adc#d####
adcd
a d c d
D:VStest.2树Debug树.exe (进程 12196)已退出，代码为 -1073741819。
按任意键关闭此窗口. . .
二叉树 数据结构 遍历 队列 进程

0 人点赞