【数据结构初阶-二叉树】非线性数据结构来了

• 求 child:

  • 左孩子：parent * 2 + 1
  • 右孩子：parent * 2 + 2（偶数）

• 求 parent: (child - 1) / 2

  • 左孩子是 (child - 1) / 2
  • 右孩子是 (child - 2) / 2，但右孩子是偶数， (偶数 - 1) / 2 = (奇数 - 1) / 2
  • 所以求父亲位置就可以统一成 (child - 1) / 2

二叉树的顺序结构

普通二叉树并不适合用顺序结构存，但用来存完全二叉树非常舒服

利用顺序结构数组、父/子位置的可计算性，可以实现一种非线性数据结构——堆

堆

堆，一种完全二叉树，遵循堆的性质…

堆的性质

1. 堆，应是完全二叉树

   （数组存储非完全二叉树，空间浪费严重）

2. 堆，每个父节点 大于/小于 其子结点

• 大根堆（大堆）：每个父结点的值，都大于其子结点
• 小根堆（小堆）：每个父结点的值，都小于其子结点

实现

顺序结构实现堆：

1. 按完全二叉树存储
2. 遵循 大堆/小堆 存储
3. 牢握 父子关系计算 这把利器

ps：此处实现的是 小堆

定义

用数组存——物理结构上是数组，逻辑结构上实现的是堆

typedef int HeapDataType;

typedef struct Heap
{
	HeapDataType* arr;//顺序表实现堆
	int size;
	int capacity;
}Heap;
1
2
3
4
5
6
7
8

接口

void HeapInit(Heap* php);

void HeapDestroy(Heap* php);

void HeapPrint(Heap* php);

bool HeapEmpty(Heap* php);

size_t HeapSize(Heap* php);

void AdjustUp(HeapDataType* arr, int child);

void AdjustDown(HeapDataType* arr, int n, int parent);

//尾部插入并向上调整
void HeapPush(Heap* php, HeapDataType x);

//删除堆顶并向下调整
void HeapPop(Heap* php);

HeapDataType HeapTop(Heap* php);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

插入堆尾

：逐个尾插并调整顺序

