菜鸟追梦旅行

这个屌丝很懒，什么也没留下！

热门标签

二叉树的链式结构（二叉树）与顺序结构（堆）---数据结构

作者：菜鸟追梦旅行 | 2024-05-29 12:56:04

踩

一、树的概念与结构

1、树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。我们常把它叫做树，是因为它看起来像一棵倒挂的树，它的根是朝上的，而叶是朝下的。

下面是树的示意图：

(1)-> 在树中有一个特殊的结点，称为根结点，与树的根类似，根结点以前不会再有前驱结点；
(2)-> 除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i =<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，但可以有0个或多个后继节点，因此，一棵树可以看成：根节点+它的子树。就例如上面的这棵树，就可以看成根节点 ' A ' 与左右两颗子树 ' B ' 和 ' C ' 所构成；而 ' B ' 子树又可以看做根节点 ' B ' 与左右子树 ' D ' 与 ' E ' 所构成；' C ' 子树同理。所以这种由大化小的问题可以转换为递归问题，因此树是由递归所定义的。

注意：在树形结构中，子树之间不能有交集，否则就不是树形结构！！！

例如下面的这几棵树就不是树形结构：

总结：

①子树与子树之间不可相交；

②一个有N个节点的树有N-1条边（每个父节点与子节点之间都由一条边所连接）；

③除根节点以为的所有节点，有且只有一个父节点。

2、树的相关概念

1->结点的度：一个结点所含的子树的个数称为该结点的度；如上图：A的有6颗子树，故A的度为6。
2->叶结点或终端结点：度为0的结点称为叶结点；如上图：B、C、H、I、P、Q、....等结点都为叶结点。
3->非终端结点或分支结点：度不为0的结点；如上图：A、D、E、F、G...等结点为分支结点。
4->双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点。

5->孩子结点或子结点：一个结点所含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点。
6->兄弟结点：具有相同父结点的结点互称为兄弟结点；如上图：B、C是兄弟结点。
7->树的度：一棵树中，最大的结点的度称为树的度；如上图：树的度为6（A结点的度）。
8->结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。
9->树的高度或深度：树中结点的最大层次；如上图：树的高度为4。
10->堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为堂兄弟结点。
11->结点的祖先：从根到该结点所经过的分支上的所有结点；如上图：A是所有结点的祖先。
12->子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙。
13->森林：由m（m>0）棵互不相交的树的集合称为森林。

3、树的表示方法

树结构如果用线性表来表示的话就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，在实际中树有很多种表示方式，例如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。


typedef int DataType;
struct Node
{
 struct Node* firstChild1;  // 第一个孩子结点（最左边的孩子节点）
 struct Node* pNextBrother; // 指向其下一个兄弟结点
 DataType data;             // 结点中的数据域
};

4 树在实际中的运用

树在实际中的应用十分广泛，我们现在所使用的手机与电脑都离不开树的功劳，例如Linux中的树状目录结构：

二、二叉树概念及结构

1、二叉树的概念

一颗二叉树是节点的有限集合，若集合为空，表明没有节点；若不为空，则该二叉树由根结点与左子树和右子树组成，当然，这里的左子树与右子树也有可能为空。

二叉树的特点：

1->二叉树不存在度大于2的结点。
2->二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

注意：所有的二叉树结构都是由下面几种情况所复合形成的：

2、特殊的二叉树

1-> 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

满二叉树示意图：

2-> 完全二叉树：完全二叉树是一种效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树，通俗来说，也就是前 K-1 层都与满二叉树中的 K-1层相同，第K层的节点必须是从左向右依次存放。要注意的是满二叉树是一种特殊的完全二叉树。

完全二叉树示意图：

3、二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 $2^{i-1}$ 个结点。

第1层最多有 $2^{0}$ 个结点，第2层最多有 $2^{1}$ 个结点，......第 i 层最多有 $2^{i-1}$ 个结点，以此类推。

2. 若规定根结点的层数为1，则深度为h的二叉树的最大结点数是 : $2^{h}-1$ (深度为h的满二叉树的节点数)。

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 $n_{_{0}}$ , 度为2的分支结点个数为 $n_{_{2}}$ ,则有 $n_{_{0}}$ ＝ $n_{_{2}}$ ＋1。

