堆排序与链式二叉树：数据结构与排序算法的双重探索

d8796d6112a840a89812634c4f357860.gif

大家好，我是小卡皮巴拉

文章目录

目录

引言

一.堆排序

1.1 版本一

核心概念

堆排序过程

1.2 版本二

堆排序函数 HeapSort

向下调整算法 AdjustDown

向上调整算法 AdjustUp

二.链式二叉树

2.1 前中后序遍历

链式二叉树的结构

创建链式二叉树

前序遍历

中序遍历

后序遍历

2.2 链式二叉树的常见操作 

二叉树的结点个数

二叉树叶子结点的个数

二叉树第k层结点的个数

求二叉树的高度/深度

二叉树查找值为x的结点

2.3 层序遍历

使用层序遍历检验是否为完全二叉树

兄弟们共勉 ！！！ 

 

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

d89d34950d1342d5a1e07d45c08f238a.png

引言

在数据结构与算法的广阔天地中，堆排序与链式二叉树无疑是两颗璀璨的明珠。它们各自以其独特的魅力和广泛的应用场景，在数据处理和算法优化中发挥着举足轻重的作用。

堆排序，作为一种基于堆数据结构的比较排序算法，以其高效的排序速度和稳定的性能表现，成为了众多排序算法中的佼佼者。它利用堆的性质，通过一系列精心设计的操作，将无序的数据逐步转化为有序，从而实现了数据的快速排序。

而链式二叉树，则以其灵活的节点连接方式和高效的查找性能，成为了数据结构中不可或缺的一部分。它通过将数据元素组织成二叉树的形式，利用节点的指针域实现数据的动态存储和访问，为数据的查找、插入和删除等操作提供了极大的便利。

今天，我们将一起踏上一段探索之旅，深入剖析堆排序的算法实现与链式二叉树的构建细节。从堆的构建、调整与排序过程，到链式二叉树的节点定义、插入与遍历操作，我们将一步步揭开这两大数据结构的神秘面纱，带你领略它们背后的智慧与魅力。

一.堆排序

1.1 版本一

版本一：基于已有数组建堆、取堆顶元素完成排序版本

void HeapSort(int* arr,int n)
{
    HP hp;
    HPInit(&hp);
    //调用push将数组中的数据建堆
    for (int i = 0; i < n; i++)
    {
	    HPPush(&hp, arr[i]);
    }
    int i = 0;
    while (!HPEmpty(&hp))
    {
	    arr[i++] = HPTop(&hp);
	    HPPop(&hp);
    }
    HPDesTroy(&hp);
}

核心概念

  • 堆：一种特殊的完全二叉树，用于实现堆排序。这里我们假设使用最大堆。

  • 空间复杂度：O(N)，因为使用了额外的堆数据结构。

堆排序过程

  1. 构建堆：

    • 将数组a中的元素逐个添加到堆hp中。

    • 注意：传统堆排序直接在输入数组上构建堆，这里为了教学目的使用了额外的堆结构。

  2. 排序：

    • 当堆不为空时，重复以下步骤：

      • 取出堆顶元素（最大值），将其放到数组a的当前位置。

      • 从堆中移除堆顶元素。

    • 这个过程会持续到堆为空，此时数组a将按降序排列。

  3. 清理：

    • 销毁堆hp，释放任何动态分配的内存。

1.2 版本二

数组建堆，首尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次大的数据

堆排序函数 HeapSort

ab5aea7c4de34a94b3ee05e112f9fa02.png

  1. 函数定义：void HeapSort(int* arr, int n)

    • arr：指向待排序数组的指针。

    • n：数组的长度。

  2. 建堆过程：

    • 循环从最后一个非叶子节点开始（(n - 1 - 1) / 2），逐步向上至根节点（i >= 0），对每个节点调用AdjustDown以确保以该节点为根的子树满足堆性质。

    • 注释中提到的向上调整算法AdjustUp被注释掉了，但其实用向上调整算法也是能够建堆的（但向下调整更为高效）。

  3. 排序过程：

    • 如果要进行升序排序，需要构建最大堆（大堆）；如果要进行降序排序，则需要构建最小堆（小堆）。

    • 通过交换堆顶（当前最大值）与数组末尾元素，并减小堆的大小（end--），然后调用AdjustDown来维护堆的性质，从而实现排序。

    • 这个过程重复进行，直到堆的大小减为1，此时数组已排序完成。

