树

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

• 有一个特殊的结点，称为根结点，根节点没有前驱结点
• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
  因此，树是递归定义的

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

树的相关概念

• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6

• 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点

• 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点

• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

• 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

• 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

• 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

• 森林：由m（m>0）棵互不相交的树的集合称为森林

树的表示

孩子兄弟表示法

树结构相对线性表比较复杂，存储起来比较麻烦，树既然保存值域，也要保存结点和结点之间
的关系 ，我们采用常用的孩子兄弟表示法 ，即左孩子右兄弟 ，右兄弟是指亲兄弟 ，不是表（堂）兄弟

A 的第一个孩子是B ，A 只指向B ，B的亲兄弟是C ，B指向第一个孩子节点D ，D指向亲兄弟节点E 、F

typedef int DataType;
struct TreeNode
{
struct TreeNode* firstChild1;//第一个孩子节点 

struct TreeNode* pNextBrother;//指向其下一个兄弟节点 
DataType data;

};
1
2
3
4
5
6
7
8
9

特殊的二叉树

满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
说，如果一个二叉树的层数为K，根据等比数列求和 算出 (2^k) - 1 ，则它就是满二叉树

完全二叉树

高度为k的完全二叉树 , 前 k -1 都是满的 ,最后一层要求从左到右是连续的, 满二叉树是一种特殊的完全二叉树 ,完全二叉树节点个数最大是满二叉树的状态 ,个数为(2^k)-1

完全二叉树节点个数最小是前k-1 层的总数再加上第K层的第一个节点 ，前k-1 层的总数是2 ^(k-1) -1 ，所以个数是 2 ^ (k-1 )

二叉树性质

对任何一颗二叉树,如果度为0其叶节点数为n0 ，度为2的分支节点个数为n2 ,则有n0 = n2 +1
度为0的永远比度为2的多一个节点
对于一颗完全二叉树n1要么为0 要么是1

二叉树的顺序结构

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

完全二叉树的值在数组位置中父子下标的关系
parent = (child-1) /2
leftchild = parent *2 +1
rightchild =parent *2 +2

堆

堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

小根堆

树中所有父亲都小于或等于孩子

大根堆

树中所有父亲都大于或等于孩子

堆的实现

堆的初始化

void HeapInit(Heap* php)
{
assert(php);
    php->a = (HeapDataType*)malloc(sizeof(HeapDataType) *4);
if (php->a == NULL)
{
printf("malloc fail");
exit(-1);
}
php->capacity = 4;
php->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

堆向上调整算法（logN)

前提 ： 左右子树必须是大堆或者小堆

向堆中插入数据，需要使用向上调整算法，因为向堆中插入数据是将数据插入到下标为size的位置，插入一个数据，size++,此时可能就不满足小堆（或大堆），因此要对其进行调整

向上调整算法
先将元素插入到堆的末尾,即最后一个孩子之后
从插入的结点位置开始和父节点比较
插入之后如果堆的性质遭到破坏,将新插入的节点顺着双亲往上调整到合适的位置即可