void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	//检查容量
	if (php->size == php->capacity)
	{
		int newCapacaity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HeapDataType* tmp = (HeapDataType*)realloc(php->arr, newCapacaity * sizeof(HeapDataType));
		if (tmp == NULL)
		{
			perror("HeapPush: realloc");
			exit(-1);
		}

		php->arr = tmp;
		php->capacity = newCapacaity;
	}
	//尾插
	php->arr[php->size] = x;
	php->size++;
	//调整顺序
	AdjustUp(php->arr, 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
24

• arr：要插入的堆

• x：要插入的结点的值

• AdjustUp在后文

删除堆顶

此处是 数组头删，用老思路往前覆盖，行吗？

• 效率低
• 父子关系全乱

于是，找到另一方法，逆置头尾再尾删，也是前面积累下的思路：用栈实现队列的时候，就通过逆置元素顺序，用尾删达到头删效果

void HeapPop(Heap* php)
{
	assert(php);

	Swap(&(php->arr[0]), &(php->arr[php->size - 1]));
	php->size--;

	AdjustDown(php->arr, php->size, 0);
}
1
2
3
4
5
6
7
8
9

• php：堆
• Swap：交换头尾
• AdjustDown在后文

核心算法

为了遵循 大堆/小堆 的顺序，前辈们设计出这样的算法：（假设堆已经建好，算法基于小堆讲解）

向上调整:

• 小堆：child比parent小就往上走
• 大堆：child比parent大就往上走

void AdjustUp(HeapDataType* arr, int child)
{
	assert(arr);

	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;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• arr：要调整的堆
• child：要调整的尾结点（尾插进来的肯定是子结点，不是父结点）
• 循环不能用 (parent >= 0) 控制，如果走到根结点，每次迭代，parent = (0-1)/2 ，永远为 0，死循环

向下调整

• 找小孩子交换（如果不找小的，找了孩子中更大的一个，那调整不彻底，还得倒回来接着调）

void AdjustDown(HeapDataType* arr, int n, int parent)
{
	assert(arr);

	int minChild = parent * 2 + 1;//默认小的是左孩子


	while (minChild < n)//孩子>=n代表走到叶子结点了
	{
        //如果右孩子更小就更正（要检查孩子合法性）
		if (minChild + 1 < n && arr[minChild + 1] < arr[minChild])
		{
			minChild++;
		}

		//parent大就得往下走
		if (arr[parent] > arr[minChild])
		{
			Swap(&arr[parent], &arr[minChild]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		//parent<=minChild就满足小根堆了
		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
28
29

• arr：要删除的堆

• n：堆内元素个数，用来检查孩子下标的合法性

• parent：要向下调整的结点（根结点，肯定是父结点而不是子结点）

• 务必检查 孩子（下标）的合法性（孩子>n代表走到叶子结点了）

• 若是大堆，找大孩子交换即可

剩下的接口在之前的顺序表实现里讲过

堆排序

堆排序！时间复杂度 O(N*logN) ！

ok，直接调用堆的插入接口，插一个排一个就好了……吗？

想想，如上面所做的话

1. 每次实现堆排序都要实现个堆出来，堆实现好了堆排序早就出来了（麻烦）
2. 对数组本身排序，要拷贝数据到堆，排序完再拷贝回数组，空间复杂度 O(N)

这两个问题能不能解决掉？那就原地建堆！

但怎么建呢…好好想想之前是怎么建的

thinking…

…

…

…

…

…

…

…

…

…

原来的建堆，是插入+调整，这里原地建堆不用插入了， 调整结点就完事。

建堆

向上调整建堆

：模拟插入建堆，遍历整个数组，逐个调整

void HeapSort(int* arr, int n)
{
	assert(arr);
    
	//向上调整建堆
	int i = 1;
	for (i = 1; i < n; i++)
	{
		AdjustUp(arr, i);
	}
}
1
2
3
4
5
6
7
8
9
10
11

• i = 1：把第0个结点当作根，调整 叶子结点，从第一个到最后一个，模拟从插入建堆

向下调整建堆

：向下调整必须保证 子树是堆（子树不是堆，调整了也不能保证到正确位置）

• 从根开始向下调整？但并不能保证子树是堆啊
• 从最后一棵子树（叶子结点）开始调呗！但…叶子结点需要向下调整嘛…显然不需要。
• 所以从 **最后一个非叶子结点（最后一个叶子结点的父结点）**开始 向下调整：
  • 叶子结点如果作父节点，单个结点即是堆，所以从叶子结点的上一层开始调整，就满足 向下调整子树是堆 的条件。
  • 每次调完往根走（往前走，依然满足子树是堆），一颗颗子树全部调完，就是堆了。

ps：此处仅演示要调整子树的顺序

void HeapSort(int* arr, int n)
{
	assert(arr);
    
	//向下调整建堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}
}
1
2
3
4
5
6
7
8
9
10
11

• i = (n - 1 - 1) / 2：最后一个结点位置是 n-1，其父结点则是 ( (n-1) - 1 ) / 2

两种方法都成功建出小堆

用哪种嘞？

向上向下调整的区别

：时间复杂度

向下调整的时间复杂度

• 随着 结点增多，需要调整的层数减少
• 最后一层不用调整（最后一层的结点占总结点数量的一半）
• 时间复杂度为 O(N)

向上调整的时间复杂度

• 随着结点增多，需要调整的层数增多
• 最后一层也要调整（最坏情况，最后一层全都依次要调到堆顶，效率就低了）
• 时间复杂度为 O(N*logN)

所以咱们堆排序中的建堆，选向下调整，时间复杂度为 O(N)。

排序

建堆解决了，建什么堆——排升序，建什么堆；排降序，建什么堆？

直觉告诉我们，升序小的排前面，建小堆；降序大的排前面，建大堆。

1. 建小堆，排升序：

• 小堆取到最小，第一个数据排好

• 除掉“最小”，剩下的看作堆

• …

​ 惊奇地发现，父子关系全乱了：想要再取次小/次大，只能重新建堆。再次建堆相当于每次都要遍历…效率不如直接遍历，那只能

2. 建大堆排升序：

• 大堆取到最大，把“最大”和尾部元素交换（升序要求从前小后大，这样相当于排好尾部的数）
• 除掉放后面的“最大”，剩下看作堆
• 将换到堆顶的元素向下调整，选出次大
• 如此类推将前N-1个排好，剩下的最后一个已经是有序，即堆排序完成

​ 逆向思维，不取小的排前面，取大的放后面也一样！

结合代码理解

void HeapSort(int* arr, int n)
{
	assert(arr);
	
    //1. 建堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}

	//选择排序：
	// 大堆 排升序 ：每次得到 最大的值，和最后位置交换（按升序排好了一个），再向下调整建堆，最后把尾部元素视作堆外元素
	// 小堆 排降序 ：每次得到 最小的值，和最后位置交换（按降序排好了一个），再向下调整建堆，最后把尾部元素视作堆外元素
	// 小堆 排降序
    
    //2. 选数（排序）
	i = 1;//使N个数有序，只需要排N-1次，最后一个自然有序
	while (i < n)
	{
		Swap(&arr[0], &arr[n - i]);
		AdjustDown(arr, n - i, 0);//调整完一次，视作堆的元素就少一个
		i++;
	}
    
}
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

优雅地，我们完成了 O(N*logN) 的堆排序

TopK

：找出前K个 最大/最小 的数

如何处理?

thinking…

…

…

…

…

…

…

…

…

…

如果现在我们要找 N个数 里 前K个最大的，怎么做？

1. 排序 – O(N*logN)：排完降序取前K个

   void PrintTopK()
   {
   	//求前K大
   	//排降序后，前K个就是前K大
   	int k = 3;
   	int arr[] = { 14, 42, 67, 2, 53 ,56, 74, 23 };
   	int sz = sizeof(arr) / sizeof(arr[0]);
   
   	HeapSort(arr, sz);
   
   	int i = 0;
   	for (i = 0; i < k; i++)
   	{
   		printf("%d ", arr[i]);
   	}
   	printf("\n");
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17

2. 堆排序中的选数：

   a. 建大堆：

   1. 选K次，也相当于 HeapPop k次，最大、次大、次次大…最后得到最大的K个
   2. 时间复杂度：O(N+logN*k) —— 建堆，O(N) + 选数K次O(logN*k)
   • 数据小没问题；
   • 数据大，内存存不下整体数据来建堆——如果 N=100亿，100亿个整数，即 400亿Byte ~= 40GB（1GB~=10亿字节），堆建不起来，排序选数都不行了

   b. 建小堆：打擂台

   1. 拿 前K个数，建 K个数的小堆——保持最弱的在堆顶，如果建大堆，万一最大的数是擂主，其他数都干不过了
   2. 后 N-K个数 一个个来攻擂，攻擂成功就向下调整，继续保持最弱的在堆顶
   3. 最后擂台上的一定是最厉害的K个数，得到TopK
   • K通常不大，空间这块拿捏了

   void GenertateData(int n)
   {
   	FILE* fin = fopen("data.txt", "w");
   	if (fin == NULL)
   	{
   		perror("fopen fail");
   		return;
   	}
   
   	srand(time(0));
   
   	int i = 0;
   	for (i = 0; i < n; i++)
   	{
   		fprintf(fin, "%d\n", rand() % 10000);
   	}
   
   	fclose(fin);
   	fin = NULL;
   }
   
   void PrintTopK_File()
   {
   	//求前K大——文件
   	GenertateData(10000000000);
   	FILE* fout = fopen("data.txt", "r");
   	if (fout == NULL)
   	{
   		perror("fopen fail");
   		return;
   	}
   
   	int k = 10;
   	int sz = 10000;
   
   	//从文件中读K个数据
   	HeapDataType* minHeap = (HeapDataType*)malloc(sizeof(HeapDataType) * k);
   	if (minHeap == NULL)
   	{
   		perror("malloc fail");
   		return;
   	}
   
   	int i = 0;
   	for (i = 0; i < k; i++)
   	{
   		fscanf(fout, "%d", &minHeap[i]);
   	}
   
   	//建小堆
   	for (i = (k - 2) / 2; i >= 0; i--)
   	{
   		AdjustDown(minHeap, k, i);
   	}
   
   	//读取后sz-k个数据攻擂
   	HeapDataType val = 0;
   
   	while (fscanf(fout, "%d", &val) != EOF)
   	{
   		if (val > minHeap[0])
   		{
   			minHeap[0] = val;
   			AdjustDown(minHeap, k, 0);
   		}
   	}
   	HeapSort(minHeap, k);
   
   	printf("Max K :\n");
   	for (i = 0; i < k; i++)
   	{
   		printf("%d\n", minHeap[i]);
   	}
   
   	fclose(fout);
   	fout = NULL;
   }
   
   int main()
   {
       TestTopK_File();
       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
   80
   81
   82
   83

如何彻底验证我们的代码对不对呢：在文件中随意挑取10个数，改成 大于 10000 的，选出来的MaxK 肯定是这10个

二叉树的链式结构

定义

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;
1
2
3
4
5
6

实现

建树

为了降低学习成本，先简单粗暴建树，用于学习其他，后期再使用真正创建方法

BTNode* CreateBinaryTree()
{
	BTNode* node1 = (BTNode*)malloc(sizeof(BTNode));
	assert(node1);
	BTNode* node2 = (BTNode*)malloc(sizeof(BTNode));
	assert(node2);
	BTNode* node3 = (BTNode*)malloc(sizeof(BTNode));
	assert(node3);
	BTNode* node4 = (BTNode*)malloc(sizeof(BTNode));
	assert(node4);
	BTNode* node5 = (BTNode*)malloc(sizeof(BTNode));
	assert(node5);
	BTNode* node6 = (BTNode*)malloc(sizeof(BTNode));
	assert(node6);
    //后续演示有时用到node7
	//BTNode* node7 = (BTNode*)malloc(sizeof(BTNode));
	//assert(node7);

	node1->data = 1;
	node2->data = 2;
	node3->data = 3;
	node4->data = 4;
	node5->data = 5;
	node6->data = 6;
    //后续演示有时用到node7
	//node7->data = 7;

	node1->left = node2;
	node1->right = node5;

	node2->left = node3;
	node2->right = node4;

	node3->left = NULL;
	node3->right = NULL;

	node4->left = NULL;
	node4->right = NULL;

	node5->left = node6;
	node5->right = NULL;

	node6->left = NULL;
    //后续演示有时用到node7
    //node6->left = node7;
	node6->right = NULL;

    //后续演示有时用到node7
	//node7->left = NULL;
	//node7->right = NULL;

	return node1;
}
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

遍历

给出下面这棵树，遍历

1. 前序遍历：根 ==> 左子树 ==> 右子树

   访问左子树前，先访问根；访问右子树前，先访问左子树
   

   void PreOrder(BTNode* root)
   {
   	if (root == NULL)
   	{
   		printf("NULL ");
   		return;
   	}
   
   	printf("%d ", root->data);
   	PreOrder(root->left);
   	PreOrder(root->right);
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12

2. 中序遍历：左子树 ==> 根 ==> 右子树

   访问根之前，先访问左子树；访问右子树前，先访问根

   void InOrder(BTNode* root)
   {
   	if (root == NULL)
   	{
   		printf("NULL ");
   		return;
   	}
   
   	InOrder(root->left);
   	printf("%d ", root->data);
   	InOrder(root->right);
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12

3. 后序遍历：左子树 ==> 右子树 ==> 根

   访问右子树前，先访问左子树；访问根之前，先访问右子树

函数调用同前\中序大致一样，这里就不赘述了

二叉树遍历的空间复杂度？

：取决于 深度

诶呀？上面的图里，调用那么多函数，创建那么多栈帧，怎么会取决于深度呢。前面讲解函数栈帧的时候，就讲了函数调用流程

• 调用函数
• 执行函数体内指令
• 销毁栈帧 并 带回返回值
• 到调用指令 call 的下一条指令接着执行

求大小

int TreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	return TreeSize(root->left)
		+ TreeSize(root->right)
		+ 1;
}
1
2
3
4
5
6
7
8
9

求叶结点数

就是加个判断

int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return TreeLeafSize(root->left)
		+ TreeLeafSize(root->right);
}
1
2
3
4
5
6
7
8
9
10
11

求高度

• lH：当前根结点的左子树高度
• rH：当前根结点的右子树高度

int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	int lh = TreeHeight(root->left);
	int rh = TreeHeight(root->right);

	return lh > rh ? lh + 1 : rh + 1;
}
1
2
3
4
5
6
7
8
9
10

第K层结点个数

• 第K层，相对第一层（整棵树的根结点）是 第K层

  第K层，相对第二层，是 第K-1层

  第K层，相对第三层、第四层、第N层……

• 第K层 = 当前层的下一层 的 K-1层

int TreeKLevel(BTNode* root, int k)
{
	assert(k > 0);

	//未到目标K层却空，这条路走不到第K层
	if (root == NULL)
		return 0;
	//能走到目标K层，就说明第K层的此位置有结点
	if (k == 1)
		return 1;

	//进入下一层
	return TreeKLevel(root->left, k - 1)//这里其实就是递减K了
		+ TreeKLevel(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

查找

BTNode* TreeFind(BTNode* root, BTDataType x)
{	
	if (root == NULL)
		 return NULL;
	if (root->data == x)
		return root;
	
	//先找左树
	BTNode* leftFind = TreeFind(root->left, x);
	if (leftFind)
		return leftFind;
	  
	//左树没找到就找右树
	BTNode* rightFind = TreeFind(root->right, x);
	if (rightFind)
		return rightFind;
	
	//左右和自己都不是，返回NULL给上一层：我这儿没有，到别处找！
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

返回值很重要，它决定了后续递归的逻辑

层序遍历

void LevelOrder(BTNode* root)
{
	Queue q;

	QueueInit(&q);

	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* tmp = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", tmp->data);
		
        //下一层
		if (tmp->left)
			QueuePush(&q, tmp->left);
		if (tmp->right)
			QueuePush(&q, tmp->right);
	}
	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

判断完全二叉树

依层序遍历的特点，遍历到第N个结点时，标蓝的地方全在队列中

看完图可以知道：出现空后不可能再出现非空

bool IsComplete(BTNode* root)
{
	//层序遍历：出现空后不可能再出现空
	Queue q;

	QueueInit(&q);

	if (root)
		QueuePush(&q, root);

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

		if (tmp == NULL)
			break;

		//NULL也要入队
		QueuePush(&q, tmp->left);
		QueuePush(&q, tmp->right);
	}

	//出现空后，全是空 ==> 完全二叉树
	//出现空后，有非空 ==> 非完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* tmp = QueueFront(&q);
		QueuePop(&q);
		if (tmp != NULL)
			return false;
	}
	QueueDestroy(&q);

	return true;
}
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

本期二叉树基础就到这里啦，下期带来二叉树的基础oj题，在实践中感受知识的内化

培根的blog，与你共同进步！