//堆排序
void HeapSort(int* arr, int n)
{
	//根据给定的arr来进行建堆
	//child；n-1 parent:(n-1-1)/2
	//向下调整算法建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}

	//向上调整算法建堆
	/*for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}*/
	//堆排序
	//排升序——建大堆
	//排降序——建小堆
	//建小堆大堆时，主要影响因素在向下调整算法中：
	//1.左孩子和右孩子的比较
	//2.孩子和父亲的比较
	//如果要从构造小堆改为构造大堆，两个判断条件的><都要取反
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}

向下调整算法 AdjustDown

6f573b42e20245b8b8c4b5e0b4d24154.png

83208cf55c2146a58cdf4e9f39707f65.png

a1e0441fce334ab9bda3f1c09fce63e7.png

  1. 函数定义：void AdjustDown(HPDataType* arr, int parent, int n)

    • arr：指向堆数组的指针（这里HPDataType是int）。

    • parent：当前需要调整的父节点索引。

    • n：堆的大小（即当前堆中元素的数量）。

  2. 调整过程：

    • 计算左孩子节点的索引（child = parent * 2 + 1）。

    • 在while循环中，首先检查是否存在右孩子，并且右孩子的值是否小于左孩子的值。如果是，则更新child为右孩子的索引。

    • 接着，比较父节点与孩子节点的值。如果父节点的值大于孩子节点的值（对于最大堆而言），则交换它们，并继续向下调整（更新parent和child）。

    • 如果父节点的值不大于孩子节点的值，则跳出循环，因为当前子树已经满足堆性质。