证明：

设 n0 、 n1 、 n2 分别为度为0、度为1、度为2 的节点个数。

总结点数N：N = n0 + n1 + n2 ①

N个结点的任意二叉树，总共有N-1条边：
* 因为二叉树中每个结点都有双亲，根结点没有双亲，每个节点向上与其双亲之间存在一条边
* 因此N个结点的二叉树总共有N-1条边。

* 因为度为0的结点没有孩子，故度为0的结点不产生边; 度为1的结点只有一个孩子，故每个度为1的结点产生一条边; 度为2的结点有2个孩子，故每个度为2的结点产生两条边，所以总边数为：
N-1 = n1 + 2*n2 ②
* 结合① 和 ②得：n0 + n1 + n2 -1 = n1 + 2*n2
* 即：n0 = n2 + 1

4. 若规定根结点的层数为1，具有n个结点的满二叉树的深度，h = $\log (n+1)$ (ps： $\log (n+1)$
是log以2为底，n+1为对数)。
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，例如：

则对于序号为i的结点有：
1. 若i>0，i位置结点的双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
2. 若2i+1<n，左孩子序号：2i+1；若2i+1>=n则无左孩子
3. 若2i+2<n，右孩子序号：2i+2；若2i+2>=n则无右孩子

4、二叉树的存储结构

二叉树一般使用两种结构存储，一种是顺序结构，另一种是链式结构。

1、顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。在现实中使用中只有堆才会使用数组来存储，二叉树用顺序存储在物理意义上是一个数组，在逻辑意义还上是一颗二叉树。

例如：

完全二叉树（无空间浪费）：

非完全二叉树（有空间浪费）：

2、链式存储

二叉树的链式存储结构是用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法中，链表的每个结点由三个域组成，数据域和左右指针域，左右指针用来找到出该结点的左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都采用的是二叉链，但高阶的数据结构，如红黑树等会用到三叉链。

下面我们分别快来看一下采用二叉链与三叉链的数据存储结构：


typedef int BTDataType;、
 
// 二叉链
struct BinaryTreeNode
{
 struct BinTreeNode* left; // 指向当前结点左孩子 
 struct BinTreeNode* right; // 指向当前结点右孩子
 BTDataType data; // 当前结点值域
}
 
// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* left; // 指向当前结点左孩子
 struct BinTreeNode* right; // 指向当前结点右孩子
 struct BinTreeNode* parent; // 指向当前结点的双亲
 BTDataType data; // 当前结点值域
}；

三、二叉树的顺序结构及实现

1、二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种完全二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是一种数据结构，一个是操作系统中管理内存的一块区域分段。

2、堆的概念及结构

如果有一个集合K = { K0，K1 ，K2 ，…，Kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： $K_{i}\leq K_{2i+1}$ 且 $K_{i}\leq K_{2i+2}$ （即孩子节点小于等于双亲节点）或者 $K_{i}\geq K_{2i+1}$ 且 $K_{i}\geq K_{2i+2}$ （即孩子节点大于等于双亲节点），（i =0， 1，2…，）则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

堆的性质：
1-> 堆中某个结点的值总是大于等于（孩子节点都大于等于父节点，即父节点更小，叫做小堆）或小于等于（孩子节点都小于等于父节点，即父节点更大，叫做大堆）其父结点的值；
2-> 堆总是一棵完全二叉树。

小堆与大堆的示意图：

3、堆的实现

1、堆的定义：


 
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;  // 数组
	int _size;       //元素个数
	int _capacity;   // 容量
}Heap;

2、堆的向上调整算法

首先我们先给出一个数组，在逻辑上将其看做一颗完全二叉树。倘若我们现在的这个数组已经是一个堆（大堆或小堆），我们如果想往堆中插入一个元素，并使新堆依旧保持堆

的性质，那么我们对所插入的元素就需要进行向上调整算法。

int a[] = {15, 18, 19, 25, 28, 34, 65, 49, 27, 37};

