您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

二叉树(一)

二叉树(一)

1:树的概念和结构

1.1树的概念

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

有一个特殊的结点,称为根结点,根节点没有前驱结点

除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。

每棵子树的根结点有且只有一个前驱,可以有0个或多个后继

因此,树是递归定义的(树可以分成根节点和子树 子树又可以分成相对于该子树的根节点和子树 依次类推)

1.2树和非树的区分

1:树的子树是不相交的

第二种情况 A的子树B和C相交了 这是错误的 树的子树不相交

2:除了根节点外,每个节点有且仅有一个父节点

第二种情况 F的父节点是B和A 这是错误的 每个子节点有且仅有一个父节点

3:一个N个节点的树有N-1条边

第一种情况 一共有9个节点(含根节点) 那么就一共有N-1也就是8条边

第二种情况 一共有9个节点(含根节点) 但是却有N条边 也就是9条边 这是错误的

1.3:树的专业术语

节点的度:一个节点含有的子树的个数称为该节点的度;

如上图所示 相对于A节点 他的子树是B C D 就是他的子树是3个 也就是度是3 相对于E节点 他的子树是H和I 也就是该节点的度是2 (其实也可以看其有多少子节点)

 

叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点

非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等节点为分支节点

如上图所示:H I F G D 这五个节点都没有子节点 也就是其度为0 那么这些节点就叫做叶节点或终端节点 但是 A B C E 这四个节点其度都不为0 也就是其都带有1个或者多个子节点 那么其称为非终端节点或者分支节点

 

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;

如上图所示 A是B和C的父节点 B和C都是A的子节点 B是E的父节点 E是B的子节点   C是G的父节点 G是C的子节点

 

兄弟节点:具有相同父节点的节点互称为兄弟节点;

堂兄弟节点:双亲在同一层的节点互为堂兄弟;

如上图所示 B C D具有相同的父节点A 所以BCD是兄弟节点 E F具有相同的父节点B 所以E F是兄弟节点

H I具有相同的父节点E 所以 H I 是兄弟节点 G的父节点是C 又因为C和B是兄弟节点 所以 E和G F和G 是堂兄弟节点

树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6

如上图

A的子节点是B C D 所以A的度是3

B的子节点是E F 所以B的度是2

C的子节点是G 所以C的度是1

E的子节点是H I 所以E的度是2

最大的度就是A的度3 那么树的度 也就是3

 

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度或深度:树中节点的最大层次; 如上图:树的高度为4

如上图所示

A B E H这条路线的层次是 A~H 也就是4

A B E I 这条路线的层次是A~I 也就是4

A B F这条路线的层次是A~F 也就是3

A C G这条路线的层次是A~G 也就是3

A D这条路线的层次是是A~D 也就是2

树的高度是该树种节点的最大层次 也就是4 那么树的高度或深度就是4

节点的祖先:从根到该节点所经分支上的所有节点;

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。

如上图所示 所有节点都是A节点的子孙 A节点是所有节点的祖先

相对于H节点 E B A都是其祖先

森林:由m(m>0)棵互不相交的树的集合称为森林;

 

1.4:树的例题

 

1.下列关于树的叙述正确的是(D )

A.树中可以有环

B.树的度是指所有结点中度最小的结点的度

C.树的深度指的是结点数最多的那一层的深度

D.树的根结点是所有结点的祖先结点

解析:A选项树不可以有环 因为树的节点不能相交, B树的度是所有节点中度最大的节点的度, C选项 树的深度指的是从根节点到子节点最大层次为树的深度

2.在用树表示的目录结构中,从根目录到任何数据文件,有( A)通道

A.唯一一条

B.二条

C.三条

D.不一定

解析:树不能相交 所以有且只有一条

3.在一颗度为3的树中,度为3的结点有2个,度为2的结点有1个,度为1的结点有2个,则叶子结点有( C)个

A.4

B.5

C.6

D.7

解析:

设度为i的节点个数为ni, 该树总共有n个节点,则n=n0+n1+n2+n3., 有n个节点的树的总边数为n-1条.

根据度的定义,总边数与度之间的关系为:n-1=0*n0+1*n1+2*n2+3*n3.联立两个方程求解,可以得到n0 = n2 + 2n3 + 1,  n0=6