//向下调整算法
void AdjustDown(HPDataType* arr, int parent,int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//先找最小的孩子
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		//parent和child比较
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

向上调整算法 AdjustUp

c0b378a102d248a1844142cd1d38518c.png

1ace71712b5c41a6a4825fb41b9648f3.png

eed10ac99fef44ee9f7b1aede13c873b.png

函数定义：void AdjustUp(HPDataType* arr, int child)

  • arr：指向堆数组的指针（这里HPDataType是int类型，表示堆中存储的是整数）。

  • child：当前需要向上调整的节点的索引（也称为“孩子”节点）。

调整过程：

  1. 初始化父节点索引：

    • 根据孩子节点索引child，计算出父节点索引parent = (child - 1) / 2。

  2. 循环调整：

    • 当child大于0，并且孩子节点的值大于父节点的值时（对于最大堆）：

      • 交换孩子节点和父节点的值。

      • 更新child为当前父节点的索引。

      • 重新计算新的父节点索引。

  3. 终止条件：

    • 当child不大于0，或者孩子节点的值不大于新的父节点的值时，停止调整。

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		// > 大堆
		// < 小堆 
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

注意事项

  • 注释中提到的向上调整算法AdjustUp函数没有使用，在堆排序中，它通常用于在插入新元素后维护堆的性质，但是此处也是可以使用向上调整算法来建堆的，在这个特定的实现中，由于是从一个无序数组开始构建堆，所以使用向下调整算法AdjustDown更为高效。

  • 堆排序是一种原地排序算法，因为它只需要一个额外的常数空间来存储临时变量（如child、parent等），而不需要额外的数组来存储数据。

  • 建小堆大堆时，主要影响因素在向下调整算法中：
    1.左孩子和右孩子的比较
    2.孩子和父亲的比较
    如果要从构造小堆改为构造大堆，两个判断条件的><都要取反

二.链式二叉树

2.1 前中后序遍历

二叉树的操作离不开树的遍历，我们先来看看二叉树的遍历有哪些方式

遍历规则

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1）前序遍历(PreorderTraversal亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前 访 问顺序为：根结点、左子树、右子树

2）中序遍历(InorderTraversal)：访问根结点的操作发生在遍历其左右子树之中（间） 访问顺序为：左子树、根结点、右子树

3）后序遍历(PostorderTraversal)：访问根结点的操作发生在遍历其左右子树之后 访问顺序为：左子树、右子树、根结点

图解遍历：

以前序遍历为例：370aa0512cd641a398431efdb8837472.png

函数递归栈帧图：

9d4995e328c741a4b2542dfb79cd9abd.png前序遍历结果：1 2 3 4 5 6 

中序遍历结果：3 2 1 5 4 6

后序遍历结果：3 1 5 6 4 1

后面会进行代码的实现

链式二叉树的结构

结构体名称：BTNode

目的：定义二叉树节点。

字段：

  1. BTDataType data;
    • 类型：字符（char的别名BTDataType）
    • 描述：节点值。
  2. BTNode* left;
    • 类型：指向BTNode的指针
    • 描述：左孩子节点。
  3. BTNode* right;
    • 类型：指向BTNode的指针
    • 描述：右孩子节点。

实现代码：

typedef char BTDataType;
//二叉树结点结构的定义
typedef struct BinaryTreeNode
{
	BTDataType data;//当前结点值域
	struct BinaryTreeNode* left;//指向当前结点左孩⼦
	struct BinaryTreeNode* right;//指向当前结点右孩⼦
}BTNode;

创建链式二叉树

函数一：申请新节点

函数名：buyNode

参数：

  • BTDataType x：要存储在新节点中的值。

返回值：

  • 指向新创建的BTNode结构体的指针。

功能：

  • 分配内存以创建一个新的BTNode节点。
  • 检查内存分配是否成功，如果失败则打印错误信息并退出程序。
  • 初始化新节点的值域为参数x。
  • 将新节点的左右孩子指针初始化为NULL。
  • 返回指向新节点的指针。

函数二：手动构造二叉树

函数名：CreateTree

参数：无

返回值：

  • 指向二叉树根节点的指针。

功能：

  • 调用buyNode函数创建六个新节点，分别存储字符'A'到'F'。
  • 设置这些节点之间的父子关系，以构造一个特定的二叉树结构：
    • 'A'是根节点。
    • 'B'和'C'是'A'的左右孩子。
    • 'D'和'E'是'B'的左右孩子。
    • 'F'是'C'的左孩子。
  • 返回指向根节点'A'的指针。

实现代码：

//申请新结点
BTNode* buyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}
//手动构造一颗二叉树
BTNode* CreateTree()
{
	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;
	nodeB->right = nodeE;
	nodeC->left = nodeF;

	return nodeA;
}

前序遍历

函数名：PreOrder

参数：

  • BTNode* root：指向二叉树根节点的指针。

返回值：无

功能：

  • 实现二叉树的前序遍历算法。
  • 前序遍历的顺序是：首先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。

实现细节：

  1. 递归终止条件：如果当前节点（root）为空，则打印"NULL "，并返回。这个条件确保了递归能够正确终止。然而，在标准的前序遍历实现中，通常不会打印"NULL"，因为空节点不产生输出。这里的打印是为了调试或满足特定要求。

  2. 访问根节点：打印当前节点的值（root->data）。

  3. 递归遍历左子树：调用PreOrder函数，传入当前节点的左孩子（root->left）作为参数。

  4. 递归遍历右子树：调用PreOrder函数，传入当前节点的右孩子（root->right）作为参数。

实现代码：

//前序遍历——根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

结合上述创建的链式二叉树，其运行结果为：

1a9c0af73274488caedea0087ba7b84e.png

中序遍历

函数名：InOrder

参数：

  • BTNode* root：指向二叉树根节点的指针。

返回值：无

功能：

  • 实现二叉树的中序遍历算法。
  • 中序遍历的顺序是：首先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。

实现细节：

  1. 递归终止条件：如果当前节点（root）为空，则打印"NULL "（这里的打印是为了便于调试）。

  2. 递归遍历左子树：调用InOrder函数，传入当前节点的左孩子（root->left）作为参数。

  3. 访问根节点：在左子树遍历完成后，打印当前节点的值（root->data）。

  4. 递归遍历右子树：调用InOrder函数，传入当前节点的右孩子（root->right）作为参数。

实现代码：

//中序遍历——左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

打印结果：

c06af63010154135948fb8a8d757537d.png

后序遍历

函数名：PostOrder

参数：

  • BTNode* root：指向二叉树根节点的指针。

返回值：无

功能：

  • 实现二叉树的后序遍历算法。
  • 按照“左子树-右子树-根节点”的顺序访问节点。

实现细节：

  1. 递归终止条件：如果当前节点（root）为空，则按照代码逻辑会打印"NULL "。

  2. 递归遍历左子树：调用PostOrder函数，传入当前节点的左孩子（root->left）作为参数，进行递归后序遍历。

  3. 递归遍历右子树：同样地，调用PostOrder函数，传入当前节点的右孩子（root->right）作为参数，进行递归后序遍历。

  4. 访问根节点：在左右子树都被遍历之后，打印当前节点的值（root->data）。

实现代码：

//后序遍历——左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c", root->data);
}

打印结果:

2096c8829dd24a1e89532795a75120b3.png

2.2 链式二叉树的常见操作 

二叉树的结点个数

函数名：BinaryTreeSize

参数：

  • BTNode* root：指向二叉树根节点的指针。

返回值：

  • int：返回二叉树的节点总数。

功能：

  • 实现计算二叉树节点总数的算法。
  • 递归地计算左子树和右子树的节点数，并将它们与根节点相加得到总节点数。