下面我们以上面的小堆为例，对新插入的节点进行向上调整算法：

我们将新插入的元素放在二叉树的最后一个节点的位置，并对其进行向上调整。

①我们首先先找到该节点的父节点，如果父节点的值更小，表明现在的新堆依然保持小堆的性质，不需要再进行调整；

②如果父节点的值更大，我们就需要交换新节点与父节点，并计算出下一个父节点的位置；

③如果下一个父节点还存在的话，就需要再次执行 ①② 步骤，直至没有父节点或已经满足小堆的性质。

示意图：

代码实现：


void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
// HPDataType 是一种数据类型的重定义，这里是int 类型
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;   // 先找到新节点的父节点
	while (child > 0)     // child == 0 表明child已经是根节点了，不需要再进行调整
	{
		if (a[child] < a[parent])   // 孩子更小就与父节点交换
		{
			Swap(&a[child], &a[parent]);
			child = parent;           // 交换后的孩子节点来到了父节点的位置
			parent = (child - 1) / 2;   // 再找到下一个父节点
		}
		else    // 孩子节点的值更大就说明以满足小堆的性质，不需要再交换
		{
			break;
		}
	}
}

3、堆的插入

通过上面的向上调整算法的学习，堆的插入也就变得十分的容易了，只需要将数据放在堆的最后，在对其进行向上调整即可。

代码实现：


 
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->_capacity == hp->_size)   // 是否需要扩容
	{
		int NewCapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
		HPDataType* New = (HPDataType*)realloc(hp->_a,sizeof(HPDataType) * NewCapacity);
		if (New == NULL)
		{
			perror("HeapPush:malloc");
			exit(-1);
		}
		hp->_capacity = NewCapacity;
		hp->_a = New;
	}
 
	hp->_a[hp->_size] = x;   // 插入的数据放在最后 
	hp->_size++;
 
	AdjustUp(hp->_a, hp->_size-1); //将插入的元素向上调整
}

4、堆的向下调整算法

学习了向上调整算法后，我们再来看一下向下调整算法。首先我们先给出一个数组，在逻辑上将其看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆，先找它的出孩子节点中较小的一个，在与其进行比较，若根节点的值大于较小孩子的值，就交换他们两个的位置。一直循环此步骤，直至遇到他的孩子节点的值大于该节点的值或者没有孩子节点就停止调整。

以下面这个数组为例：

int array[] = {27,15,19,18,28,34,65,49,25,37};

我们将其看做一个逻辑上的二叉树：

上树的性质恰好满足 向下调整算法，根节点的左右子树都已经是一个小堆了，此时我们只需要向下调整根节点即可将整棵树变成一个小堆，下面来看一下调整示意图：

代码实现：


void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
// HPDataType 是一种数据类型，这里是int类型
void AdjustDown(HPDataType* a, int size,int parent)
{
	int child = 2 * parent + 1;  // 左孩子
	while (child < size)
	{
            // 存在右孩子    并且    右孩子更小
		if ((child + 1) < size && a[child + 1] < a[child])  // 找出左右孩子中较小一个
		{
			child++;
		}
		if (a[parent] > a[child])   // 如果孩子更小就交换，并且更新父节点与孩子节点
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		} 
		else     // 如果父节点更小表明不用再交换了 ，跳出循环
		{
			break;
		}
	}
}

5、堆的创建

通过上面我们学会了向下调整算法，但当根节点的左右子树并不是一个堆时，我们又该如何进行调整呢？其实方法很简单，既然左右子树不是堆，我们就先调整左右子树成为一个堆后，在对根节点进行调整；在调整左右子树时，又可以单独的将左右子树看做一棵树进行向下调整；如果左右子树的子树也不是堆的话，我们就需要先调整左右子树的子树。所以我们既可以得出一个结论：因为单独的一个节点可以将其看做一个堆，所以对于叶子结点，我们不用对其进行向下调整；故我们从第一个非叶子节点开始进行向下调整。

int a[] = {1,5,3,8,7,6};

我们以上面的数组为例，对其进行向下调整使其成为一个大堆：

