数据结构——树

发布于：2025-09-13 ⋅ 阅读:(16) ⋅ 点赞:(0)

目录

1 树的概念与结构

树是一种非线性的数据结构，它是一个由 n 个结点所组成的集合
在这里插入图片描述
在讨论树时，会使用到以下概念：

  • 根结点：位于最上层的结点，比如上图的 1 结点
  • 子树：在当前的树中，规模更小的一棵树，比如上图以 2 为根的树，就是子树
  • 结点的度：一个结点的孩子数量，比如上图的 1 结点，它的度为3，因为它有三个子树
  • 树的度：在树当中，结点拥有的最大的度为树的度，比如上图的树，它的度是 3，因为最大的度是 3
  • 叶结点或终端结点：度为 0 的结点，比如上图的 5，6，3，7，8 结点都是叶节点
  • 分支结点或非终端结点：度不为 0 的结点，比如上图的 1，2，4 结点都是分支结点
  • 父结点或双亲结点：一个结点向上连接的结点被称为父结点，比如上图中 2 是 5 的父结点
  • 兄弟结点：有相同父结点的结点，称为兄弟结点，比如上图中 5 和 6 的父结点都是 2 ，因此它们是父结点
  • 结点所在的层级：在树中，根结点处于第一层，层级从根结点开始起算，向下逐渐加1
  • 树的高度：叶子结点所在的层次为树的高度，比如上图的树，高度是 3
  • 堂兄弟结点：在同一层的结点，比如上图的 5, 8
  • 某结点的祖先：从根结点出发，到某结点为止的路上所经过的所有结点，都是它的祖先，比如上图中，5 的祖先是 2, 1
  • 某结点的子孙：以某结点为根的子树中的其它结点，都是它的子孙，比如上图中，1 的子孙是它以下的所有结点
  • 森林：由一棵及以上的树所组成的集合

在定义树的结构时，经常会使用到左孩子右兄弟的表示方法，也就是，在结点的左侧链接该结点的孩子，在结点的右侧链接该结点的兄弟
结构如下：

typedef int TreeNodeDataType 
struct TreeNode
{
	TreeNodeDataType val;
	struct Tree* child; //孩子结点
	struct Tree* brother; //兄弟结点
}TreeNode;

现在，我们尝试将上面的树转换为这种表示方法：
在这里插入图片描述

2 二叉树的概念和结构

2.1 二叉树

二叉树是一种特殊的树，它的度位于区间 [0, 2] 内，可以是空树
在这里插入图片描述

2.2 完全二叉树

完全二叉树是一种结点连续的二叉树

完全二叉树
在这里插入图片描述

非完全二叉树
在这里插入图片描述

2.3 满二叉树

满二叉树是一种特殊的完全二叉树，它的特征是，最后一层的结点始终是排满的状态

满二叉树
在这里插入图片描述
非满二叉树

在这里插入图片描述

2.4 二叉树的性质

若根节点在第一层，那么非空二叉树的第 i 层上最多有 2(i-1) 个结点

第一层有 20 个结点，第二层有 21 个结点，第三层有 22 个结点，以此类推，那么第 i 层就有 2(i-1) 个结点
在这里插入图片描述

若根节点在第一层，那么高度为 h 的二叉树最多有 2h - 1 个结点

第一层有 20 个结点，第二层有 21 个结点，第三层有 22 个结点，以此类推，那么第 h 层就有 2(h-1) 个结点
将结点数相加，可以得到总结点数 n = 20+ 21 + 22 + … + 2(h-1) ，进行等比数列求和，最终可以得到 n = 2h - 1

一棵有 n 个结点的满二叉树的高度 h = log2（n + 1）

假设满二叉树的高度为 h ，那么它的结点总数 n = 2h - 1，化简可得 h = log2（n + 1）

设一棵二叉树度为 0 的叶子结点有 n0 个，度为 2 的分支结点有 n2 个，可得 n0 = n2+ 1