实现细节：

  • 递归终止条件：如果当前节点（root）为空，则根据二叉树的定义，空树没有节点，返回0。

  • 递归计算左子树节点数：调用BinaryTreeSize函数，传入当前节点的左孩子（root->left）作为参数，递归地计算左子树的节点总数。

  • 递归计算右子树节点数：同样地，调用BinaryTreeSize函数，传入当前节点的右孩子（root->right）作为参数，递归地计算右子树的节点总数。

  • 计算总节点数：将左子树的节点数、右子树的节点数与根节点（1个）相加，得到当前二叉树的总节点数。

实现代码：

//二叉树的结点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//递归
	//每一颗二叉树的结点个数都可以表示为
	//根结点（1）+左子树结点个数+右子树结点个数
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

二叉树叶子结点的个数

函数名：BinaryTreeLeafSize

参数：

  • BTNode* root：指向二叉树根节点的指针。

返回值：

  • int：返回二叉树中叶子节点的总数。

功能：

  • 实现计算二叉树叶子节点总数的算法。
  • 递归地检查每个节点是否为叶子节点，并累加叶子节点的数量。

实现细节：

  • 递归终止条件：如果当前节点（root）为空，则根据二叉树的定义，空树没有叶子节点，返回0。

  • 叶子节点判断：如果当前节点的左孩子（root->left）和右孩子（root->right）都为空，则当前节点是叶子节点，返回1。

  • 递归计算叶子节点数：如果当前节点不是叶子节点，则递归地调用BinaryTreeLeafSize函数，分别传入当前节点的左孩子和右孩子作为参数，计算左子树和右子树的叶子节点总数，并将这两个数相加得到当前二叉树的叶子节点总数。

实现代码：

 

//二叉树叶子结点的个数
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);
}

二叉树第k层结点的个数

函数名：BinaryTreeLevelKSize

参数：

  • BTNode* root：指向二叉树根节点的指针。
  • int k：指定的层数，从1开始计数。

返回值：

  • int：返回二叉树第k层节点的总数。

功能：

  • 实现计算二叉树第k层节点总数的算法。
  • 递归地遍历二叉树，直到达到指定的层数，然后累加该层的节点数。

实现细节：

  • 递归终止条件：
    • 如果当前节点（root）为空，则根据二叉树的定义，该层没有节点，返回0。
    • 如果当前层数k等于1，说明已经到达了根节点所在的层（根节点位于第1层），因此该层有1个节点，返回1。
  • 递归计算第k层节点数：
    • 如果当前节点不是空节点且当前层数k大于1，则递归地调用BinaryTreeLevelKSize函数，分别传入当前节点的左孩子和右孩子作为新的根节点，并将层数k减1（因为向下递归一层），计算左子树和右子树在第k-1层的节点总数。
    • 将左子树和右子树在第k-1层的节点数相加，得到当前二叉树在第k层的节点总数。

注意：

  • 这里的递归逻辑有一点需要注意，即当我们想要计算第k层的节点数时，实际上是递归地去计算左子树和右子树在第k-1层的节点数。这是因为当我们从根节点开始递归时，根节点是第1层，它的子节点（左孩子和右孩子）位于第2层，依此类推。

实现代码：

//二叉树第k层结点的个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1; // 根节点所在层，只有1个节点
	}
	//递归
	//总数：左子树第k-1层结点的个数+右子树第k-1层结点的个数
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

求二叉树的高度/深度

函数名：BinaryTreeDepth

参数：

  • BTNode* root：指向二叉树根节点的指针。

返回值：

  • int：返回二叉树的高度（或深度），即从根节点到最远叶子节点的最长路径上的节点数。

功能：

  • 实现计算二叉树高度的算法。
  • 递归地计算左子树和右子树的高度，并返回其中较大的高度值加上1（根节点的高度）。

实现细节：

  • 递归终止条件：如果当前节点（root）为空，则根据二叉树的定义，空树的高度为0。

  • 递归计算子树高度：分别调用BinaryTreeDepth函数，传入当前节点的左孩子（root->left）和右孩子（root->right）作为参数，递归地计算左子树和右子树的高度。

  • 计算总高度：将左子树的高度（leftDep）和右子树的高度（rightDep）进行比较，取其中较大的值，然后加上1（根节点的高度），得到当前二叉树的总高度。

实现代码：

//求二叉树的高度/深度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//递归计算左子树和右子树的高度
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);
	//返回当前树的高度：根节点的高度（1）加上左右子树中较大的高度
	return 1 + (leftDep > rightDep ? leftDep : rightDep);
}

