【落羽的落羽 数据结构篇】链式结构的二叉树

发布于：2025-02-27 ⋅ 阅读:(8) ⋅ 点赞:(0)

在这里插入图片描述

文章目录

  • 一、链式结构二叉树的结点结构
  • 二、二叉树遍历
    • 1. 前序遍历
    • 2. 中序遍历
    • 3. 后序遍历
    • 4. 层序遍历
  • 三、常见二叉树操作
    • 1. 求二叉树结点个数
    • 2. 求二叉树叶子结点个数
    • 3. 求二叉树第k层结点个数
    • 4. 求二叉树高度
    • 5. 查找值为x的结点
    • 6. 判断二叉树是否是完全二叉树
    • 7. 销毁二叉树

一、链式结构二叉树的结点结构

上一篇我们讲了底层为数组的顺序结构的二叉树，今天我们再来看看链式结构的二叉树——由一个链式结点构成。我们将结点的结构定义为：

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

每一个结点除了存储数据，还有两个指针变量分别指向左孩子和右孩子，如果没有左孩子或右孩子，则为空指针。

本篇文章下面的内容我们都以下面的二叉树为例演示：
在这里插入图片描述

二、二叉树遍历

遍历一棵二叉树，通常可以分为深度优先遍历和广度优先遍历两种方式。我们主要介绍深度优先遍历的前序遍历、中序遍历、后序遍历，以及广度优先遍历的层序遍历。

我们先写一个BuyNode方法用于申请二叉树新结点，创建好上面的二叉树：

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

创建二叉树：

BTNode* creatBinaryTree()
{
	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;
}

1. 前序遍历

前序遍历的定义是：先遍历根结点，再遍历左子树，再遍历右子树。（根左右）

以上面的二叉树为例：

  • 开始遍历，对于以A为根结点的二叉树，先遍历A，再遍历左子树（以B为根结点的二叉树），再遍历右子树（以C为根结点的二叉树）
  • 对于以B为根结点的二叉树，先遍历B，再遍历左子树（以D为根结点的二叉树），再遍历右子树（NULL）
  • 对于以C为根结点的二叉树，先遍历C，再遍历左子树（以E为根结点的二叉树），再遍历右子树（以F为根结点的二叉树）
  • 对于以D、E、F为根结点的二叉树，先遍历D、E、F，再遍历左子树（NULL），再遍历右子树（NULL）

可以看出，这里有一些递归的味道了。所以，我们的前序遍历实现代码为：

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

函数传参为根结点，用到了递归的思想
在这里插入图片描述
（有点抽象，尽量理解，这张概念图前、中、后序遍历都通用）

可以看出，经过前序遍历，我们打印的结果应该是：
A B D NULL NULL NULL C E NULL NULL F NULL NULL

测试：
在这里插入图片描述

2. 中序遍历

中序遍历的定义是：先遍历左子树，再遍历根结点，再遍历右子树。（左根右）

以上面的二叉树为例：

  • 开始遍历，对于以A为根结点的二叉树，先遍历左子树（以B为根结点的二叉树），再遍历A，再遍历右子树（以C为根结点的二叉树）
  • 对于以B为根结点的二叉树，先遍历左子树（以D为根结点的二叉树），再遍历B，再遍历右子树（NULL）
  • 对于以C为根结点的二叉树，先遍历左子树（以E为根结点的二叉树），再遍历C，再遍历右子树（以F为根结点的二叉树）
  • 对于以D、E、F为根结点的二叉树，先遍历左子树（NULL），再遍历D、E、F，再遍历右子树（NULL）

实现方法仍然是递归：

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

测试：
在这里插入图片描述
打印结果确实符合“左根右”的规则

在这里插入图片描述

3. 后序遍历

后序遍历的定义是：先遍历左子树，再遍历右子树，再遍历根结点。（左右根）

以上面的二叉树为例：

  • 开始遍历，对于以A为根结点的二叉树，先遍历左子树（以B为根结点的二叉树），再遍历右子树（以C为根结点的二叉树），再遍历A
  • 对于以B为根结点的二叉树，先遍历左子树（以D为根结点的二叉树），再遍历右子树（NULL），再遍历B
  • 对于以C为根结点的二叉树，先遍历左子树（以E为根结点的二叉树），再遍历右子树（以F为根结点的二叉树），再遍历C
  • 对于以D、E、F为根结点的二叉树，先遍历左子树（NULL），再遍历右子树（NULL），再遍历D、E、F

实现方法仍然是递归：

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

这时我们可以看出，前中后序遍历的实现方法其实是非常相似的。

测试：在这里插入图片描述
结果符合后序遍历的定义

在这里插入图片描述

4. 层序遍历

层序遍历的定义是：从上到下，从左到右依次遍历。对于上面的二叉树，层序遍历的结果应是：A B C D E F（空结点忽略）

实现这一方法，我们可以利用队列的特性——先进先出
思路是：构建一个队列，根结点先入队列。循环判断队列是否为空，不为空则出队头结点并打印，并将队头结点的左右孩子入队列。为空则结束遍历。

