【数据结构初阶】--二叉树(六)

发布于：2025-08-01 ⋅ 阅读:(22) ⋅ 点赞:(0)

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。   

前言： 这篇博客将会和大家一起实现一下二叉树中的层序遍历以及判断一个二叉树是否为完全二叉树的代码实现，其中会引入队列这个数据结构的使用，中间有些需要修改的地方会特别声明大家注意一下。

目录

一.二叉树的层序遍历

准备工作：

代码实现： 

test.c： 

二.判断是否为完全二叉树

代码实现：

test.c： 

三.代码展现

Tree.h：

Tree.c：

一.二叉树的层序遍历

--我们前面实现的前中后序遍历都是属于深度优先遍历，而我们这里的层序遍历属于广义优先遍历，这里使用不了递归，我们都借助队列这个数据结构来实现，那么在实现之前有以下几个修改的地方

准备工作：

1.我们需要先把队列的.c和.h文件导入到当前vs项目中，然后在Tree.c文件里面包含上Queue.h文件

2.在Queue.h文件中我们需要把数据类型那里从int修改成二叉树节点结构类型，具体操作如图所示

代码实现： 

//二叉树的层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//根节点入队
	QueuePush(&q, root);

	//遍历
	while (!QueueEmpty(&q))
	{
		//取队首,打印，然后出队首
		BTNode* top = QueueHead(&q);
		printf("%c ", top->data);
		QueuePop(&q);

		//将top不为空的左右孩子节点入队
		if (top->left)
		{
			QueuePush(&q, top->left);
		}
		if (top->right)
		{
			QueuePush(&q, top->right);
		}
	}

	QueueDestory(&q);
}

具体操作过程如图所示： 

test.c： 

#include"Tree.h"

BTNode* buyNode(char x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}
BTNode* CreateTree()
{
	BTNode* nodeA = buyNode('A');
	BTNode* nodeB = buyNode('B');
	BTNode* nodeC = buyNode('C');
	BTNode* nodeD = buyNode('D');
	BTNode* nodeE = buyNode('E');
	BTNode* nodeF = buyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}

void test1()
{
	BTNode* root = CreateTree();

	//前中后序遍历
	//PreOrder(root);
	//InOrder(root);
	//PostOrder(root);

	//二叉树结点个数
	printf("Size: %d\n", BinaryTreeSize(root));
	//二叉树叶子结点个数
	printf("LeafSize: %d\n", BinaryTreeLeafSize(root));
	//第k层节点个数
	printf("K Size: %d\n", BinaryTreeLevelKSize(root,3));
	//二叉树的深度/高度
	printf("Depth: %d\n", BinaryTreeDepth(root));
	//二叉树查找值为x的结点
	BTNode* pos = BinaryTreeFind(root, 'E');
	if (pos)
	{
		printf("找到了\n");
	}
	else {
		printf("没找到\n");
	}

	//层序遍历
	printf("层序遍历结果:");
	LevelOrder(root);
	printf("\n");

	// 二叉树销毁
	BinaryTreeDestory(&root);
}

int main()
{
	test1();
	return 0;
}

--测试完成，打印顺序没有问题，退出码为0

二.判断是否为完全二叉树

  • 完全二叉树就是除了最后一层以外其它层节点个数全部达到最大，且节点全是从左到右依次排列

代码实现：

//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//根节点入队
	QueuePush(&q, root);

	//遍历
	while (!QueueEmpty(&q))
	{
		//取队首,然后出队首
		BTNode* top = QueueHead(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			//top取到空直接出队列
			break;
		}
		//将top的左右孩子节点全部入队
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}

	//队列不为空，继续取队列中的队头
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueHead(&q);
		if (top != NULL)
		{
			//有不是NULL的就不是完全二叉树
			QueueDestory(&q);
			return false;
		}
		QueuePop(&q);
	}
	QueueDestory(&q);
	return true;
}

 具体操作图示如下：

test.c： 

#include"Tree.h"

BTNode* buyNode(char x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}
BTNode* CreateTree()
{
	BTNode* nodeA = buyNode('A');
	BTNode* nodeB = buyNode('B');
	BTNode* nodeC = buyNode('C');
	BTNode* nodeD = buyNode('D');
	BTNode* nodeE = buyNode('E');
	BTNode* nodeF = buyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}