4.一颗拥有1000个结点的树度为4,则它的最小深度是(B )

A.5

B.6

C.7

D.8

解析:一棵树的树度是4 也就是说其节点的度最大为4 那么要求最小的深度 就只能每个节点都达到其最大的度

最小深度也要到第六层

 

1.5:树的表示

实际中树有很多种表示方式,如:双亲表 示法,孩子表示法、孩子兄弟表示法等等。

以下是最常用的孩子兄弟表示法。

typedef int DataType; 
struct Node 
{ 
    struct Node* _firstChild1; // 第一个孩子结点 
    struct Node* _pNextBrother; // 指向其下一个兄弟结点 
    DataType _data; // 结点中的数据域 
};

图解:

2:二叉树

2.1概念

一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树 的二叉树组成。

二叉树的特点:

1. 每个结点最多有两棵子树,即二叉树不存在度大于2的结点。

(每个节点的度可以是0~2 但是一定不能超过2)

2. 二叉树的子树有左右之分,其子树的次序不能颠倒。

2.2特殊的二叉树:

1.满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是 说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。

满二叉树就是除了第k层(如上图所示 k是4) 其余的第一层到第k-1层 每个节点的度都是2 也就是每个节点的子节点都是2 同时 满足总结点树等于(2^k)-1

如上图所示 第一层是2^0个节点 第二层是 2^1个节点 第三层是2^2个节点 第四层是2^3个节点

总结点就是 2^0+2^1+2^2+2^3=15

2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K 的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。

要注意的是满二叉树是一种特殊的完全二叉树。

完全二叉第1层到第k-1层是满足满二叉树的 但是第k层 跟满二叉树不同

要符合完全二叉树 第k层的节点从左到右要是连续的 第一个从左到右是D节点的左子树H D节点的右子树I E节点的左子树J 这是连续的

但是第二个 H I都满足 但是K是E节点的右子树 不连续 所以不是完全二叉树

总结:二叉树是特殊的树 完全二叉树是特殊的二叉树 满二叉树是特殊的完全二叉树

 

2.3 二叉树的性质

1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h- 1.

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0=n2+1

4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=Log2(n+1). (ps:Log2(n+1)是log以2为 底,n+1为对数)

相对于二叉树:

设第一层为1 总深度为h 节点总数为N

最大深度 为N 也就是深度h等于N 也就是我们说的单边树

最小深度 为满二叉树 也就是h = log(N+1)

相对于满二叉树:

设第一层为1 总深度为h 节点总数为N

那么 2^h-1 = N 那么得到h = log(N+1)

相对于完全二叉树

设第一层为1 总深度为h 节点总数为N

则前h-1层为满二叉树,故N满足: 2^(h - 1) - 1 < N <= 2^h - 1

即:2^(h - 1)< N + 1 <= 2^h

两边取对数得:h - 1 < log(n + 1) <= h

可得:log(n + 1) <= h < log(n + 1) + 1

可得:log(n + 1) <= h < log(2(n + 1)) //对数性质log(ab) = log(a) + log(b)

 

5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对 于序号为i的结点有:

1. 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点

2. 若i为某个父节点 则其左孩子坐标为2*i+1 右孩子坐标是2*i+2

 

二叉树例题:

1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为(B)

A 不存在这样的二叉树

B 200

C 198

D 199

解析:因为二叉树的性质 度为0的节点可以表示成度为2的节点+1 所以该题中度为2的节点是199 那么度为0的节点是199+1 = 200

2.下列数据结构中,不适合采用顺序存储结构的是( A)

A 非完全二叉树

B 堆

C 队列

D 栈

解析:A选项非完全二叉树会造成空间浪费 其实队列也不是太好

3.在具有 2n 个结点的完全二叉树中,叶子结点个数为(A)

A n

B n+1

C n-1

D n/2

解析:满二叉树可以看成是一种特殊的完全二叉树 所以度为1的节点只可能是0或者1个 因为度为0的节点又可以表示度为2的节点+1个 所以设度为2的节点是X个 那么 2n = (X)+(X+1)+(1) 或者

