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

Bertha 。 2023-09-25 14:41 8阅读 0赞

二叉树——层次遍历

**目录**

1.定义变量

2.创建一棵树

3.初始化队

4.入队操作

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

6.出队操作

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

7.先序遍历，对比结果

8.主函数调用

9.结果展示

--------------------

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

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

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

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

代码：

### **1.定义变量** ###

#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.创建一棵树** ###

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

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.初始化队** ###

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

### **4.入队操作** ###

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.判断队列是否为空函数** ###

int is_emepty(QueueNode* Q)
    {
    	if (Q->next == NULL)
    		return 0;
    	else
    		return 1;
    }

### **6.出队操作** ###

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.层次循环遍历，打印结果** ###

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.先序遍历，对比结果** ###

void preOrder(TreeNode* t)
    {
    	if (t == NULL)
    		return;
    	else
    	{
    		printf("%c", t->data);
    		preOrder(t->lchild);
    		preOrder(t->rchild);
    	}
    }

### **8.主函数调用** ###

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.结果展示** ###

ab##c##
    abc
    a b c
    D:\VS\test.2\树\Debug\树.exe (进程 7660)已退出，代码为 -1073741819。
    按任意键关闭此窗口. . .

adc#d####
    adcd
    a d c d
    D:\VS\test.2\树\Debug\树.exe (进程 12196)已退出，代码为 -1073741819。
    按任意键关闭此窗口. . .