void test1()
{
	BTNode* root = CreateTree();

	//前中后序遍历
	//PreOrder(root);
	//InOrder(root);
	//PostOrder(root);

	//二叉树结点个数
	printf("Size: %d\n", BinaryTreeSize(root));
	//二叉树叶子结点个数
	printf("LeafSize: %d\n", BinaryTreeLeafSize(root));
	//第k层节点个数
	printf("K Size: %d\n", BinaryTreeLevelKSize(root,3));
	//二叉树的深度/高度
	printf("Depth: %d\n", BinaryTreeDepth(root));
	//二叉树查找值为x的结点
	BTNode* pos = BinaryTreeFind(root, 'E');
	if (pos)
	{
		printf("找到了\n");
	}
	else {
		printf("没找到\n");
	}

	//层序遍历
	printf("层序遍历结果:");
	LevelOrder(root);
	printf("\n");

	//判断是否为完全二叉树
	bool iscomplete = BinaryTreeComplete(root);
	if (iscomplete)
	{
		printf("是完全二叉树\n");
	}
	else {
		printf("不是完全二叉树\n");
	}

	// 二叉树销毁
	BinaryTreeDestory(&root);
}

int main()
{
	test1();
	return 0;
}

--测试完成，没有问题，这里创建的树不是完全二叉树，退出码为0

三.代码展现

--其中队列的代码还有test.c文件(和最后一次的一样)就不展示了

Tree.h：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef char BTDataType;
typedef struct BinaryNode
{
	BTDataType data;
	struct BinaryNode* left;//左孩子
	struct BinaryNode* right;//右孩子
}BTNode;

//前序遍历
void PreOrder(BTNode* root);

//中序遍历
void InOrder(BTNode* root);

//后序遍历
void PostOrder(BTNode* root);

// 二叉树结点个数
int BinaryTreeSize(BTNode* root);

// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);

// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);

// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

//二叉树的层序遍历
void LevelOrder(BTNode* root);

//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

Tree.c：

#include"Tree.h"
#include"Queue.h"

//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	//根左右
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	//左根右
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	//左右根
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

// 二叉树结点个数=根节点+左子树节点个数+右子树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

// 二叉树叶子结点个数=左子树叶子节点个数+右子树节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//判断是否为叶子节点（没有左右孩子）
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

// 二叉树第k层节点个数=左子树第K-1层节点个数+右子树第k-1层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	//判断是否为第k层
	if (k == 1)
	{
		return 1;
	}
	//每次注意要k-1
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

//二叉树的深度/高度=根节点+max(左子树高度，右子树高度)
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int leftdepth = BinaryTreeDepth(root->left);
	int rightdepth = BinaryTreeDepth(root->right);
	return 1 + (leftdepth > rightdepth ? leftdepth : rightdepth);
}

// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}

	BTNode*leftroot = BinaryTreeFind(root->left, x);
	//如果leftroot不为空就是找到了直接返回
	if (leftroot)
	{
		return leftroot;
	}
	//没找到就继续右子树找
	BTNode* rightroot = BinaryTreeFind(root->right, x);
	if (rightroot)
	{
		return rightroot;
	}
	//都没找到就返回空
	return NULL;
}

// 二叉树销毁--采用后序遍历的思想
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}

	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
		*root = NULL;
}

//二叉树的层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//根节点入队
	QueuePush(&q, root);

	//遍历
	while (!QueueEmpty(&q))
	{
		//取队首,打印，然后出队首
		BTNode* top = QueueHead(&q);
		printf("%c ", top->data);
		QueuePop(&q);

		//将top不为空的左右孩子节点入队
		if (top->left)
		{
			QueuePush(&q, top->left);
		}
		if (top->right)
		{
			QueuePush(&q, top->right);
		}
	}

	QueueDestory(&q);
}

//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//根节点入队
	QueuePush(&q, root);

	//遍历
	while (!QueueEmpty(&q))
	{
		//取队首,然后出队首
		BTNode* top = QueueHead(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			//top取到空直接出队列
			break;
		}
		//将top的左右孩子节点全部入队
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}

	//队列不为空，继续取队列中的队头
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueHead(&q);
		if (top != NULL)
		{
			//有不是NULL的就不是完全二叉树
			QueueDestory(&q);
			return false;
		}
		QueuePop(&q);
	}
	QueueDestory(&q);
	return true;
}

往期回顾：

【数据结构初阶】--二叉树(二)

【数据结构初阶】--二叉树(三)

【数据结构初阶】--二叉树(四)

【数据结构初阶】--二叉树(五)

结语：我们在这篇文章中实现了链式结构二叉树的全部常用接口，其实二叉树中还有一些常考的选择题，博主这里会专门出一个特别篇带大家一起学习一下二叉树中常考的选择题，分享一下能用到的知识点，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布