2n = (X)+(X+1)+(0) 两个公式分别解的 n=X+1 和 (2n-1)/2 = X 因为节点不可能存在小数 所以只有n=X+1满足 因为X+1等于度为0的节点 所以度为0的节点等于n

4.一棵完全二叉树的节点数位为531个,那么这棵树的高度为(B)

A 11

B 10

C 8

D 12

解析:同理 满二叉树可以看成是一种特殊的完全二叉树 满二叉树的节点是2^k-1个 当k等于9的时候是512个 k等于10的时候是1024个 所以只有k等于10满足

5.一个具有767个节点的完全二叉树,其叶子节点个数为(B)

A 383

B 384

C 385

D 386

解析:同理 完全二叉树度为1的节点只能是0个或者1个 所以设度为2的节点是X个 得到

767 = (X)+(X+1)+(1)或者 767 = (X)+(X+1)+(0) 分别解的 765 = 2X 和 766 = 2X

因为节点数不可能是小数 所以X等于766/2等于383 那么 度为0的节点就是383+1=384

6.下列关于二叉树的叙述错误的是( A  )

A.二叉树指的是深度为 2 的树

B.一个 n 个结点的二叉树将拥有 n-1 条边

C.一颗深度为 h 的满二叉树拥有 2^h-1 个结点(根结点深度为1)

D.二叉树有二叉链和三叉链两种表示方式

解析:二叉树指的是树的度最大为2 而不是深度为2

7.一颗完全二叉树上有1001个结点,其叶子结点的个数是( C)

A.251

B.500

C.501

D.不能确定

解析:同理 完全二叉树度为1的节点只能是0个或者1个 所以设度为2的节点是X个 得到

1001 = (X)+(X+1)+(1)或者 1001 = (X)+(X+1)+(0) 分别解的 999 = 2X 和 1000 = 2X

因为节点数不可能是小数 所以X等于1000/2等于500 那么 度为0的节点就是500+1=501

8.如果在一颗完全二叉树中,某一个结点没有其左孩子,则该结点一定(B )

A.是根结点

B.是叶结点

C.是分支结点

D.在倒数第二层

解析:根据二叉树的性质 对于完全二叉树 其k-1层是完全跟满二叉树相同的 并且完全二叉树在最后一层的子树必须是从左到右连续的 所以 A C D 均错误 只有叶节点存在该情况

9.设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为(C )个

A.11

B.12​

C.13

D.14

解析:度为0的节点是3 那么度为2的节点就是3-2=2 度为1的节点是8 那么总节点就是8+3+2等于13

10.有n个元素的完全二叉树的深度是(  D )

A.nlogn

B.nlogn+1

C.logn

D.logn+1

解析:因为二叉树的节点个数可以看成是 2^k-1 > n n>2^(k-1) 所以 以满二叉树的深度来看 n个元素的满二叉树深度是 2^k-1 = n 2^k = n+1 得到k等于 k = log2^(n+1) 简写成 k = logn+1

11.设某种二叉树有如下特点:每个结点要么是叶子结点,要么有2棵子树。假如一棵这样的二叉树中有m(m>0)个叶子结点,那么该二叉树上的结点总数为( )

A.2m+1

B.2(m-1)

C.2m-1

D.2m

解析:由题解可得 该二叉树是完全二叉树 且不存在度为1的节点 那么总结点=度为0节点+度为2节点

度为0的节点是m 度为2的节点就是m-1 那么总的就是2m-1

12.设根结点的深度设置为1,则一个拥有n个结点的二叉树的深度一定在( A)区间内

A.[logn + 1,n]

B.[logn,n]

C.[logn + 1,n - 1]

D.[logn + 1,n + 1]

解析:一个二叉树有n个节点 如果是最大的深度 那就是除了叶子节点 每个节点的度都为1

最大深度就是n

最小深度就是该二叉树是满二叉树 最小深度是logn+1

13.对任意一颗二叉树,设N0、N1、N2分别是度为0、1、2的结点数,则下列式子中一定正确的是(A)

A.N0 = N2 + 1

B.N1 = N0 + 1

C.N2 = N0 + 1

D.N2 = N1 + 1