一棵二叉树中，可能有度为 0 的结点，度为 1 的结点，度为 2 的结点，结点总数就是它们的和
所以可以设度为 0 的叶子结点有 n0 个，度为 1 的分支结点有 n1个，度为 2 的分支结点有 n2 个，总结点数 n = n0 + n1 + n2
同时，结点总数还等于 根节点 + 所有的孩子结点，2 * n2 + 1 * n1 表示除根结点外孩子结点的数量，而 1 则指根节点，因此总结点数 n 还可以表示为 2 * n2 + 1 * n1 + 1
因此， n0 + n1 + n2 = 2 * n2 + 1 * n1 + 1，化简后可得 n0 = n2+ 1

对于一棵完全二叉树，将它的结点从上至下，从左到右按序编号后，编号为 i 的结点有以下性质：
如果该结点有双亲结点，则双亲结点的编号为 (i - 1) / 2
如果该结点有左孩子结点，则左孩子的编号是 2i + 1
如果该结点有右孩子结点，则右孩子的编号是 2i + 2

在这里插入图片描述

2.5 二叉树的存储

二叉树在存储时，可以采用顺序结构，也可以采用链式结构

2.5.1 顺序结构存储

顺序结构存储一般只用来存储完全二叉树，否则会有较大的空间浪费，存储时，按照完全二叉树的编号性质进行操作

顺序结构存储完全二叉树
在这里插入图片描述

顺序结构存储普通二叉树
在这里插入图片描述

2.5.2 链式结构存储

在使用链式结构存储二叉树时，通常使用二叉链表或者三叉链表，较为常用的为二叉链表，它通常会在每个结点中设置一左一右两个指针，左指针用来连接左子树，右指针用来连接右子树

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

在这里插入图片描述

3 树的应用

3.1 堆

3.1.1 堆的概念和结构

堆是通过顺序结构存储的完全二叉树来实现的，在物理结构上是顺序表，在逻辑结构上是二叉树，堆分为两种：小根堆和大根堆
小根堆：父结点的值总是要小于孩子结点的值
大根堆：父结点的值总是要大于孩子结点的值
在这里插入图片描述
堆的结构如下

typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* a; //存储数据的数组
	int size; //有效数据的个数
	int capacity; //容量
}Heap;

接下来，基于小根堆，来说说堆的实现

3.1.2 堆的初始化

与顺序表的初始化相同

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

3.1.3 堆的销毁

与顺序表的销毁相同

void HeapDestroy(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

3.1.4 堆的插入

在插入数据至小根堆时，需要先将该数据插入到堆的末尾，再让它不断地与父结点比较，若该数据比父结点的值小，则需要上升，不断重复这个过程直到上升至根或者比父结点的值大
在这里插入图片描述

void AdjustUp(HeapDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] < a[child]) //小堆：子 < 父,需要调整  大堆：子 > 父，需要调整
		{
			Swap(&a[child], &a[parent]); //交换父子
			child = parent;
			parent = (child - 1) / 2; //定位新的父节点
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* hp, HeapDataType x)
{
	assert(hp);
	if (hp->capacity == hp->size)
	{
		int newCapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
		HeapDataType* tmp = (HeapDataType*)realloc(hp->a, sizeof(HeapDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}

	hp->a[hp->size++] = x;
	AdjustUp(hp->a, hp->size - 1); //调整为小根堆/大根堆
}

3.1.5 堆的删除

虽然堆是使用顺序表来实现的，但是删除时，不能使用顺序表的删除方法，因为会破坏堆的结构
堆在删除时，删除的是堆顶的元素，需要先将堆顶元素与堆底元素交换，删除最后一个元素，再将堆顶元素的左右孩子结点作比较，选出小的那个（小堆），下调堆顶元素，直到不能下调为止
在这里插入图片描述

void AdjustDown(HeapDataType* a, int n, int parent)
{
	while (parent * 2 + 1 < n)
	{
		int child = parent * 2 + 1; //假设较小的为左孩子
		if (child + 1 < n && a[child] < a[child + 1]) //小堆：右子树存在,找左右孩子中较小者  大堆：右子树存在,找左右孩子中较大者
		{
			child = child + 1;
		}

		if (a[parent] < a[child]) //小堆：父 > 子  大堆：父 < 子
		{
			Swap(&a[child], &a[parent]); //交换
			parent = child;
		}
		else
		{
			break;
		}
	}
}

//堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	Swap(&hp->a[0], &hp->a[hp->size - 1]); //交换首尾元素
	hp->size--;
	AdjustDown(hp->a, hp->size, 0); //向下调整
}

3.1.6 获得堆顶数据

由于堆使用顺序表实现，所以堆顶元素就在 0 号下标的位置

//堆顶数据
HeapDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	return hp->a[0];
}