二叉树查找值为x的结点

函数名：BinaryTreeFind

参数：

  • BTNode* root：指向二叉树根节点的指针。
  • BTDataType x：要查找的目标值，其类型应与二叉树节点的数据类型相匹配。

返回值：

  • BTNode*：返回指向找到的值为x的节点的指针；如果未找到，则返回NULL。

功能：

  • 实现在二叉树中查找值为x的节点的算法。
  • 递归地遍历二叉树，直到找到值为x的节点或遍历完整个树。

实现细节：

  • 递归终止条件：如果当前节点（root）为空，则根据二叉树的定义，该节点下不存在任何子节点，因此返回NULL表示未找到。

  • 查找目标值：如果当前节点的值（root->data）等于目标值x，则找到了目标节点，返回当前节点的指针。

  • 递归查找：

    • 首先，递归地调用BinaryTreeFind函数，传入当前节点的左孩子（root->left）作为新的根节点和相同的目标值x，尝试在左子树中查找目标节点。
    • 如果左子树中找到了目标节点（即leftFind不为NULL），则返回该节点的指针。
    • 如果左子树中没有找到目标节点，则继续递归地调用BinaryTreeFind函数，传入当前节点的右孩子（root->right）作为新的根节点和相同的目标值x，尝试在右子树中查找目标节点。
    • 如果右子树中找到了目标节点（即rightFind不为NULL），则返回该节点的指针。

  • 未找到目标值：如果左子树和右子树中都没有找到目标节点，则返回NULL表示在整个二叉树中未找到值为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)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

2.3 层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1，层序遍历就是从所在二叉树的根结点出发，首先访问第1层的树根结点，然后从左到右访问第2层上的结点，接着是第3层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历，实现层序遍历需要额外借助数据结构：队列

2eef706bacf64ed09b23c32e2604cf30.png

函数名：LevelOrder

参数：

  • BTNode* root：指向二叉树根节点的指针。

功能：

  • 实现二叉树的层序遍历（广度优先遍历），通过队列数据结构辅助完成。

实现细节：

  1. 初始化队列：
    • 创建一个Queue类型的变量q。
    • 调用QueueInit(&q)函数初始化队列q，使其处于可用状态。
  2. 根节点入队：
    • 调用QueuePush(&q, root)函数，将二叉树的根节点root添加到队列q的末尾。
  3. 遍历队列：
    • 使用while循环遍历队列q，条件是队列不为空（!QueueEmpty(&q)）。
    • 在循环体内，首先调用QueueFront(&q)函数获取队列头部的节点指针，并将其赋值给BTNode* top。这里需要注意的是，QueueFront只是获取队列头部的节点指针，并不会将该节点从队列中移除。
    • 紧接着，调用QueuePop(&q)函数从队列中移除刚才通过QueueFront获取的节点（即top指向的节点）。
    • 使用printf("%c", top->data);语句打印当前节点（即top指向的节点）的值。这里假设节点值的数据类型为字符，因此使用%c格式说明符。
  4. 孩子节点入队：
    • 检查当前节点（top）的左孩子是否存在（top->left）。如果存在，则调用QueuePush(&q, top->left);将其添加到队列q的末尾。
    • 同样地，检查当前节点的右孩子是否存在（top->right）。如果存在，则调用QueuePush(&q, top->right);将其添加到队列q的末尾。
  5. 销毁队列：
    • 遍历完成后，调用QueueDestroy(&q)函数销毁队列q，并释放其占用的资源。

代码实现：

//层序遍历
void LevelOrder(BTNode* root)
{
	//借助数据结构——队列
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		printf("%c", top->data);
		//将队头左右孩子入队列(不为空)
		if (top->left)
		{
			QueuePush(&q, top->left);
		}
		if (top->right)
		{
			QueuePush(&q, top->right);
		}
	}
	QueueDestroy(&q);
}

上述是完整的解析，其中用队列实现层序遍历的核心思路如下： 

  1. 初始化队列：
    • 创建一个空队列，用于存储待访问的节点。
  2. 根节点入队：
    • 将二叉树的根节点加入队列。
  3. 循环遍历：
    • 当队列不为空时，执行以下步骤：
      a. 从队列头部取出一个节点（访问该节点，例如打印其值）。
      b. 如果该节点有左孩子，将左孩子加入队列。
      c. 如果该节点有右孩子，将右孩子加入队列。
  4. 结束：
    • 当队列为空时，遍历结束，所有节点都已按层次顺序访问过。

