程序员社区

初阶数据结构——二叉树

🎉🎉想快速入门数据结构,推荐订阅作者的初阶数据结构专栏!此专栏预计更新:顺序表,链表,栈,队列,二叉树,排序算法等等

🎉🎉初阶数据结构我们通过c语言实现,所以此专栏也可以帮助大家巩固大家的c语言知识

🎉🎉源代码已上传至我的码云

前言

我们在上篇文章中已经介绍了二叉树的相关性质及其应用,点我直达上一篇文章

然而,在实际应用中,单纯地讲二叉树的增删查改是没有意义的

因为存储和访问数据,将会变得特别的困难,因为二叉树是一种层次结构,需要递归来定义,在哪一点添加删除?这将变成一个最大的问题

二叉树的增删查改仅仅在搜索二叉树和AVL树中有应用,但由于它们的实现比较复杂,将在后续的专栏中进行讲解

但我们实际在很多oj题中需要多二叉树进行遍历操作,所以我们在这篇文章中不讲解增删查改,只讲解一些基础的操作


分治思想
二叉树的各种操作使用的分治的思想,就是将大事化小,小事化了

举一个形象的例子:

你是某个学校的校长,需要统计你学校的总学生数

但如果你一个个的数的话,那工作量将会非常巨大

所以你可以这么分解问题:

将每个院的院长叫来,让他们统计每个院的人数

院长同样会将每个辅导员叫过来,安排任务

辅导员叫班主任,班主任叫班长

在这里班长已经不可拆分了,就可以依次往上上报了

最好,你只需要将每个院的结果加起来,就得到了学校的总人数

在解决二叉树的问题中,我们也用到了一样的思想:根就像我们的校长,要执行某个任务,可以安排给左子树和右子树进行,而左子树和右子树又可以把任务安排给它们的子树。。。


目录

  • 前言
  • 二叉树的定义
  • 遍历操作
    • 前序遍历
    • 中序遍历
    • 后序遍历
    • 层序遍历
  • 二叉树求结点个数
  • 二叉树求叶子结点的个数
  • 二叉树求第K层结点个数
  • 二叉树求最大深度
  • 二叉树返回某个指定结点
  • 判断是否为完全二叉树
  • 二叉树的销毁

二叉树的定义

我们这里采用链式定义的方式,一个结构体来定义一个结点,分别存放数据,指向左孩子的指针和指向右孩子的指针

typedef int BTDataType;

typedef struct BinTreeNode
{
	struct BinTreeNode* left;
	struct BinTreeNode* right;
	BTDataType data;
}BTNode;

为了以下内容的讲解,我们先写一个函数来创建一棵简单的树

BTNode* createBinTree()
{
	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));
	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;
	n6->data = 6;
	n7->data = 7;

	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = n5;
	n3->left = n6;
	n3->right = NULL;
	n4->left = n7;
	n4->right = NULL;
	n5->left = NULL;
	n5->right = NULL;
	n6->left = NULL;
	n6->right = NULL;
	n7->left = NULL;
	n7->right = NULL;

	return n1;
}

创建出来就是这样的一棵树

在这里插入图片描述

遍历操作

绪论

二叉树我们采用递归的方式来遍历,基本思想就是访问根,左子树,右子树,再访问左子树的根,左子树的左子树,左子树的右子树。。。依次往下

根据访问顺序的不一样,将它们分为以下几种遍历顺序

  1. 前序遍历:访问根,左子树,右子树
  2. 中序遍历:访问左子树,根,右子树
  3. 后序遍历:访问左子树,右子树,根

以下将具体举例

前序遍历

记得要始终先访问每棵树不论是哪棵子树的根,然后继续往下操作
直接上图解:

在这里插入图片描述
这样,前序遍历遍历出的结点顺序依次为:

1,2,4,7,5,3,6

根据递归的思想,我们可以直接写出代码

记住递归的几个要素:递归终止条件和递归继续的条件

void PrevOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL");//终止条件,为空直接返回
		return;
	}

	printf("%d ", root->data);//访问根部

	PrevOrder(root->left);//访问左子树
	PrevOrder(root->right);//访问右子树
}

递归展开图

在这里插入图片描述

中序遍历

中序遍历就是总是先访问完左子树后再访问根和右子树

还是以前面那棵树为例

在这里插入图片描述
这样,遍历出的顺序为

7,4,2,5,1,5,3

代码实现

void InOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);//与前序遍历的区别仅仅是将根部的访问放在中间
	InOrder(root->right);
}

后序遍历

与前面的思想基本差不多,这里就不详细阐述了

void PostOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

层序遍历

层序遍历,顾名思义,就是对树一层一层的进行遍历,其中每一层的结点都是从左到右遍历,就像下图这样

在这里插入图片描述
遍历出的顺序为

1,2,3,4,5,6,7

但是,这种遍历方式却不能用递归,

因为结点间的遍历没有上下级的关系了,每一层结点间也没有直接的联系,所以递归不能达到我们的目的

但是,我们却可以利用一种先进先出的数据结构:队列来解决我们的问题