我们要用到队列的一些操作，项目中就需要包含之前写过的关于队列的头文件和实现文件。
要注意的是，这个项目中的队列成员类型是二叉树结点，而在Tree.h头文件中，我们已有typedef struct BinaryTreeNode{.......}BTNode;，在Queue.h头文件中，必须有typedef struct BTNode* QDataType;（或typedef struct BinaryTreeNode* QDataType;），要加上struct。因为头文件之间不是相互包含的，Queue.h头文件并不认识在Tree.h中声明的BTNode类型，必须加上struct提醒它这是个自定义结构体类型，才能编译通过：

在这里插入图片描述
在这里插入图片描述

实现代码：

void LevelOrder(BTNode* root)
{
	//创建队列,根结点入队
	Queue q;
	q.phead = q.ptail = NULL;
	QueuePush(&q, root);
	
	while (q.phead != NULL)
	{
		//打印队头结点值，出队头
		BTNode* top = q.phead->data;
		printf("%c ", top->data);
		QueuePop(&q);
		//将队头结点的非空孩子结点入队列
		if (top->left != NULL)
		{
			QueuePush(&q, top->left);
		}
		if (top->right != NULL)
		{
			QueuePush(&q, top->right);
		}
	}
	//队列利用完了就销毁
	QueueDestroy(&q);
}

测试：
在这里插入图片描述
没有问题

在这里插入图片描述

三、常见二叉树操作

我们在第一次介绍二叉树时就提到过，它是递归定义的。不光上面的遍历方法要用到递归思想，下面介绍的大部分其他二叉树操作也要用到递归方法。

1. 求二叉树结点个数

二叉树结点个数 = 根结点（1）+ 左子树结点个数 + 右子树结点个数

int BinaryTreeSize(BTNode* root)
{
    //用static修饰保证每次递归size不被重置
	static int size = 0;
	if (root == NULL)
		return 0;
	size++;
	//计左子树结点数
	BinaryTreeSize(root->left);
	//计右子树结点数
	BinaryTreeSize(root->right);
	return size;
}

/*或：
int size = 0; //将size定义在函数外也可以
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	size++;
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);
	return size;
}*/

/*或：
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}*/

测试：
在这里插入图片描述

2. 求二叉树叶子结点个数

判断叶子结点的依据是：叶子结点的左右孩子都是NULL。
二叉树的叶子结点个数 = 左子树叶子结点个数 + 右子树叶子结点个数

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);
}

测试：
在这里插入图片描述

3. 求二叉树第k层结点个数

同样还是遍历，二叉树第k层结点个数 = 左子树第k-1层结点个数 + 右子树第k-1层个数。

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

测试：
在这里插入图片描述

结果没有问题
在这里插入图片描述

4. 求二叉树高度

二叉树的高度 = 根结点（1）+ 左子树深度和右子树深度中的最大值

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);
}

测试：
在这里插入图片描述

5. 查找值为x的结点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind != NULL)
		return leftFind;

	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind != NULL)
		return rightFind;

	return NULL;
}

测试：

在这里插入图片描述

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

我们讲过，完全二叉树的特点是：除了最后一层外每一层结点数都达到最大，最后一层结点数不一定达到最大，结点从左到右依次排列。
注意到，这个特点和我们上面讲过的层序遍历很像啊，层序遍历是“从上到下，从左到右”。也就是说，层序遍历一棵二叉树时，如果中间都没出现NULL结点，只有结尾是NULL，那它一定是完全二叉树；如果中间出现了NULL结点，而后面还有非空结点，则一定不是完全二叉树。

所以，我们的判断完全二叉树方法是：根结点入队列，队头结点不为空则出队列，将队头结点的左右孩子入队列……如此循环。若中途出结点出到了NULL，则判断队列中的剩余结点，若存在非空结点，则返回false；不存在非空结点返回true。

bool BinaryTreeComplete(BTNode* root)
{
	//创建队列,根结点入队
	Queue q;
	q.phead = q.ptail = NULL;
	QueuePush(&q, root);

	while (q.phead != NULL)
	{
		BTNode* top = q.phead->data;
		QueuePop(&q);
		if (top == NULL) //出到了NULL
		{
			break;
		}
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}

	//判断队列中还存不存在非空结点
	while (q.phead != NULL)
	{
		BTNode* top = q.phead->data;
		QueuePop(&q);
		if (top != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

测试：（我们的二叉树不是完全二叉树）
在这里插入图片描述

在这里插入图片描述

7. 销毁二叉树

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
		return;
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

测试：
注：若传参一级指针，则函数调用后还需手动将实参传入的指针置为NULL，因为函数内只能将形参置为NULL，无法修改实参。这里我们选择传二级指针，就不用再手动将root置NULL了。
在这里插入图片描述

在这里插入图片描述

本篇完，感谢阅读

网站公告

今日签到

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

热门文章

最新发布