3.1.7 获得堆的数据个数

结构体中的 size 记录了堆的数据个数

//堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}

3.1.8 判空

查看堆的数据个数是否为 0 即可

//判空
int HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

3.2 链式二叉树

3.2.1 链式二叉树的结构

链式二叉树一般采用二叉链表的方式来实现，结点的左侧链接左子树，结点的右侧链接右子树

//二叉链表
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType val;
	struct BinaryTreeNode* left; //左子树
	struct BinaryTreeNode* right; //右子树
}BTNode;

3.2.2 先序遍历

先序遍历遵循 根节点 左子树 右子树 的遍历顺序，但是在遍历树时需要使用递归，所以在访问完左子树时，需要回到根，再去访问右子树，同样的，在访问完右子树后，也需要回到根
在这里插入图片描述

//先序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->val); //根节点
	PreOrder(root->left); //左子树
	PreOrder(root->right); //右子树
}

3.2.3 中序遍历

中序遍历遵循 左子树 根节点 右子树 的遍历顺序，由于是递归实现的，所以在访问完左子树和右子树时，要回到根
在这里插入图片描述

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

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

3.2.4 后序遍历

后序遍历遵循 左子树 右子树 根节点 的遍历顺序
在这里插入图片描述

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

3.2.5 层次遍历

层次遍历是按照树的每一层来进行遍历，比较特殊的是，它不是用递归实现的，而是借助队列来实现的
在层次遍历时，会依次将队头结点出队，并使其的孩子结点入队，直到队列为空，树遍历完成
在这里插入图片描述

void LevelOrder(BTNode* root)
{
	Queue q;

	QueueInit(&q);
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* tmp = QueueFront(&q); //出队头结点
		QueuePop(&q);

		printf("%d ", tmp->val);

		//结点的左右孩子入队
		if (tmp->left)
			QueuePush(&q, tmp->left);
		if (tmp->right)
			QueuePush(&q, tmp->right);
	}

	QueueDestroy(&q);
}

3.2.6 计算结点个数

若一棵二叉树为空树，那么结点个数为 0
若一棵二叉树不是空树，那么结点个数为 左子树的结点个数 + 右子树的结点个数 + 1 （根节点）

int TreeNodeSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	return TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
}

3.2.7 计算叶子结点个数

若一棵二叉树为空树，那么叶子结点个数为 0
若一棵二叉树不是空树，那么叶子结点的个数是 左子树叶子结点个数 + 右子树叶子结点个数

int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	else if (root->left == NULL && root->right == NULL) //是叶子结点
		return 1;

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

3.2.8 计算二叉树第 k 层结点个数

若一棵二叉树为空树，那么结点个数为 0
若 k = 1，那么结点个数为 1 （第一层结点个数）
若 k > 1，就需要将问题转化为计算第 k-1 层的结点个数，第 k-2 层的节点个数 … 第 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);
}

3.2.9 查找值为 x 的结点

若二叉树为空，则一定不会有符合要求的结点，直接返回空即可
若二叉树不为空，那么就需要使用先序遍历，先比对根节点，再查找左子树，再查找右子树，如果该结点位于左子树中，那么就没有必要去右子树中进行查找了，直接返回即可，否则还需要去右子树中查找，若左右都没有，那么返回空即可
在这里插入图片描述

3.2.10 二叉树的销毁

使用后序遍历逐个销毁结点即可

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
		return;

	BinaryTreeDestory(root->left); //释放左子树
	BinaryTreeDestory(root->right); //释放右子树
	free(root); //释放根节点
}

网站公告

今日签到

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

热门文章

最新发布