具体步骤如下:

  1. 入一个结点
  2. 出队头结点并用变量保存,若这个结点的左右结点不为空,就将这个结点的左右结点也入在队列中
  3. 检查队列是否为空,不为空继续出,为空代表遍历完成

具体遍历过程如下:

在这里插入图片描述

代码实现

void LevelOrder(BTNode* root)
{
	if (!root)
		return;
	Quene q;
	QueneInit(&q);

	QuenePush(&q, root);

	while (!QueneEmpty(&q))
	{
		BTNode* front = QueneFront(&q);
		QuenePop(&q);
		printf("%d ", front->data);
		
		if (front->left)
			QuenePush(&q, front->left);
		if (front->right)
			QuenePush(&q, front->right);

	}
	QueneDestory(&q);
}

以下是对二叉树的一些基础判断操作

二叉树求结点个数

我们可以利用开始说到的思想,将问题分配给每个结点的下级,让他们分配任务

首先,如果是空树,或者走到叶子结点的下级了(叶子结点的下级为空)就返回0

然后就转换为左结点的个数+右结点的个数+1(+1代表要加上结点自己)

画图求解

在这里插入图片描述

int BinTreeSize(BTNode* root)
{
	return !root ? 0 : 1 + BinTreeSize(root->left) + BinTreeSize(root->right);
}

二叉树求叶子结点的个数

叶子结点的特征是它的左右子树为空,根据这个特征来判断是否为叶子结点

根据这个特征可以判断,与上个函数一样,数出左右子树的叶子结点个数加起来即可

int BinTreeLeafSize(BTNode* root)
{
	if (!root)
		return 0;
	return root->left == NULL && root->right == NULL ? 1 : BinTreeLeafSize(root->left) + BinTreeLeafSize(root->right);
}

二叉树求第K层结点个数

这里同样用到分治思想

如果是空树或者到叶子结点的下一层,返回0

如果只有一层的话,也就是只有一个根结点,就返回1

问题转化成求第左子树第k-1层结点个数+右子树第k-1层结点个数

不断往下分解即可,直到求到需要的层数

画图求解

在这里插入图片描述

int BinTreeLevelKSize(BTNode* root, int k)
{
	//返回第K层结点个数
	assert(k >= 0);
	if (!root)
		return 0;
	if (k == 1)
		return 1;
	return BinTreeLevelKSize(root->left, k - 1) + BinTreeLevelKSize(root->right, k - 1);
	
}

二叉树求最大深度

问题分解为求出左右子树中的较大深度+1(这里的+1代表此时的根结点也占1个深度)

为了防止函数调用过多,用变量保存左右子树的深度

int BinTreeDepth(BTNode* root)
{
	if (!root)
		return 0;
	//函数调用频繁
	//return BinTreeDepth(root->left) > BinTreeDepth(root->right) ? 1 + BinTreeDepth(root->left) : 1 + BinTreeDepth(root->right);

	//用变量保存

	int leftDepth = BinTreeDepth(root->left);
	int rightDepth = BinTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

二叉树返回某个指定结点

还是从左右子树中找

如果左右子树没有的话,我们就继续找左右子树的孩子结点,不断往下

BTNode* BinTreeFind(BTNode* root, BTDataType x)
{
	if (!root)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* Left = BinTreeFind(root->left, x);//看这里有没有返回值
	if (Left)
		return Left;
	BTNode* Right = BinTreeFind(root->right, x);
	if (Right)
		return Right;
	return NULL;
}

判断是否为完全二叉树

这里就需要用到层序遍历的知识了

首先我们来复习一下,什么是完全二叉树?

前K-1层是满的,最后一层从左到右结点是连续的

在这里插入图片描述
对它们进行层序遍历的话,你会发现以下特点:

如果中间没有出现空结点顺利的遍历完成,它就是一颗二叉树,反之不是

就拿上图举例

在这里插入图片描述
代码实现

bool BinTreeComplete(BTNode* root)
{
	if (!root)
		return true;
	Quene q;
	QueneInit(&q);
	QuenePush(&q, root);

	while (!QueneEmpty(&q))
	{
		BTNode* front = QueneFront(&q);
		QuenePop(&q);
		if (!front)
			break;//如果出现空了,就跳出循环出剩余元素
		else
		{
			QuenePush(&q, front->left);//这里不管空不空,都要插入
			QuenePush(&q, front->right);
		}
		
	}

	while (!QueneEmpty(&q))
	{
		BTNode* front = QueneFront(&q);
		QuenePop(&q);
		if (front)//如果出现了非空结点
		{
			QueneDestory(&q);
			return false;
		}
	}
	QueneDestory(&q);
	return true;
}

二叉树的销毁

这里需要注意一下顺序问题

如果先销毁跟结点的话,它的左右孩子结点我们就找不到了

所以这里我们需要进行后序遍历来销毁每个结点

void BinTreeDestory(BTNode* root)
{
	if (!root)
		return;
	BinTreeDestory(root->left);
	BinTreeDestory(root->right);
	free(root);
}

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 初阶数据结构——二叉树

一个分享Java & Python知识的社区