解析:对于任意一个二叉树 度为0的节点可以表示成度为2的节点+1

 

2.4 二叉树的存储结构

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构

顺序存储: 顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的 浪费。

而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

使用顺序存储的时候 对于满二叉树和完全二叉树

父亲的下标是i:

那么左孩子下标是:2*i+1 右孩子下标是:2*i+2

孩子的下标是i:

那么父亲的下标是: (i-1)/2

2.41:堆的概念及结构

如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质:

1:堆中某个节点的值总是不大于或不小于其父节点的值;

2:堆总是一棵完全二叉树。

如上所示 是小堆 也就是说 在符合完全二叉树的同时,父节点一定是小于其子节点的

如上所示 是大堆 也就是说 在符合完全二叉树的同时,父节点一定是大于其子节点的

2.42:堆的实现

2.421:堆向下调整算法

现在我们给出一个数组,逻辑上看做一颗完全二叉树。

我们通过从根节点开始的向下调整算法可以把它调整 成一个堆。

小堆向下调整算法有一个前提:左右子树必须是一个小堆,才能调整。

大堆向下调整算法有一个前提:左右子树必须是一个大堆,才能调整。

向下调整法跟堆的高度有关 时间复杂度是O(logN+1)等于O(logN)

数组示例:int a[] = {27,15,19,18,28,34,65,49,25,37};//发现其左右子树是小堆

#if 0
void BigDownAlgor(DataType* a, int Size, int coor)//大堆向上调整算法
{
	assert(a);//断言判断传入的指针的有效性
	int parent = coor;//parent等于传入的根节点坐标
	int child = (coor * 2) + 1;//child等于左孩子坐标

	while (Size > child)//如果子节点坐标大于数组有效元素个数  就结束
	{
		if ((child + 1 < Size) && (a[child + 1] > a[child]))//如果右孩子小于左孩子, 变量child++
		{
			child++;//当前的坐标就是右孩子的坐标
		}

		if (a[parent] < a[child])//如果父节点小于子节点 互换
		{
			SwapHead(&(a[parent]), &(a[child]));
			parent = child;//把互换之后子节点当成父节点
			child = (parent * 2) + 1;//互换之后的子节点等于互换完后父节点*2+1
		}
		else//否则结束循环
		{
			break;
		}
	}
}
#endif

void SmallDownAlgor(DataType* a, int Size, int coor)//小堆向下调整算法
{
	assert(a);//断言判断传入的指针的有效性
	int parent = coor;//parent等于传入的根节点坐标
	int child = (coor * 2) + 1;//child等于左孩子坐标

	while (Size > child)//如果子节点坐标大于数组有效元素个数  就结束
	{
		if ((child+1 < Size) && (a[child + 1] < a[child]))//如果右孩子小于左孩子, 变量child++
		{
			child++;//当前的坐标就是右孩子的坐标
		}

		if (a[parent] > a[child])//如果父节点小于子节点 互换
		{
			SwapHead(&(a[parent]), &(a[child]));
			parent = child;//把互换之后子节点当成父节点
			child = (parent * 2) + 1;//互换之后的子节点等于互换完后父节点*2+1
		}
		else//否则结束循环
		{
			break;
		}
	}
}

小堆向下调整算法图解(大堆向下调整同理 判断父节点是否小于子节点):

如上所示:第一 相对于根节点 红色方块框起来的两个子树都是一个小堆

每次通过比较父节点和其子节点 把该父节点下的子节点中最小的子节点跟其父节点互换 然后把该把子节点的坐标赋值给父节点 重新从赋值之后的父节点对比其子节点 一直到对比完成。

向下调整算法的局限性也就是 从根节点开始 其下的子树必须已经是小堆 如果不是 需要从最后一个叶子节点的父节点开始 依次向上进行向下调整算法

2.422堆的创建

给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算 法,把它构建成一个堆。根节点左右子树不是堆,我们怎么调整呢?(也就是说不能一下子使用向下调整法)这里我们从倒数的第一个非叶子节点的 子树开始调整,一直调整到根节点的树,就可以调整成堆。

操作次数是:n-log(n+1) 即时间复杂度是:O(n)   因为是等差数列*等比数列  所以使用错位相减法得到结果