void AdjustUp(HeapDataType* a, int child) //向上调整算法
{
int parent = (child-1)/2; //父子节点下标关系推论
while (child >0 )
{
//大队根
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
//向上调整
child = parent;
parent = (child - 1) / 2;//更新parent
}
//不满足大堆根条件
else
{
break;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

堆的插入

插入一个数据是插入到数组的末尾，即树形结构的最后一层的最后一个结点，插入数据仍然需要保持堆的结构，所以插入数据后需要使用堆的向上调整算法对堆进行调整

void HeapPush(Heap* php, HeapDataType x)
{
assert(php);
if (php->capacity == php->size)
{
//扩容
HeapDataType*  tmp = (HeapDataType *)realloc(php->a, sizeof(HeapDataType) * php->capacity * 2);
//扩容失败
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}

//扩容成功
php->a = tmp;
php->capacity *= 2;

}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

以大堆根为例 ，插入一个60

向下调整算法

前提 ： 左右子树必须是大堆或者小堆

从根节点处开始，选出左右孩子中值较大的孩子
父节点和较大的子节点进行比较, 如果父节点的数据比大的那个孩子结点的数据要小，那就进行交换

在选左右孩子节点较大的时候，我们可以使用假设逻辑 ，假设默认左孩子大于右孩子， 如果左孩子大于右孩子 ，则假设成立 , 如果左孩子小于右孩子 ，重新定义即可

最坏的情况下调整到叶子节点为止
那如何判断是否调整到叶子节点？ 如果调整到叶子节点，也就意味着没有子节点，换句话说就是子节点超出了数组的范围

这里以大堆为例 ,以5为根节点的左右子树，都满足大堆的性质，只有根节点不满足大堆的性质，因此只需要将根节点向下调整到合适的位置，即可形成堆结构

void AdjustDown(HeapDataType* a, int n, int parent) // parent 是下标 , n 是数组元素个数
{
int child = parent * 2 + 1; // 父子节点之间的关系
while (child < n ) //调整到叶子节点结束 ,即超出数组范围
{ 
//以大堆为例 ， 左右孩子比较 ，选出较大值
//假设默认左孩子大于右孩子
if ( child+1<n && a[child + 1] > a[child])  // 右孩子是否存在 ，防止越界
{
child++; 
}
if (a[child] > a[parent])
{

Swap(&a[child], &a[parent]); // 交换
parent = child;
child = parent * 2 + 1; //更新子节点
}
else
{
break; 
}
}
}


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

堆的删除

堆的删除以大堆根为例
如果直接挪动数据 ，时间复杂度为O(N) ，且破化了堆中的父子兄弟关系 ,堆的删除采用向下调整算法

堆的删除其实就是删除堆顶元素(最大的元素）
先将数组末尾的元素与堆顶元素交换，size-- , 堆顶元素就被删除了
删除堆顶数据之后 ，堆的结构就被破坏了 ，使用向下调整算法 ，恢复堆的结构

void HeapPop(Heap* php) // 删除 
{
assert(php);
assert(!HeapEmpty(php));
// 堆顶和数组最后一个元素交换
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--; //删除
//向下调整算法
AdjustDown(php->a, php->size , 0);

}
1
2
3
4
5
6
7
8
9
10
11

拿到堆顶的数据

获取堆顶的数据，即返回数组下标为0的数据

HeapDataType  HeapTop(Heap* php) // 拿到堆顶的数据
{
assert(php);
return php->a[0];
}
1
2
3
4
5

获取堆的数据个数

获取堆的数据个数，即返回堆结构体中的size变量

int HeapSize(Heap* php)// 获取堆的数据个数
{
assert(php);
return php->size;
}

1
2
3
4
5
6

堆是否为空

堆的判空，即判断堆结构体中的size变量是否为0

bool HeapEmpty(Heap* php)  // 堆是否为空
{
assert(php);

return php->size == 0; 
}
1
2
3
4
5
6

完整代码
Test.c

#include"Heap.h"

void TestHeap1()
{
Heap hp;
HeapInit(&hp);
HeapPush(&hp , 70);
HeapPush(&hp, 56);
HeapPush(&hp, 30);
HeapPush(&hp, 25);
HeapPush(&hp, 15);
HeapPush(&hp, 10);
HeapPush(&hp, 20);
HeapPush(&hp, 60);

//打印
int k = 0;
scanf_s("%d",&k);
while (!HeapEmpty(&hp) && k--)
{
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
printf("\n");



}
 void TestHeap2()
{
 Heap hp;
 HeapInit(&hp);
 HeapPush(&hp, 70);
 HeapPush(&hp, 56);
 HeapPush(&hp, 30);
 HeapPush(&hp, 25);
 HeapPush(&hp, 15);
 HeapPush(&hp, 10);
 HeapPush(&hp, 20);
 HeapPush(&hp, 60);

 HeapPop(&hp);
 HeapPop(&hp);
 HeapPop(&hp);

}
 void TestHeap3()
 {
 Heap hp;
 HeapInit(&hp);
 HeapPush(&hp, 70);
 HeapPush(&hp, 56);
 HeapPush(&hp, 30);
 HeapPush(&hp, 25);
 HeapPush(&hp, 15);
 HeapPush(&hp, 10);
 HeapPush(&hp, 20);
 HeapPush(&hp, 60);

int a =  HeapTop(&hp);
int c =  HeapSize(&hp);
 

  }
 void TestHeap4()
 {
 Heap hp;
 HeapInit(&hp); 
 HeapEmpty(&hp);
  }

//int main()
//{
//TestHeap1();
////TestHeap2();
///*TestHeap3();*/
////TestHeap4();
//return 0;
//}
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
71
72
73
74
75
76
77
78
79

---

Heap.c

#include"Heap.h"
void HeapInit(Heap* php)
{
assert(php);
    php->a = (HeapDataType*)malloc(sizeof(HeapDataType) *4);
if (php->a == NULL)
{
printf("malloc fail");
exit(-1);
}
php->capacity = 4;
php->size = 0;
}
void Swap(HeapDataType* p1, HeapDataType* p2)
{
HeapDataType  x = *p1;
*p1 = *p2;
*p2 = x;
}
void AdjustUp(HeapDataType* a, int child) //向上调整算法 ，child 是插入数据下标
{
int  parent = (child-1)/2; //父子节点下标关系推论
while (child >0 )
{
//大堆根
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
//向上调整
child = parent;
parent = (child - 1) / 2;//更新parent
}
//不满足大堆根条件
else
{
break;
}
}
}


void HeapPush(Heap* php, HeapDataType x)
{
assert(php);
if (php->capacity == php->size)
{
//扩容
HeapDataType*  tmp = (HeapDataType *)realloc(php->a, sizeof(HeapDataType) * php->capacity * 2);
//扩容失败
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}

//扩容成功
php->a = tmp;
php->capacity *= 2;

}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size-1);  // php->size-1 是插入数据的下标
}




void AdjustDown(HeapDataType* a, int n, int parent) // parent 是下标 , n 是数组元素个数
{
int child = parent * 2 + 1; // 父子节点之间的关系
while (child < n ) //调整到叶子节点结束 ,即超出数组范围
{ 
//以大堆为例 ， 左右孩子比较 ，选出较大值
//假设默认左孩子大于右孩子
if ( child+1<n && a[child + 1] > a[child])  // 右孩子是否存在 ，防止越界
{
child++; 
}
if (a[child] > a[parent])
{

Swap(&a[child], &a[parent]); // 交换
parent = child;
child = parent * 2 + 1; //更新子节点
}
else
{
break; 
}

}


}
void HeapPop(Heap* php) // 删除 
{
assert(php);
assert(!HeapEmpty(php));
// 堆顶和数组最后一个元素交换
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--; //删除
//向下调整算法
AdjustDown(php->a, php->size , 0);

}

HeapDataType  HeapTop(Heap* php) // 拿到堆顶的数据
{

assert(php);
return php->a[0];
}
int HeapSize(Heap* php)// 获取堆的数据个数
{
assert(php);
return php->size;
}
bool HeapEmpty(Heap* php)  // 堆是否为空
{
assert(php);

/*return php->size == 0; */
if (php->size == 0)
{
return true;
}
else
{
return false;
}
}
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

---

Heap.h

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef int HeapDataType;
typedef struct Heap
{
HeapDataType * a;
int capacity;//存储容量 
int size; //  实际大小
} Heap;

void HeapInit(Heap * php);

void Swap(HeapDataType* p1, HeapDataType* p2);

void AdjustUp(HeapDataType* a, int child); //向上调整算法

void HeapPush(Heap* php, HeapDataType x);

void AdjustDown(HeapDataType* a, int child, int n); 

void HeapPop(Heap* php); // 删除 

HeapDataType  HeapTop(Heap* php);  // 拿到堆顶的数据

int HeapSize(Heap* php); // 获取堆的数据个数

bool HeapEmpty(Heap* php);  // 堆是否为空

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

堆排序

排降序 建立小堆
排升序 建立大堆

升序

向上调整建堆,时间复杂度为O(N* longN)

使用向上调整算法建大堆，将数组建成大堆后,此时堆顶元素是最大的 ，将堆顶元素和最后一个元素进行交换,这样最大的元素就到了数组最后一个元素,对剩下的元素使用向下调整 ， 当下一次向下调整时，我们不管这个处在数组最后一个位置的最大元素（有点类似堆的删除 ），此时第二大的元素来到的堆顶 ，堆顶元素继续与最后一个元素进行交换，（注意第一个交换过去的最大的元素已经不在范围内了） ，依次类推 ，升序就完成了

 void HeapSort(int* a, int n)
 {
 //向上调整建堆
 for (int i = 0; i < n; i++)
 {
 AdjustUp(a, i);
}
 //向下调整排序
 int end = n - 1;// end 是最后一个元素的下标
 while (end > 0)
 {
 Swap(&a[0], &a[end]);
 AdjustDown(a, end, 0);
 end--;
 }
 }
 int main()
 {
 int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3 };
 HeapSort(a, 10);
 return 0; 
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

向下调整建堆的前提是左右子树都是堆 ，从倒数第一个非叶子节点开始倒着调整,如何找到倒数第一个非叶子节点？通过最后一个节点的父节点来找到 , 那为什么要找倒数第一个非叶子节点？ 因为倒数第一个非叶子节点的左右子树都满足大堆或小堆的条件

 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);
 }
 //向下调整排序
 int end = n - 1; //end 是最后一个元素的下标 
 while (end >=0)
 {
 Swap(&a[0], &a[end]);
 AdjustDown(a, end, 0);
 end--;
 }

 }
 int main()
 {
 int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3 };
 HeapSort(a, 10);
 return 0; 
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

建堆时间复杂度

向上调整建堆——O(N*logN)

向下调整建堆—— O(N)

TOP-K问题

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

找N个数中最大的前k个一般建立N个的大堆 ,再Pop K 次就完成了，这种思路适合数据量比较小

如果数据量比较大
前K个数据建一个小堆
遍历剩下的元素，如果这个数据比堆顶的数据大，就将这个数据代替堆顶数据进堆（ 向下调整）
最后小堆的数据就是最大的前K个

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

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

如果你觉得这篇文章对你有帮助，不妨动动手指给点赞收藏加转发，给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力！！！