代码实现：


 
void AdjustDown(HPDataType* a, int size,int parent)
{
	int child = 2 * parent + 1;
	while (child < size)
	{
		if ((child + 1) < size && a[child + 1] > a[child])  // 找出左右孩子中较大一个
		{
			child++;
		}
		if (a[parent] < a[child])   // 如果孩子更大就交换，并且更新父节点与孩子节点
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		} 
		else     // 如果父节点更大表明不用再交换了 ，跳出循环
		{
			break;
		}
	}
}
 
void HeapSort(int* a, int n)
{
 
	for (int i = (n - 1-1) / 2; i >= 0; i--)  // n-1 是最后一个节点，（n-1-1）/2就是第一个非叶子节点
	{
		AdjustDown(a, n,i);
	}
}

6、堆的删除

堆的删除是删除堆顶的数据，先将堆顶的数据与最后一个数据交换，然后再删除数组最后一个数据，但将最后一个数据交换到堆顶后，可能此刻的堆已经被打乱，所以还需要对堆顶的数据进行向下调整算法，使交换后的堆依旧满足堆的性质。

int arr[] = {10, 15, 19, 25, 18, 34, 65, 49, 27, 37, 28};

我们以上面的堆为例，来看一下堆的删除示意图：

代码实现：


 
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size);    // 确保有数据才能进行删除
	hp->_a[0] = hp->_a[hp->_size - 1];   // 将最后一个元素放入堆顶
	hp->_size--; 
 
	AdjustDown(hp->_a, 0, hp->_size);  //将堆顶的数据向下调整
 
}

堆的全部代码实现：


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;
 
// 堆的初始化
void HeapInit(Heap* hp);
 
// 堆的销毁
void HeapDestory(Heap* hp);
 
// 交换两个元素
void Swap(HPDataType* p1, HPDataType* p2);
 
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
 
// 向上调整
void AdjustUp(HPDataType* a, int child);
 
// 堆的删除 (删除堆顶的数据)
void HeapPop(Heap* hp);
 
// 向下调整
void AdjustDown(HPDataType* a, int size,int parent);
 
 
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
 
// 堆的数据个数
int HeapSize(Heap* hp);
 
// 堆的判空
int HeapEmpty(Heap* hp);
 
 
 
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}
 
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}
 
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
// HPDataType 是一种数据类型的重定义，这里是int 类型
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;   // 先找到新节点的父节点
	while (child > 0)     // child == 0 表明child已经是根节点了，不需要再进行调整
	{
		if (a[child] < a[parent])   // 孩子更小就与父节点交换
		{
			Swap(&a[child], &a[parent]);
			child = parent;           // 交换后的孩子节点来到了父节点的位置
			parent = (child - 1) / 2;   // 再找到下一个父节点
		}
		else    // 孩子节点的值更大就说明以满足小堆的性质，不需要再交换
		{
			break;
		}
	}
}
 
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->_capacity == hp->_size)   // 是否需要扩容
	{
		int NewCapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
		HPDataType* New = (HPDataType*)realloc(hp->_a,sizeof(HPDataType) * NewCapacity);
		if (New == NULL)
		{
			perror("HeapPush:malloc");
			exit(-1);
		}
		hp->_capacity = NewCapacity;
		hp->_a = New;
	}
 
	hp->_a[hp->_size] = x;   // 插入的数据放在最后 
	hp->_size++;
 
	AdjustUp(hp->_a, hp->_size-1); //将插入的元素向上调整
}
 
void AdjustDown(HPDataType* a, int size,int parent)
{
	int child = 2 * parent + 1;
	while (child < size)
	{
		if ((child + 1) < size && a[child + 1] > a[child])  // 找出左右孩子中较大一个
		{
			child++;
		}
		if (a[parent] < a[child])   // 如果孩子更大就交换，并且更新父节点与孩子节点
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		} 
		else     // 如果父节点更大表明不用再交换了 ，跳出循环
		{
			break;
		}
	}
}
 
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size);    // 确保有数据才能进行删除
	hp->_a[0] = hp->_a[hp->_size - 1];   // 将最后一个元素放入堆顶
	hp->_size--; 
 
	AdjustDown(hp->_a, 0, hp->_size);  //将堆顶的数据向下调整
 
}
 
