• 【数据结构】二叉树详解（下篇）

    在这里插入图片描述

    🧑‍💻作者： @情话0.0
    📝专栏：《数据结构》
    👦个人简介：一名双非编程菜鸟，在这里分享自己的编程学习笔记，欢迎大家的指正与点赞，谢谢！

    在这里插入图片描述

    二叉树（下）

    前言

      上一篇文章主要讲解了关于二叉树的概念、性质以及顺序结构的实现，此篇文章将继续完成堆的应用、二叉树的链式结构介绍以及相关操作实现。

    一、堆的应用

    1. 堆排序

      想要完成堆排序，第一步就是要完成建堆，而堆的类型分为大堆和小堆，这两种堆类型对应着不同排序结构，如果要实现从小到大的排序，那么就要建大堆，相反就要建小堆。
      利用堆删除思想来进行排序，建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

      思路： 1）完成建堆，让其拥有父亲结点大于孩子结点的特性（或者父亲结点小于孩子结点）
          2）交换根结点与最后一个孩子结点，那么此时最大的结点就来到了堆的最后一位，将堆的元素个数减一，然后在从根结点（刚交换上去的结点）完成向下调整算法。《注意： 堆的顺序结构是用数组实现的，所以说将堆元素个数减一并不是将其删除，而是将其放在了数组的最后一个位置》
          3）一直持续到最后两个结点将其完成交换即可完成堆排序。

    代码实现：

    void swap(int* left, int* right)
{
	int temp = *left;
	*left = *right;
	*right = temp;
}
//向下调整算法
void AdjustDown(HeapDataType array[], int num, int parent)
{
	int child = parent * 2 + 1;
	while (child < num)
	{
		if (child + 1 < num && array[child] < array[child + 1])
		{
			child ++ ;
		}
		if (array[child]>array[parent])
		{
			swap(&array[child], &array[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapCreat(Heap* h,int arr[],int num)
{
	h->array = (HeapDataType*)malloc(sizeof(HeapDataType)*num);
	memcpy(h->array, arr, sizeof(HeapDataType)*num);
	for (int root = (num - 2) / 2; root >= 0; --root)
	{
		//建堆
		AdjustDown(h->array, num, root);
	}
	//堆排序
	int end = num - 1;
	while (end)
	{
		swap(&h->array[0], &h->array[end]);
		AdjustDown(h->array, end, 0);
		end--;
	}
}


void HeapTest()
{
	Heap h;
	int arr[10] = { 5, 4, 3, 9, 7, 6, 1, 2, 8, 0 };
	int num = sizeof(arr) / sizeof(arr[0]);
	HeapCreat(&h, arr, num);
	for (int i = 0; i < num; i++)
	{
		printf("%d ", h.array[i]);
	}
	printf("\n");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61

    2. TOP-K问题

      TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

      对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

    1. 用数据集合中前K个元素来建堆

    前k个最大的元素，则建小堆；前k个最小的元素，则建大堆

    1. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

    将剩余N-K个元素依次与堆顶元素进行比较，若符合条件进行交换（大堆，小于堆顶元素；小堆，大于堆顶元素），再完成向下调整算法，直到剩余的N-K个元素都已比较完，最后堆中剩余的K个元素就是所求前K个最小或者最大的元素。

    代码实现：（选择十个数字中的前三大，建小堆）

    void Swap(HPDataType* left, HPDataType* right)
{
	HPDataType temp = *left;
	*left = *right;
	*right = temp;
}

void AdjustDown(Heap* hp, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n&&hp->array[child] > hp->array[child + 1])
		{
			child += 1;
		}
		if (hp->array[child] < hp->array[parent])
		{
			Swap(&hp->array[child], &hp->array[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			return;
		}
	}
}

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->array = (HPDataType*)malloc(sizeof(HPDataType)*n);
	if (hp->array == NULL)
	{
		return;
	}
	memcpy(hp->array, a, sizeof(HPDataType)*n);
	hp->size = hp->capacity = n;
	
	//先建小堆（3个元素）
	for (int root = (n - 2) / 2; root >= 0; root--)
	{
		AdjustDown(hp, n, root);
	}
	
	//再将剩余7个元素与根结点比较插入
	for (int i = n; i < 10; i++)
	{
		//取前三大元素，建小堆，大于堆顶元素进行交换，判断，调整
		if (a[i]>hp->array[0])
		{
			Swap(&a[i], &hp->array[0]);
			AdjustDown(hp, 3, 0);
		}
	}
}

void Test()
{
	int arr[10] = { 5, 8, 1, 6, 3, 0, 2, 7, 4, 9 };
	Heap hp;
	HeapCreate(&hp, arr, 3);
	for (int i = 0; i < 3; i++)
	{
		printf("%d ", hp.array[i]);
	}
	printf("\n");

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70

    二、二叉树链式结构的实现

    1.二叉树的结构

    结点类型，包括左右孩子指针以及该结点的数值域

    typedef struct BTNode
{
	struct BTNode* Lchild;
	struct BTNode* Rchild;
	BTNDataType data;
}BTNode;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    在这里插入图片描述

    2.二叉树的遍历

      二叉树的遍历是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问每一次，而且仅访问一次。由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，进而便于遍历。
      由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点 N、左子树L 和右子树R 的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序 (NLR)、中序 (LNR)和后序(LRN)三种遍历算法，其中 “序” 指的是根结点在何时被访问。

    2.1 前序遍历

      访问根结点，先序遍历左子树，先序遍历右子树

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    2.2 中序遍历

      中序遍历左子树，访问根结点，中序遍历右子树

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    2.3 后序遍历

      后序遍历左子树，后序遍历右子树，访问根结点

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    2.4 层序遍历

      除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
      对于目前知识储备，我们只能选择通过队列来完成对二叉树的层序遍历，大致思路就是先将根结点入队，然后在其出队的同时将它的两个孩子结点入队，一直持续到队列为空（当孩子结点为空时不入队）

    主要代码：

    typedef struct BinaryTreeNode* QDataType;

void LeverOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	int leverSize = 0;
	//先入根结点
	if (root != NULL)
	{
		QueuePush(&q, root);
		leverSize = 1;
	}
	while (!QueueEmpty(&q))
	{
		//此处的leverSize记录的是每一行的结点个数
		while (leverSize--)
		{
			//注意：在这里，对头的返回值类型本应该是 int 类型的，但是为了后续的结点访问，
			//要将其强制转化为二叉树结点类型
			BTNode* front = QueueFront(&q);
			printf("%d ", front->data);
			QueuePop(&q);
			if (front->left)
			{
				QueuePush(&q, front->left);
			}
			if (front->right)
			{
				QueuePush(&q, front->right);
			}
		}
		printf("\n");
		leverSize = QueueSize(&q);
	}
	printf("\n");
	QueueDestroy(&q);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    3.二叉树的相关练习

    3.1 二叉树节点个数

      通过全局变量进行计数，每到一个结点就总数++

    //全局变量计数
int size = 0;
int TreeNodeNum(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	size++;
	TreeNodeNum(root->left);
	TreeNodeNum(root->right);
	return size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    3.2 二叉树的高度

      一直递归到最后一层，根据左右子树的高度进行比较加一获取当前结点的高度。

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    3.3 二叉树叶子节点个数

      判断当前结点不为空且左右孩子都为空时就为叶子结点。

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    3.4 二叉树第K层节点个数

      大致思路与叶子节点一样，主要判断条件发生了变化。而是当 K 变成 1 时就计数。

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    3.5 二叉树查找值为x的节点

    BTreeNode* BinaryTreeFind(BTreeNode* root, BTreeNodeType x)
{
	BTreeNode* ret1 = NULL;
	BTreeNode* ret2 = NULL;
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	ret1 = BinaryTreeFind(root->left, x);
	if (ret1)
		return ret1;
	ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
		return ret2;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    3.6 判断二叉树是否是完全二叉树

      大致思路是与层序遍历一致的，同样要使用队列来进行辅助，还是先一层一层的将结点入、出队列，当遇到空结点时停止入队列。然后再判断队列中是否都为空结点，若都是空结点，则为完全二叉树，反之不为完全二叉树。

    int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root != NULL)
	{
		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 0;
		}
	}
	QueueDestroy(&q);
	return 1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    总结

      至此就基本完成了对二叉树的学习，主要还是要明白二叉树的性质，堆的创建、排序和TOPK问题，核心内容就是要明白向下调整算法以及向上调整算法的实现（这些都是建立于二叉树是完全二叉树的基础之上）。再者就是熟悉二叉树的遍历算法，主要是前中后序遍历，层序遍历的实现稍微有点难度，以及二叉树的有关操作（递归实现）。
      感谢您的阅读，若文章存在问题还烦请指出，感觉有帮到你的话还请一键三连。

    在这里插入图片描述

  • 相关阅读:
    UE5.3报错
    SpringBoot Aop使用篇
    hiveSql 相互关注问题
    10道不得不会的JavaEE面试题
    图像篡改检测调研
    Spring MVC中的异常处理
    L79.linux命令每日一练 -- 第11章 Linux系统管理命令 -- sar和chkconfig
    2024年天津中德应用技术大学专升本机械电子工程专业课考试大纲
    Lyapunov稳定性分析2（连续、离散系统）
    前后端分离项目-基于springboot+vue的高校学科竞赛平台的设计与实现（内含代码+文档+报告）
  • 原文地址：https://blog.csdn.net/weixin_47648037/article/details/128111909