学习了层序遍历，下面我们用层序遍历来检验二叉树是否为完全二叉树

使用层序遍历检验是否为完全二叉树

函数名：BinaryTreeComplete

参数：

  • BTNode* root：指向二叉树根节点的指针。

返回值：

  • bool：如果二叉树是完全二叉树，则返回true；否则返回false。

功能：

  • 该函数通过层序遍历的方式验证给定的二叉树是否为完全二叉树。

实现细节：

  1. 空树处理：
    • 首先检查根节点root是否为NULL。如果是，根据完全二叉树的定义（有时空树也被认为是完全二叉树），函数返回true。
  2. 队列初始化：
    • 创建一个名为q的队列，并调用QueueInit(&q)函数对其进行初始化。
  3. 根节点入队：
    • 将二叉树的根节点root通过QueuePush(&q, root)函数加入队列q。
  4. 遍历与检查：
    • 使用while循环遍历队列q，条件是队列不为空（!QueueEmpty(&q)）。
    • 在循环内部，首先通过QueueFront(&q)函数获取队列头部的节点指针，并将其赋值给BTNode* node。
    • 随后，调用QueuePop(&q)函数将node节点从队列中移除。
    • 使用一个布尔变量met_null来跟踪是否遇到了空节点。如果在遍历过程中遇到了空节点，并且之后还遇到了非空节点，则树不是完全二叉树。
  5. 空节点与非空节点处理：
    • 如果node为空，则将met_null设置为true，表示之后应该只遇到空节点。
    • 如果node不为空，则检查met_null是否为true。如果是，说明在之前已经遇到了空节点，但当前节点却是非空的，因此树不是完全二叉树。在这种情况下，函数会销毁队列并返回false。
    • 如果node不为空且met_null为false，则将node的左右孩子（如果存在）加入队列。
  6. 队列销毁与结果返回：
    • 如果遍历完成后没有违反完全二叉树的性质，则函数销毁队列q，并返回true，表示树是完全二叉树。

 代码实现：

#include <stdbool.h>

// 假设已经定义了BTNode结构体、Queue结构体以及相关的队列操作函数

bool BinaryTreeComplete(BTNode* root) {
    if (root == NULL) {
        // 空树被认为是完全二叉树（根据定义可有所不同，这里假设是）
        return true;
    }

    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    bool met_null = false; // 标记是否遇到了空节点

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

        // 如果已经遇到了空节点，但当前节点不是空，则不是完全二叉树
        if (met_null && node != NULL) {
            QueueDestroy(&q);
            return false;
        }

        // 如果当前节点是空，则设置标记为true，表示之后应该只遇到空节点
        if (node == NULL) {
            met_null = true;
        } else {
            // 否则，将当前节点的左右孩子加入队列
            QueuePush(&q, node->left);
            QueuePush(&q, node->right);
        }
    }

    QueueDestroy(&q);
    return true;
}

简化提炼思路如下：

思路：

  1. 初始化：
    • 使用一个队列来进行层序遍历。
    • 将根节点加入队列。
    • 初始化一个布尔变量 met_null 为 false，用于标记是否遇到了空节点。
  2. 层序遍历：
    • 遍历队列，直到队列为空。
    • 在每次循环中，从队列头部取出一个节点。
    • 如果 met_null 为 true（意味着之前已经遇到了空节点），但当前节点不是空节点，则树不是完全二叉树，返回 false。
    • 如果当前节点是空节点，则将 met_null 设置为 true。
    • 如果当前节点不是空节点，则将其左右孩子（如果存在）加入队列。
  3. 结束条件：
    • 如果遍历结束后没有违反完全二叉树的性质（即没有在遇到空节点后再遇到非空节点），则树是完全二叉树，返回 true。

关键点：

  • 一旦在层序遍历中遇到了空节点，之后的所有节点（如果存在）都应该是空节点，否则树就不是完全二叉树。
  • 使用队列来保持层序遍历的顺序。
  • 使用布尔变量 met_null 来跟踪是否遇到了空节点。

兄弟们共勉 ！！！ 

码字不易，求个三连

抱拳了兄弟们！

cad4eb7aa9fb4624aa20a08056a4030c.gif

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/913280.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【LinuxC编程】06 - 守护进程，线程

【LinuxC编程】06 - 守护进程，线程

进程组和会话 概念和特性 进程组&#xff0c;也称之为作业。BSD于1980年前后向Unix中增加的一个新特性。代表一个或多个进程的集合。每个进程都属于一个进程组。在waitpid函数和kill函数的参数中都曾使用到。操作系统设计的进程组的概念&#xff0c;是为了简化对多个进程的管…
阅读更多...
【MongoDB】MongoDB的聚合(Aggregate、Map Reduce)与管道(Pipline) 及索引详解（附详细案例）

