【数据结构】二叉树链式结构

在这里插入图片描述

🚀write in front🚀
📜所属专栏：初阶数据结构
🛰️博客主页：睿睿的博客主页
🛰️代码仓库：🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
关注我，关注我，关注我，你们将会看到更多的优质内容！！

在这里插入图片描述

文章目录

前言
一.二叉树的理解：
二.二叉树的遍历：
- 创建二叉树：
- 1.前序遍历：
- 2.中序遍历：
- 3.后序遍历：
- 4.层序遍历：
三.判断二叉树是否为完全二叉树：
四.二叉树结点数量：
- - 分治和遍历的区别：
五.二叉树的高度（深度）：
六.二叉树第k层节点个数
总结

前言

在之前的二叉树的顺序结构中我们发现，该二叉树对于堆（一种完全二叉树）非常实用，但是对于非完全二叉树就会出现以下的结构，造成空间浪费：
在这里插入图片描述
所以这里我们还是要通过链式结构来实现二叉树。但是其实普通二叉树是没有什么意义的，增删查改没有多大的意义。真正有意义的是搜索二叉树：

搜索二叉树的特点是左子树比根大/小，右子树比根小/大。这里的二叉树可以用来搜索，也可以用来进行插入，删除等操作，拥有实际的意义。所以对于普通二叉树，我们不用学习他的增删查改，只用学习他的遍历等操作，并且复习一下递归的相关知识。

一.二叉树的理解：

我们先回顾一下回顾下二叉树的概念，二叉树是：

空树
非空：根节点，根节点的左子树、根节点的右子树组成的。

对于一颗二叉树，我们看到它就要把他分为：根，左子树，右子树。对于左子树，在把他分为：根，左子树，右子树。对于右子树，在把他分为：根，左子树，右子树……以此类推直到左右子树都为空才停止。
在这里插入图片描述
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

二.二叉树的遍历：

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的每个节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历。我们以这颗二叉树为例：
在这里插入图片描述

创建二叉树：

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc::fail");
		return;
	}

	node->left = NULL;
	node->right = NULL;
	node->data = x;

	return node;
}


BTNode* CreatTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);


	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node3->right = node7;


	return node1;
}

在这里插入图片描述

1.前序遍历：

前序遍历的顺序是：根，左子树，右子树。

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

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

结果：
在这里插入图片描述

2.中序遍历：

中序遍历的顺序是：左子树，根，右子树。
在这里插入图片描述

代码实现：

void InOrder(BTNode* root)
{

	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

结果：
在这里插入图片描述

3.后序遍历：

后序遍历的顺序是：左子树，右子树，根。
在这里插入图片描述
代码实现：

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

结果：
在这里插入图片描述
其实上面的三种遍历就是通过s三句代码的顺序导致结果的不同，当然他们的递归过程都能用下面这张图来代表：

4.层序遍历：

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历

在这里插入图片描述
那么如何实现层序遍历呢？这里我们就要用到我们之前所学的队列了！
在这里，我们将二叉树的根先进队列，然后将其出队列，每出一次，就让其左右子结点进入队列，随后在出一个队列，将其左右子节点加入队列……这样通过队列的push和pop就能实现层序遍历

在这里插入图片描述

我们首先将队列的代码导入即可，就可以创建队列了：
在这里插入图片描述
代码实现：

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	
	while (!QueueEmpty(&q))
	{
		BTNode* front= QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&q);
}

注意：
这里我们放入队列的不是要打印的数据，而是树结点的指针，为什么呢？如果我们存入的是要打印的数据（整形数据），那么我们无法找到他们的子节点!所以我们每次pop出一个指针，然后push这个指针（结点）的子节点即可。图解如下：
在这里插入图片描述

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

我们先来看看这张图：
在这里插入图片描述
我们会发现，通过层序遍历的方法，满二叉树在层序遍历时的非空结点一定是连续的，空结点也是连续的，所以我们只要在层序遍历的基础上把空结点存入，然后判断空结点是否连续即可。

代码实现：

// 判断二叉树是否是完全二叉树
bool TreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}

	// 判断是不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		// 后面有非空，说明非空节点不是完全连续
		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}

四.二叉树结点数量：

如果我们要计算结点的数量，通过上面所学的遍历的方式当然可以计算出结点数量。
在这里插入图片描述
这就是遍历的方法，但是事实上我们用分治的方法更多一些：

分治和遍历的区别：

拿学校人口统计作为例子，遍历法与分治法的区别如下：

遍历法，做法如下：
校长自己一个人带着一个本子，跑遍全校查人数

分治法，做法如下：
校长想知道人数，就找来院长统计每个院的人数相加，院长找来系主任统计每个系的人数相加……这样校长就不用亲自动手了。其实递归就是把任务交给打工人（呜呜）。
在这里插入图片描述
那么我们如何实现分治法呢？
总体思路就是返回：左子树数量+右子树数量+1
代码实现：

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

五.二叉树的高度（深度）：

在这里要求二叉树的高度，我们也是用分治的思想：

int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
}

其实对于递归内容，我们只需要考虑：

将问题分为子问题，子问题的解决方式和总问题的解决方式的方式一样
有中止的条件

六.二叉树第k层节点个数

现在我们把他分为子问题：

当前树的第k层个数=左子树的第k-1层个数+右子树的第k-1层个数
代码如下：

int TreeKLevel(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	int leftklevel = TreeKLevel(root->left, k - 1);
	int rightklevel = TreeKLevel(root->right, k - 1);

	return leftklevel + rightklevel;
}