int a[] = {6, 35, 47, 23, 25, 74, 22};//需要调整的数组

 

 

void CreateArrayToHead(DataType* a, int Size)//把一个不适用向上向下调整的数组变换成适用该算法 从而创建一个堆
{
	int child = Size - 1;//数组最后一个元素的坐标Size-1 也就是说最后一个孩子的坐标是Size-1
	int parent = ((Size - 1)-1)/2;//从孩子坐标求的父亲坐标
	while (parent >= 0)//从最后一个叶节点的父亲节点开始 适用向下调整法进行调整 一直到根节点
	{
		DownAlgor(a, Size, parent);
		parent--;
	}
}

堆的创建图解:

数组Size的大小是7 所以最后一个元素的坐标是6 因为在逻辑上这是一个完全二叉树 所以最后一个是叶子节点 从而该叶子节点的坐标是6

通过公式 该叶子节点的父节点坐标是 (i-1)/2 所以得到最后一个叶子节点的父节点坐标是2

把该父节点当成根节点 作为一棵树 传递给向下调整法进行调整

因为是使用顺序表进行存储堆 所以该父节点减1 得到的是下一个子树的根节点 也就是下一个子树根节点为1的节点 同理 对该子树进行向下调整 依次类推

 

2.43堆的插入删除

# include <stdio.h.>
# include <malloc.h>
# include <string.h>
# include <stdlib.h>
# include <assert.h>

# include "HPH_Head.h"