【MongoDB】MongoDB的聚合(Aggregate、Map Reduce)与管道(Pipline) 及索引详解（附详细案例）

文章目录 MongoDB的聚合操作&#xff08;Aggregate&#xff09;MongoDB的管道&#xff08;Pipline操作&#xff09;MongoDB的聚合&#xff08;Map Reduce&#xff09;MongoDB的索引 更多相关内容可查看 MongoDB的聚合操作&#xff08;Aggregate&#xff09; 简单理解&#xff…
阅读更多...
Python的函数（补充浅拷贝和深拷贝）

Python的函数（补充浅拷贝和深拷贝）

一、定义 函数的定义&#xff1a;实现【特定功能】的代码块。 形参&#xff1a;函数定义时的参数&#xff0c;没有实际意义 实参&#xff1a;函数调用/使用时的参数&#xff0c;有实际意义 函数的作用&#xff1a; 简化代码提高代码重用性便于维护和修改提高代码的可扩展性…
阅读更多...
Unity常见问题合集（一）

Unity常见问题合集（一）

PS&#xff1a;不定期更新...... 目录 &#xff08;1&#xff09;无法关闭自动编译&#xff08;Edit — Preference — General — Auto Refresh&#xff09; &#xff08;1&#xff09;无法关闭自动编译&#xff08;Edit — Preference — General — Auto Refresh&#xff0…
阅读更多...
HTB：Sightless[WriteUP]

HTB：Sightless[WriteUP]

目录 连接至HTB服务器并启动靶机 使用nmap对靶机TCP端口进行开放扫描 继续使用nmap对靶机开放的TCP端口进行脚本、服务扫描 首先尝试对靶机FTP服务进行匿名登录 使用curl访问靶机80端口 使用浏览器可以直接访问该域名 使用浏览器直接访问该子域 Getshell 横向移动 查…
阅读更多...
深度学习-神经网络基础-网络搭建-损失函数-网络优化-正则化方法

深度学习-神经网络基础-网络搭建-损失函数-网络优化-正则化方法

一. 神经网络搭建和参数计算 一个继承(nn.model), 两个方法(init, forward) 简介 在pytorch中定义深度神经网络其实就是层堆叠的过程&#xff0c;继承自nn.Module&#xff0c;实现两个方法&#xff1a; init方法中定义网络中的层结构&#xff0c;主要是全连接层&#xff0c;…
阅读更多...
全彩LED显示屏有几种安装方式？

全彩LED显示屏有几种安装方式？

全彩LED显示屏的安装方式多样&#xff0c;根据不同的使用场景和安装环境&#xff0c;可以选择最合适的安装方法。以下是一些常见的全彩LED显示屏安装方式&#xff1a; 室内显示屏安装方式 吊装&#xff1a;适用于室内承重混凝土顶&#xff0c;可以使用标准吊件&#xff0c;吊杆…
阅读更多...
ZISUOJ 2024算法基础公选课练习二

ZISUOJ 2024算法基础公选课练习二

一、前言 先把代码丢上来&#xff0c;后续再补上思路 二、题目总览 三、具体题目 3.1 问题 A: 成绩排序1 参考代码 简单排序 #include <bits/stdc.h> using i64 long long;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int t 1;std::cin >&g…
阅读更多...
阿里云智能语音交互产品试用，基于语音识别、语音合成、自然语言理解

阿里云智能语音交互产品试用，基于语音识别、语音合成、自然语言理解

VER&#xff1a;2024年1月25日 17:29:33 智能语音交互产品基于语音识别、语音合成、自然语言理解 新开通智能语音交互服务用户&#xff0c;可享有3个月免费试用期&#xff0c;试用期间将不会产生费用 智能语音交互产品基于语音识别、语音合成、自然语言理解等技术&#xff0c…
阅读更多...
服务器被攻击排查记录

服务器被攻击排查记录

起因 我的深度学习的所有进程突然被killed&#xff0c;我以为是检修&#xff0c;后面发现好像简单的python代码可以正常运行。但是我的训练进程一启动就会被killed 第一时间没有用htop查看cpu&#xff0c;用top看着挺正常的&#xff0c;但是后面看htop&#xff0c;全是绿的&a…
阅读更多...
安卓好软-----电脑端查看apk全部信息的工具 查看包名 名称以及权限等等

安卓好软-----电脑端查看apk全部信息的工具 查看包名 名称以及权限等等