// 取出栈顶的数据
 
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->_size);
	return hp->_a[0];
}
 
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}
 
int HeapEmpty(Heap* hp)
{
	assert(hp);
 
	return hp->_size == 0;  // 是空就返回1
}

4、堆的应用

4.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1. 建堆
如果排升序：建大堆；
如果排降序：建小堆；

2. 利用堆删除思想来进行排序

如果我们想要排升序：

①首先我们需要利用上面所讲到的建堆，建立一个有N个数据的大堆；

②再利用堆的删除思想将堆顶的数据（最大）与最后一个数据（下标是N-1）交换，此时我们最大的数据就来到了最后（N-1的位置），这时我们就不用再需要去考虑最后一个元素了，因为最后一个元素已经是最大；

③再对前N-1个数据再次进行堆排序即可。

注意：此刻交换到堆顶的数据并不一定满足大堆的性质，所以还需要对堆顶的数据进行向下调整，使得满足大堆的性质。

int a[] = {20, 17, 4, 16, 5, 3};

下面是对上述数组的排序示意图（蓝色所标记的元素表明不用再考虑）:

代码实现：


 
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void AdjustDown(HPDataType* a, int size,int parent)
{
	int child = 2 * parent + 1;
	while (child < size)
	{
		if ((child + 1) < size && a[child + 1] > a[child])  // 找出左右孩子中较大一个
		{
			child++;
		}
		if (a[parent] < a[child])   // 如果孩子更大就交换，并且更新父节点与孩子节点
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		} 
		else     // 如果父节点更大表明不用再交换了 ，跳出循环
		{
			break;
		}
	}
}
 
void HeapSort(int* a, int n)
{
	// 利用向下调整算法建立一个大堆
	for (int i = (n - 1-1) / 2; i >= 0; i--)  // n-1 是最后一个节点，（n-1-1）/2就是第一个非叶子节点
	{
		AdjustDown(a, n,i);
	}
 
	while(n>1)  //如果数据个数大于1个，才进行排序
	{
		Swap(&a[0], &a[n - 1]);   // 堆顶与最后一个元素进行交换
		n--;           // 每排好一个就不用再考虑最后一个元素，相当与堆的数据减少一个
		AdjustDown(a, n, 0); // 将堆顶的数据向下调整
	}
}

4.2 TOP-K问题

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

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据量太大以至于不能一次性全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
若求前k个最大的元素，则建小堆
若求前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足条件则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

解释：当我们要求数据中最大的前K个时：

①我们需要建立一个K个元素的小堆，这样就保证了堆顶的元素永远是堆中最小的；

②建好小堆以后，我们就可以用后面的 N-K 元素分别来跟堆顶的元素比较，只要发现有元素比堆顶的元素大，就将堆顶的元素替换为该元素；

③再对该元素进行向下调整，再一次找出堆中最小的元素到堆顶；

④一直循环上面的步骤，这样就保证了最大的数据一定会被存储在堆中。

代码实现：


 
void AdjustDown(HPDataType* a, int size,int parent)
{
	int child = 2 * parent + 1;
	while (child < size)
	{
		if ((child + 1) < size && a[child + 1] < a[child])  // 找出左右孩子中较大一个
		{
			child++;
		}
		if (a[parent] > a[child])   // 如果孩子更大就交换，并且更新父节点与孩子节点
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		} 
		else     // 如果父节点更大表明不用再交换了 ，跳出循环
		{
			break;
		}
	}
}
 
 
void PrintTopK(int* a, int n, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	for (int i = (k - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, k, i);
	}
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	for (int i = k; i < n; i++)
	{
		if (a[i] > a[0])  // 如果后面的 N-K 个元素中有大于堆顶元素的，就替换堆定的数据
		{
			a[0] = a[i];
			AdjustDown(a, k, 0); // 将堆顶数据向下调整，保证小堆的性质
		}
	}
     // 前K个元素就是最大的K个元素
	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}
}

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