void SwapHead(DataType *e1, DataType *e2)//互换数组中的两个值
{
	DataType tmp = 0;
	tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
#if 0
/*                      大堆向下调整算法
每经过一次向下调整 都会使得当前的堆符合大堆的特性 并且 堆中最大的元素会到堆顶
*/
void BigDownAlgor(DataType* a, int Size, int coor)
{
	assert(a);//断言判断传入的指针的有效性
	int parent = coor;//parent等于传入的根节点坐标
	int child = (coor * 2) + 1;//child等于左孩子坐标

	while (Size > child)//如果子节点坐标大于数组有效元素个数  就结束
	{
		if ((child + 1 < Size) && (a[child + 1] > a[child]))//如果右孩子小于左孩子, 变量child++
		{
			child++;//当前的坐标就是右孩子的坐标
		}

		if (a[parent] < a[child])//如果父节点小于子节点 互换
		{
			SwapHead(&(a[parent]), &(a[child]));
			parent = child;//把互换之后子节点当成父节点
			child = (parent * 2) + 1;//互换之后的子节点等于互换完后父节点*2+1
		}
		else//否则结束循环
		{
			break;
		}
	}
}
#endif

/*                      小堆向下调整算法
每经过一次向下调整 都会使得当前的堆符合小堆的特性 并且 堆中最小的元素会到堆顶
*/
void SmallDownAlgor(DataType* a, int Size, int coor)
{
	assert(a);//断言判断传入的指针的有效性
	int parent = coor;//parent等于传入的根节点坐标
	int child = (coor * 2) + 1;//child等于左孩子坐标

	while (Size > child)//如果子节点坐标大于数组有效元素个数  就结束
	{
		if ((child+1 < Size) && (a[child + 1] < a[child]))//如果右孩子小于左孩子, 变量child++
		{
			child++;//当前的坐标就是右孩子的坐标
		}

		if (a[parent] > a[child])//如果父节点小于子节点 互换
		{
			SwapHead(&(a[parent]), &(a[child]));
			parent = child;//把互换之后子节点当成父节点
			child = (parent * 2) + 1;//互换之后的子节点等于互换完后父节点*2+1
		}
		else//否则结束循环
		{
			break;
		}
	}
}


void SmallUpAlgor(DataType* a, int Size, int child)//小堆向上调整算法
{
	
	//插入的数据在数组的最末尾 通过child传递过来的最末尾元素的下标 从而找到其父节点的下标
	int parent = (child - 1) / 2;

	//算法原理:如果当前插入节点大于其父节点 那么可以直接插入
	//如果小于其父节点 那么需要跟其父节点交换 因为交换之后 其父节点作为子节点的子树 也会存在变化
	//所以也需要再次进行判断
	while (child>0)
	{
		if (a[parent] > a[child])
		{
			SwapHead(&(a[parent]), &(a[child]));
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
/*
创建一个堆(小堆或者大堆 看算法)
把一个不符合大堆或者小堆的数组 通过多次的变化调整 变成大堆或者小堆
时间复杂度O(n)
*/
void CreateArrayToHead(DataType* a, int Size)
{
	int child = Size - 1;//数组最后一个元素的坐标Size-1 也就是最后一个叶子节点的坐标
	int parent = ((Size - 1)-1)/2;//从孩子坐标求的父亲坐标
	while (parent >= 0)//从最后一个叶节点的父亲节点开始 使用向下调整法(小堆or大堆)进行调整 一直到根节点
	{
		SmallDownAlgor(a, Size, parent);
		parent--;
	}
}

void InitHph(ArrayHead* ps, DataType* a, int Size)//初始化堆空间
{
	assert(ps);//断言判断传入的指针的有效性
	ps->ArrHph = (DataType*)malloc(sizeof(DataType)*Size);//动态开辟一个Size大小的空间
	if (ps->ArrHph == NULL)//判断堆空间是否开辟成功
	{
		printf("%s\n", strerror(errno));
		exit(-1);
	}
	memcpy(ps->ArrHph, a, sizeof(DataType)*Size);//把数组a中的内容拷贝到动态开辟的ArrHph空间中去
	ps->Campity = Size;//堆的容量是Size
	ps->HphTop = Size;//堆的有效元素是Size
}

void PrintHead(ArrayHead* ps)//当前堆元素的输出
{
	assert(ps);//断言判断传入的指针的有效性
	for (int i = 0; i < ps->HphTop; i++)
	{
		printf("%d->", ps->ArrHph[i]);
	}
}

void HeapDestory(ArrayHead* ps)//堆的销毁
{
	assert(ps);//断言判断传入的指针的有效性
	free(ps->ArrHph);//释放动态开辟的数组内存
	ps->ArrHph = NULL;//指针指向置空
	ps->Campity = 0;//堆的容量为0
	ps->HphTop = 0;//堆的有效元素为0
}

DataType HeapTop(ArrayHead* ps)//取堆顶的数据
{
	assert(ps);//断言判断传入的指针的有效性
	if (ps->HphTop == 0)//判断堆是否为空 为空返回-1  不为空返回数组首元素
		return -1;
	else
		return ps->ArrHph[0];
}

void HeapPush(ArrayHead* ps, DataType x)//堆的插入
{
	assert(ps);//断言判断传入的指针的有效性
	if (ps->Campity == ps->HphTop)//判断是否需要增容
	{
		ps->ArrHph = (DataType*)realloc(ps->ArrHph, sizeof(DataType)*(ps->Campity)*2);
		if (ps->ArrHph == NULL)
		{
			printf("%s\n", strerror(errno));
			exit(-1);
		}
	}
	//向上调整法 因为插入是在堆的最末尾(即数组最末尾插入) 所以使用向上调整法 如果是头插的话 因为使用顺序表
	//数组的每个元素都要移动 所以时间复杂度高 不好

	int child = ps->HphTop;//child的坐标等于没插入前的有效元素个数
	ps->ArrHph[child] = x;//把当前要插入的数据放到数组中去
	ps->HphTop++;//有效元素个数加1
	SmallUpAlgor(ps->ArrHph, ps->HphTop, child);//调用向上调整法 最后一个参数是要插入元素的坐标
	//使用向上调整法的目的是 插入数据之后 让堆保持原来的特性 也就是原来是小堆 那就是小堆 原来是大 就是大
}

void HeapPop(ArrayHead* ps)//堆的删除(删除堆顶的数据)
{
	assert(ps);//断言判断传入的指针的有效性
	assert(ps->HphTop > 0);//断言判断堆不为空

	SwapHead(&(ps->ArrHph[0]), &(ps->ArrHph[ps->HphTop-1]));//头尾数据交换 这个时候堆顶的数据到了最末尾
	ps->HphTop--;//数组的有效元素减1 因为本来堆顶的数据到了最末尾 所以减减之后 在最末尾的堆顶数据被删除了
	SmallDownAlgor(ps->ArrHph, ps->HphTop, 0);//使用向下调整法调整一次
	//这里为什么使用向下调整法 因为在互换数据之后 实际上 从根节点的角度看 两个子树还是具有小堆的特性
	//所以使用向下调整 使得删除之后的堆保持原来特性
}

int HeapSize(ArrayHead* ps)//堆的数据个数
{
	assert(ps);//断言判断传入的指针的有效性
	if (ps->HphTop == 0)//如果堆为空 返回0 否则返回有效元素个数 即ps->HphTop
	{
		return 0;
	}
	else
	{
		return ps->HphTop;
	}
}

bool HeapEmpty(ArrayHead* ps)//堆的判空
{
	assert(ps);//断言判断传入的指针的有效性
	if (ps->HphTop == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

堆的插入图解:

该方法是使用针对原来堆是小堆特性的进行插入

堆的删除图解:

1:头尾数据互换之后 原来的堆顶元素就变成到最后的叶子节点

2:因为是使用顺序表进行存储 所以直接有效元素减1 这样原来的堆顶元素就被干掉了

3:原本最末尾的元素现在变成了堆顶 但是在堆中 因为只改变了头尾元素 该堆中的其他子树仍是保持原来堆的特性(即小堆或者大堆) 所以可以直接使用向下调整法进行调整(因为向下调整法的要求之一是树的根节点的子树必须同是大堆或者小堆)

 

2.43堆的排序

要点:

1:排升序(也就是从小到大) 需要使用大堆向下调整法

2:排降序(也就是从大到小) 需要使用小堆向下调整法

#if 0
//方法1:如果有N个元素 那么进行N次堆创建  每创建一次堆 然后Pop一次堆顶 把pop的堆顶的数据依次排列 就是升序或降序的数组
void SortArrayHead(DataType* a, int Size)//堆排序
{
	DataType* b = (DataType*)malloc(sizeof(DataType) * Size);
	if (b == NULL)//判断数组空间是否开辟成功
	{
		printf("%s\n", strerror(errno));
		exit(-1);
	}
	for (int i = 0; i < Size; i++)
	{
		CreateArrayToHead(a, Size);
		b[i] = HeapTop(a);
	}
	//每创建一次堆 那么该堆中所有元素最小的就是堆顶 把堆顶出堆
	//然后堆剩余的元素继续创建堆 出堆 依次类推
	
}
//时间复杂度 O(N*N)
#endif

//方法2:先创建一个堆 然后在循环中 先把堆中的首尾元素互换 然后干掉尾巴元素(即原来的堆顶元素)
//然后使用向下调整法进行调整 使其又变成一个原来特性的堆 继续循环 知道排序完成
void SortArrayHead(DataType* a, int Size)//堆排序
{
	//方法1:如果有N个元素 那么进行N次堆创建  每创建一次堆 然后Pop一次堆顶 把pop的堆顶的数据依次排列 就是升序或降序的数组
	CreateArrayToHead(a, Size);//先进行堆创建(因为使用的是小堆向下调整法 所以最小的在首位)
	int end = Size - 1;
	while (end > 0)//循环遍历数组 降序
	{
		SwapHead(&a[0], &a[end]);//把最小的一个元素放到数组的最后面
		SmallDownAlgor(a, end, 0);//使用小堆向下调整法 注意传递的数组大小是end 也就是把最后一个元素给剔除出来
		end--;//end减1 
	}

}
//操作次数  N+N*logN 时间复杂度O(N*logN)

堆排序方法1升序原理:

每次堆排序 都会创建一个符合堆特性的 然后把堆顶出堆 拷贝给另一个数组 然后依次类推

堆排序方法2降序原理:

先进行堆创建之后 得到数组如下

创建变量end等于Size-1 即end = 6 进入循环

把数组首元素和尾元素交换

使用向下调整法 但是传递的数组有效元素个数是end 也就是6个 剔除了最后一个(最小的)

然后循环条件成立 继续 交换当前数组的倒二元素和第一个元素

这个时候 次二的数字就变到了最后 依次类推 一直遍历完成


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进