有时候从网络下载的应用很多是英文。时间久了会忘记到底是什么apk应用。这款工具可以方便的查看apk应用的名称 包名以及各种权限 图标 大小版本号等等。方便用户随时查看 APK Helper能够详细地获得安装包名、软件名称、APK证书、真实版本号、要求的手机版本、系统权限、以及证书…
阅读更多...
算法每日双题精讲——双指针（移动零，复写零）

算法每日双题精讲——双指针（移动零，复写零）

&#x1f31f;快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。 &#x1f31f; 别再犹豫了&#xff01;快来订阅我们的算法每日双题精讲专栏&#xff0c;一起踏上算法学习的精彩之旅吧&#xff01;&#x1f4aa;…
阅读更多...
【SQL】在 SQL Server 中创建数据源是 MySQL 数据表的视图

【SQL】在 SQL Server 中创建数据源是 MySQL 数据表的视图

背景&#xff1a;Windows系统已安装了mysql5.7和sqlServer数据库&#xff0c;现在需要在sqlServer创建视图或者查询来自mysql的数据&#xff0c;视图的数据来源mysql数据库。下面进行实现在sqlserver实现获取mysql数据表数据构建视图。 1、打开 ODBC 数据源管理器&#xff0c;…
阅读更多...
Git 入门篇（一）

Git 入门篇（一）

前言 操作系统&#xff1a;win11 64位 与gitee搭配使用 Git 入门篇&#xff08;一&#xff09; Git 入门篇&#xff08;二&#xff09; Git 入门篇&#xff08;三&#xff09; 目录 git下载、安装与配置 下载 安装 配置 git下载、安装与配置 下载 官网&#xff1a;git-…
阅读更多...
【React】条件渲染——逻辑与运算符

【React】条件渲染——逻辑与运算符

条件渲染——逻辑与&&运算符 你会遇到的另一个常见的快捷表达式是 JavaScript 逻辑与&#xff08;&&&#xff09;运算符。在 React 组件里&#xff0c;通常用在当条件成立时&#xff0c;你想渲染一些 JSX&#xff0c;或者不做任何渲染。 function Item({ nam…
阅读更多...
Ubuntu 的 ROS 操作系统安装与测试

Ubuntu 的 ROS 操作系统安装与测试

引言 机器人操作系统&#xff08;ROS, Robot Operating System&#xff09;是一个用于开发机器人应用的开源框架&#xff0c;它提供了一系列功能丰富的库和工具&#xff0c;能够帮助开发者构建和控制机器人。 当前&#xff0c;ROS1的最新版本为Noetic Ninjemys&#xff0c;专为…
阅读更多...
无人驾驶汽车——AI技术在交通领域的进展与未来展望

无人驾驶汽车——AI技术在交通领域的进展与未来展望

文章目录 前言什么是无人驾驶汽车？特斯拉的无人驾驶愿景无人驾驶的技术进程：从DARPA挑战赛到特斯拉中国无人驾驶技术的现状谷歌的加入与优步的竞争深度学习的到来与特斯拉的独特优势无人驾驶的未来：机遇与挑战总结前言 今天，我想通过讲一个故事，帮助大家更好地理解无人驾…
阅读更多...
MCU面试题

MCU面试题

面试题 1、Crotex-M 处理器才用的架构是"v7" Cortex-M3处理器是基于ARMv7-M架构的处理器&#xff0c;支持更丰富的指令集&#xff0c;包括许多32位指令&#xff0c;这些指令可以高效的使用高位寄存器。另外&#xff0c;M3还支持&#xff1a; 查表跳转指令和条件执行&…
阅读更多...
基于多设计模式下的同步异步日志系统

基于多设计模式下的同步异步日志系统

目录 一、项目介绍 1.1 项目功能 1.2 开发环境 1.3 核心技术 1.4 环境搭建 二、日志系统介绍 2.1 日志系统存在的必要性 2.2 日志系统的技术实现 三、相关技术知识的补充 3.1 不定参函数的使用 3.2 设计模式 四、日志系统框架设计 4.1 模块划分 4.2 模块关系图 …
阅读更多...
C# 选择导入文件的路径、导出文件的路径

C# 选择导入文件的路径、导出文件的路径

通过C#代码&#xff0c;调出windows风格的文件选择对话框和存储文件对话框。提供界面来选择文件的位置&#xff0c;并将完整路径以字符串形式返回。 1、选择导入文件&#xff0c;获取其路径 C#通过这段代码将弹出一个文件选择对话框&#xff0c;允许用户选择一个文件&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023