1、前置说明

在学习二叉树的基本操作前，首先需先要创建一棵二叉树，然后才能学习其相关的基本操作。但二叉树的创建是一个很复杂的过程，下面我们先手动快速创建一棵简单的二叉树，快速进入二叉树操作学习。


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("BuyNode:malloc");
		exit(-1);
	}
	node->_data = x;
	node->_left = node->_right = NULL;
}
 
BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
 
    node1->_left = node2;
    node1->_right = node4;
    node2->_left = node3;
    node4->_left = node5;
    node4->_right = node6;
    return node1;
}

再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：
1. 一颗空树；
2. 非空树：根结点+根结点的左子树+根结点的右子树。

下面是上面我们创建的二叉树示意图：

2、二叉树的遍历

2.1 二叉树的前、中、后序遍历

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

规则：

        1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前(先访问根节点，再访问左节点，再访问右节点)。
        2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）（先访问左节点，再访问根节点，再访问右节点）。
        3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后（先访问左节点，再访问右节点，再访问根节点）。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

代码实现：


// 前序遍历
void BinaryTreePrevOrder(BTNode* root) // 根 -> 左子树 -> 右子树
{
	if (root == NULL)  // 节点为空就返回
		return;
 
	putchar(root->_data); // 不为空就先访问该节点，再访问左节点，最后访问右节点
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
 
// 中序遍历
void BinaryTreeInOrder(BTNode* root) // 左子树 -> 根 -> 右子树
{
	if (root == NULL)// 节点为空就返回
		return;
 
	BinaryTreePrevOrder(root->_left); // 不为空就先访问左节点，再访问该节点，最后访问右节点
	putchar(root->_data);
	BinaryTreePrevOrder(root->_right);
}
 
// 后序遍历
void BinaryTreePostOrder(BTNode* root) // 左子树 -> 右子树 -> 根
{
	if (root == NULL) // 节点为空就返回
		return;
 
	BinaryTreePrevOrder(root->_left); // 不为空就先访问左节点，再访问右节点，最后访问该节点
	BinaryTreePrevOrder(root->_right);
	putchar(root->_data);
}

2.2 二叉树的层序遍历

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

例如下图：访问的结果就是 : A->B->C->D->E->F->G->H->I

那么怎样才能做到这样的效果呢？答案是用“队列”。利用队列先进先出的功能就能很好的实现。

①创建一个空队列，并将第一个节点插入到队列；

②检测队列是否为空，若为空就停止，说明遍历完成；若不为空就出队列的第一个节点，并将该节点的左右节点（左右节点不为空时才入队列）都插入队列（先入左节点，再入右节点）；

③一直循环步骤②，直至队列为空，说明遍历已经完成。

代码实现：


void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;  // 创建一个队列
	QueueInit(&q);  // 队列初始化
	if (root)  // 如果树不为空就将根节点插入队列
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))  // 判断队列是否为空，不为空就继续遍历
	{
		BTNode* front = QueueFront(&q);  // 出队列
		QueuePop(&q);       
 
		printf("%c ", front->_data);  // 访问该节点
 
		if(front->_left)  // 如果存在左子树就插入队列
			QueuePush(&q, front->_left);
 
		if(front->_right)   // 如果存在右子树就插入队列
			QueuePush(&q, front->_right);
	}
	QueueDestroy(&q); // 队列的销毁
}

3、二叉树结点个数以及高度等


// 二叉树的节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL) // 该节点为空就返回 0；
		return 0;
 
	// 该节点不为空就返回  左树的节点个数+右树的节点个数+1；
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
 
 
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL) // // 该节点为空就返回 0;
		return 0;
 
	// 该节点不为空，并且左右子树都为空，说明该节点是叶子结点
	if (root->_left == NULL && root->_right == NULL)
		return 1;
 
	 // 否则返回  左树的叶子结点+右树的叶子结点
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
 
 
// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL) // 如果为空就返回0
		return 0;
 
	if (k == 1) // k == 1,并且该节点不为空，说明该节点属于第K层节点
		return 1;
 
	// 否则返回  左树的K-1层节点+右树的K-1层节点
	return BinaryTreeLevelKSize(root->_left  , k - 1) +
		       BinaryTreeLevelKSize(root->_right, k - 1);
}
 
 
int Max(int x, int y)
{
	return x > y ? x : y;
}
// 二叉树的高度
int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL) //节点为空就返回 0； 
		return 0;
 
	// 否则返回 左子树的高度与右子树的高度的较大值 + 1 
    return Max(BinaryTreeHeight(root->_left), BinaryTreeHeight(root->_right)) + 1;
}
 
 
 
// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)  // 如果该节点为空，说明不在该节点
		return NULL;
 
	if (root->_data == x) // 如果找到了就返回 该节点
		return root;
 
 
	// 否则先在左树找，如果左树找到了，就返回；
	// 左树倘若没找到，就去右树找，并返回右数找到的结果
 
	BTNode* node = BinaryTreeFind(root->_left, x);  //左树找
 
	if(node)   // node 不为空说明找到了
		return node;   // 左树找到了就返回
 
	// 左树没找到就去右树里面找，无论右树找没找到都返回该结果
	return BinaryTreeFind(root->_right, x);  
}

4、二叉树的创建和销毁


// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
// 其中 ‘#’表示空节点
 
                         //数组 a  元素个数 n  元素下标 pi
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	// 如果元素下标超出数组的返回就返回空
	// 1、如果遇到‘#’(空节点）就++下标i，并返回NULL
	if (*pi >= n || a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
 
	// 2、正常情况下
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->_data = a[*pi];
	(*pi)++;   // 每放入一个数据就++下标i；
 
	node->_left = BinaryTreeCreate(a, n, pi);
	node->_right = BinaryTreeCreate(a, n, pi);
 
	return node;
}
 
 
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root)  // 节点不为空
	{
		BinaryTreeDestory(&(*root)->_left);  // 先释放左子树
		BinaryTreeDestory(&(*root)->_right);//再释放右子树
		free(*root); //再释放根节点
		*root = NULL;
	}
}

5、判断二叉树是否是完全二叉树

这里如何判断是否是完全二叉树与上面层序遍历的方法十分类似，大致分为下面几步：

完全二叉树的定义：若某二叉树的高度为 K ，且前 K-1 层是一个满二叉树，第K层的节点从左至右依次存放，则该二叉树是完全二叉树。

说明：完全二叉树前K-2层的节点左右孩子都不为空；第K-1层的节点存在3种情况：

①左孩子右孩子都存在；②左孩子存在，右孩子不存在；③左右孩子都不存在。

示意图：

解题思路：

①创建一个空队列，并将第一个节点插入到队列；

②检测队列是否为空，若为空就停止，说明遍历完成；若不为空就出队列的第一个节点，并将该节点的左右节点（左右节点为空也要入队列）都插入队列（先入左节点，再入右节点）。

③重复步骤②，当出队列的节点为空节点时就结束遍历；若该树满足完全二叉树的结构，则在队列中，该空节点后的所有节点都是空节点；若不满足二叉树结构，则该空节点后一定存在非空节点。

例如上面的完全二叉树出队列时的状态图：

如果在上面的完全二叉树中F节点的左边添加一个节点 “J” ，那么该树就不满足完全二叉树的结构，它的出队列时的状态图将发生改变：

④从该空节点开始，向后访问队列中的各个节点，若队列中还存在不为空的节点，则该树不是完全二叉树；若队列中的节点都为空节点，则说明该树是完全二叉树。

代码实现：


int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)  // 如果取出的节点是空节点就跳出循环
		{
			break;
		}
		QueuePush(&q, front->_left);  // 不是空节点就插入它的左节点与右节点
		QueuePush(&q, front->_right);
	}
 
	while (!QueueEmpty(&q))  // 从第一个空节点往后遍历
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)  // 如果存在不为空的节点，说明不是完全二叉树
		{
			QueueDestroy(&q);
			return 0;
		}
	}
	//  没有非空节点就返回 1
	return 1;
	QueueDestroy(&q);
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/642229