devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】树、二叉树与堆（长期维护）

作者：很楠不爱3 | 2024-05-23 15:32:07

赞

踩

【数据结构】树、二叉树与堆（长期维护）

下面是关于树、二叉树、堆的一些知识分享，有需要借鉴即可。

一、初识树（了解即可）

1.树的概念

概念：一种非线性数据结构，逻辑形态上类似倒挂的树
在这里插入图片描述
树的构成：由一个根+左子树+右子树构成，其中子树又可以拆分为根、左子树、右子树…

2.树的相关概念

  • 结点的度：一个结点的孩子个数
  • 叶节点（终端结点）：没有孩子的结点
  • 分支节点（非终端结点）：有孩子的结点
  • 父节点（双亲结点）：结点的上一层结点
  • 子节点（孩子结点）：孩子
  • 兄弟节点：相同父节点的结点
  • 树的度：一课树中最大的结点的度
  • 结点的层次：树的高度，从1开始计算
  • 树的高度/深度：一棵树中最大的层次
  • 结点的祖先：一个节点的上面层级的结点都可以是该节点的祖先
  • 子孙：孩子，孩子的孩子…
  • 森林：两颗或者多棵树

3.树的表示方法

树的表示方法有很多，下面来展示树的主流表示方法。

#pragma once

//方法1：结点指针数组
//前提：明确树的度
#define N 100
typedef struct TreeNode
{
	int val;
	struct TreeNode* childArr[N];//结点指针数组
}TreeNode;
//方法1：不推荐，浪费空间

//方法2：顺序表
typedef struct TreeNode
{
	int val;
	//顺序表
	struct TreeNode* arr;
	int capacity;
	int size;
}TreeNode;
//方法2：可以使用，借助其他数据结构，不够方便

//方法3：左孩子右兄弟
typedef struct TreeNode
{
	int val;
	struct TreeNode* leftchild;
	struct TreeNode* rightchild;
}TreeNode;
//方法3：十分推荐，不依赖其他数据结构，且高效表示

  • 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

在这里插入图片描述

4.树的应用

树的应用场景最典型的两个：一是linux树状目录结构；二是windows森林状分盘
在这里插入图片描述

二、二叉树

(一)、初识二叉树(了解即可)

1.二叉树的相关概念

二叉树概念：二叉树属于一种特殊的树，需要具备两个条件的树才可以成为二叉树：

  • 首先是树
  • 树的度<=2
    在这里插入图片描述
    在这里插入图片描述

满二叉树的概念：一种特殊的二叉树、同时满足二叉树、且满足树的每一层都是满的
完全二叉树概念：一种特殊的二叉树、同时满足二叉树、且树前h-1层满的+第h层是自左向右是连续的
在这里插入图片描述

思考1：探索满二叉树/完全二叉树总结点个数与层数关系
在这里插入图片描述
思考2：区分各种树的包含关系？
答：
在这里插入图片描述

2.二叉树的意义

二叉树意义：为后面的搜索二叉树、红黑树、AVL树等高阶数据结构做铺垫。

本身树的意义并不大，二叉树的意义单从存储数据来说也没有什么意义，但是二叉树是组成搜索二叉树、哈夫曼树的基础，有了搜索二叉树大大方便数据搜索但也存在一些问题，有些搜索二叉树可能会退化为类似链表的树，因而AVL树、红黑树、M阶B树也随之而来解决问题。
在这里插入图片描述

3.二叉树的存储结构

一般来说二叉树具有两种存储方式，一是数组存储、二是链式存储。
顺序存储（数组存储）

//完全二叉树顺序结构表示
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

在这里插入图片描述
链式存储
在这里插入图片描述

思考：该如何选择存储方式？
如果是完全二叉树/满二叉树，选择顺序结构，如果是一般的二叉树，要选择链式结构进行存储。
至于为什么，下面来进行解答：
如果是完全二叉树，放在数组中，其数组下标在父子关系上存在公式，也就是说知道孩子的结点下标就可以算出父亲的数组下标，这样一来就很方便了，但如果不是完全二叉树就不具备这个关系。
在这里插入图片描述
父子间公式：

  • leftchild = 2 * parent + 1;
  • rightchild = 2 * parent + 2;
  • parent = (child - 1)/2;

4.二叉树的相关性质

在这里插入图片描述

拓展练习题：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

(二)、堆

1.堆的概念

数据结构堆，需要满足两个条件：

  • 是完全二叉树
  • 父子间满足父>=子(父<=子)

注：我们称父>=子的堆为大堆，反之为小堆
在这里插入图片描述
下面是堆的所有接口一览：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

/*
//方法1：结点指针数组
//前提：明确树的度
#define N 100
typedef struct TreeNode
{
	int val;
	struct TreeNode* childArr[N];//结点指针数组
}TreeNode;
//方法1：不推荐，浪费空间

//方法2：顺序表
typedef struct TreeNode
{
	int val;
	//顺序表
	struct TreeNode* arr;
	int capacity;
	int size;
}TreeNode;
//方法2：可以使用，借助其他数据结构，不够方便

//方法3：左孩子右兄弟
typedef struct TreeNode
{
	int val;
	struct TreeNode* leftchild;
	struct TreeNode* rightchild;
}TreeNode;
//方法3：十分推荐，不依赖其他数据结构，且高效表示
*/


//完全二叉树顺序结构表示
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HeapInit(HP* php);
void HeapDestroy(HP* php); 
void HeapPush(HP* php, HPDataType x);
void AdjustUp(HPDataType* a, int child);
void HeapPop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
HPDataType HeapTop(HP* 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
  • 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

2.堆的初始化与销毁接口

堆的底层我们使用顺序表实现，所以堆的初始化与销毁 == 顺序表的初始化与销毁

void HeapInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->capacity = php->size = 0;
}

void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);//本身free对空会进行检查
	php->a = NULL;
	php->capacity = php->size = 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

3.堆的插入接口

思路：底层是数组，也就是顺序表，顺序表尾插成本很低，因而我们进行尾插。
问题：但是出现一个问题，尾插之后还是堆吗？（还满足父子间结点下标关系吗？）—>向上调整算法
在这里插入图片描述

void Swap(HPDataType* p1, HPDataType* p2)
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

//小堆
void AdjustUp(HPDataType* a, int child)
{
	assert(a);

	int parent = (child - 1) / 2;
	while (child > 0) //思考：请思考while括号内的结束条件是什么？
	{                 //提示选项如下：1.parent>=0 2.child>=0 3.child>0          
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//扩容
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* temp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		php->a = temp;
		php->capacity = newcapacity;
	}
	
	php->a[php->size++] = x;

	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
  • 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

数据测试：

#include"Tree.h"

int main()
{
	int a[9] = { 1,4,7,2,5,8,3,6,9 };
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}

	HeapDestroy(&hp);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

测试结果：
在这里插入图片描述

思考1：请思考while括号内的结束条件是什么？
提示选项如下：1.parent>=0 2.child>=0 3.child>0
答：while(child>0)，原因如下图。
在这里插入图片描述
思考2：向上调整的使用前提是什么？前面的数据是堆。

4.堆的删除接口

堆数据结构中规定：删除堆顶的数据。
意义：可以找出下一个最小值（最大值），也就是这一串数据中的次小值（次大值）。

怎么删除？
使用挪动数据删除,存在问题：

  • 父子间的关系全乱
  • 每次删除重建堆，时间复杂度(O(N^2))*

所以我们使用另一种思路：首尾交换，尾删，向下调整算法，原因如下：

  • 首尾交换删除之后，左右子树还存在父子关系
  • 顺序表尾删的成本低
  • 向下调整算法时间复杂度低（O(logN)）
    在这里插入图片描述
void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;

	while (child < size)//思考1：while的结束条件是什么？
	{
		// 假设左孩子小，如果解设错了，更新一下
		if (child + 1 < size && a[child + 1] < a[child])//思考2：if中“child + 1 < size”的意义是什么？
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	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
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

思考1：while中的条件是什么？
答：child < size
在这里插入图片描述
思考2：if中“child + 1 < size”的意义是什么？防止右孩子不存在。
思考3：向下调整算法的使用前提条件是什么？左右子树保证是堆。

测试（删除接口的意义之一）：删除的应用：用来找一列数中前k小/大的K个数字：
#include"Tree.h"

int main()
{
	int a[9] = { 1,4,7,2,5,8,3,6,9 };
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}

	//假设找堆中前三小的数字
	for (int i = 0; i < 3; i++)
	{
		int num = hp.a[0];
		HeapPop(&hp);
		printf("%d ", num);
	}

	HeapDestroy(&hp);
	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

在这里插入图片描述

5.其他接口

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

HPDataType HeapTop(HP* php)
{
	assert(php);

	return php->a[0];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

测试（堆的意义之一），可以打印出一组有序数据（注：这里并不是堆排序）：

思考：为什么打印出有序数据!=堆排序？
答：两者的最大区别在于两点

  • 有序打印没有改变原数组，而堆排序是对原数组进行排序
  • 有序打印需要空间复杂度为O(N)，而堆排序空间复杂度O(1)
#include"Tree.h"

int main()
{
	int a[9] = { 1,4,7,2,5,8,3,6,9 };
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}

	假设找堆中前三小的数字
	//for (int i = 0; i < 3; i++)
	//{
	//	int num = hp.a[0];
	//	HeapPop(&hp);
	//	printf("%d ", num);
	//}

	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}

	HeapDestroy(&hp);

	//system("pause");
	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

在这里插入图片描述

6.堆排序的应用：TopK问题

场景：如果现在有100亿的个整形数据，找出前一百个小的值。

  • 方法1：对100亿个数据建堆，top，pop一百次即可。
    显然这种方法有问题，下面为分析：
    在这里插入图片描述
  • 方法2：升序，借助堆
    思想：排升序，建K个值大小的大堆，然后让(10亿-K)个数据依次与大堆中的堆顶进行比较，比堆顶小的值进行替换，然后向下调整…不断进行比较，直到结束。

思考1：为什么排升序要建大堆？
这其实利用了大堆的小数向下沉的性质，从而巧妙地保护了小数，防止小数被替换掉。
思考2：排升序建小堆可以吗？
可以，但是因为效率低下，还不如冒泡排序效率高。

下面是1万的数据的代码示例：

void MakeData()
{
	int n = 10000;

	srand(time(0));

	const char* pfile = "data.txt";
	FILE* pf = fopen(pfile, "w");
	if (pf == NULL)
	{
		perror("open fail");
		exit(-1);
	}

	for (int i = 0; i < n; i++)
	{
		int num = rand()%1000;
		fprintf(pf, "%d\n", num);
	}

	fclose(pf);
}

void Select_TopK(int n)
{
	int k = 10;

	FILE* pf = fopen("data.txt", "r");
	if (pf == NULL)
	{
		perror("fopen 'r' fail");
	}

	//建堆
	HPDataType* minheap = (HPDataType*)malloc(sizeof(HPDataType) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &minheap[i]);
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);
	}

	int x = 0;
	while (fscanf(pf, "%d", &x) != EOF)
	{
		// 读取剩余数据，比堆顶的值大，就替换他进堆
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	
	free(minheap);
	fclose(pf);
}

test_TopK()
{
	//MakeData();
	Select_TopK(10000);
}

int main()
{
	//test_heap();
	test_TopK();
	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

小技巧1：在面对庞大数据的随机数选前最值时候，如何快速测试自己代码得到结果是对的？
首先要控制数据范围，然后手动随机对每个数据修改为最值，看是否代码可以选出来。
庞大随机数测试，手动修改

小技巧2：手动条件断点，如果上面代码我只想看大于1万的值是怎么进堆的，所以我可以这样：
冷知识：没有完整语句的地方不能打断点，下面定义xx = 0目的在于打断点。在这里插入图片描述

7.堆排序

  • 方法1：借用堆push接口实现堆排序。
    过程略。
  • 方法2：对数组直接进行建堆，大致过程如下：

假如说要对N个数的数组进行排序，要求降序
第一步建堆：在这里插入图片描述

思想：将数组中第一个视为堆，将第二个数字进行向上调整，使前两个数字成为堆，将第三个数字向上调整…以此类推，对整个数组向上调整。
在这里插入图片描述
显然，现在这只是形成了小堆，并不是有序并且也不是降序。

思考：在数组直接建堆时候可以用向下调整算法吗？
可以，只需要从倒数第一个非叶子开始，依次向上对每个结点进行调整就好了。
思考：为什么要从倒数第一个非叶子开始使用向下调整算法？
因为向下调整算法的使用前提是左右子树是堆。

第二步：选数排序：
思想：建好小堆之后，首尾交换，再将尾数据不视为堆，这样，最小的数字就到了最后，同理，再次对前N-1个数字进行建堆，然后首尾交换，这样第二小的数字就到了倒数第二个位置…以此类推。
在这里插入图片描述

思考：如果要升序，建大堆还是小堆，如果要降序，建大堆还是小堆？为什么？
答：

  • 升序 —> 建大堆
  • 降序 —> 建小堆
    至于为什么，是因为无论大堆还是小堆，只能确保堆顶的数据是最大值/最小值，而我们利用了堆删除接口的思想，首尾交换，因而说升序 —> 建大堆 - 降序 —> 建小堆 。
void HeapSort(int* a, int n)
{
	// a数组直接建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)//思考：while的结束条件是什么？
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

(三)、分析堆

1.向下调整算法建堆的时间复杂度分析

void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;

	while (child < size)//思考1：while的结束条件是什么？
	{
		// 假设左孩子小，如果解设错了，更新一下
		if (child + 1 < size && a[child + 1] < a[child])//思考2：if中“child + 1 < size”的意义是什么？
		{
			++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

在这里插入图片描述

结论：
向下调整算法时间复杂度为O(logN)
向下调整算法建堆的时间复杂度是多少？O(N)

2.向上调整算法建堆的时间复杂度分析

//小堆
void AdjustUp(HPDataType* a, int child)
{
	assert(a);

	int parent = (child - 1) / 2;
	while (child > 0) //思考：请思考while括号内的结束条件是什么？
	{                 //提示选项如下：1.parent>=0 2.child>=0 3.child>0          
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

在这里插入图片描述

结论：
向上调整算法的时间复杂度为O(logN)
向上调整算法建堆的时间复杂度为：O(N * log(N))

思考：向上调整算法与向下调整算法同为调整算法，且时间复杂度都为O(logN),为什么向下调整算法建堆的时间复杂度为O(N)，而向上调整算法却到达了O(N*logN)?
答：
说的简单一点，对于单个结点的向上调整/向下调整，都大概最差要调整高度次，也就是差不多是logN，但是对于一整个堆而言，这个堆中如果用向上调整算法，第一行不需要调整，如果用向下调整算法，最后一行不需要调整，而往往在N足够大的情况下，最后一行的结点个数占百分之50左右。
在这里插入图片描述

3.堆排序的时间复杂度分析

堆排序有两部分组成，第一步是建堆，第二是首尾交换，尾不视为堆内，对N-1个数据向下调整算法重新成为堆。
在第一步，可以使用向上/向下调整算法建堆，肯定是选择向下调整算法建堆。时间复杂度上面经过分析为O(N)
在第二步，时间复杂度为O(N*logN)
代码如下：

void HeapSort(int* a, int n)
{
	// a数组直接建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)//思考：while的结束条件是什么？
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

在这里插入图片描述
综上，堆排的时间复杂度为O(N*logN)

结论：堆排的时间复杂度为O(N*logN)

(四)、一般的二叉树

上面所说的堆是特殊的二叉树+满足大堆小堆的条件才可以称为堆，下面来简单说一下对于一般二叉树的常规知识点。

每棵树都可以分为根、左子树、右子树，其中左子树又可以分为根、左子树、右子树…二叉树也不例外。
在这里插入图片描述
同时，因为一般二叉树放入顺序结构中比较浪费空间，一般选用链式结构来构造一般的二叉树。

1.一般二叉树的遍历

二叉树的遍历可以分为前序遍历、中序遍历、后序遍历。

  • 二叉树的前序遍历(根、左子树、右子树)：
    前序遍历本质上是深度优先遍历
void PreOrder(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

在这里插入图片描述
在这里插入图片描述

拓展练习题：二叉树的前序遍历LINK
在这里插入图片描述
示例代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 int TreeSize(struct TreeNode* root)
 {
    if(root == NULL)
    {
        return 0;
    }

    return TreeSize(root->left) + TreeSize(root->right) + 1;
 }

void PreOrder(struct TreeNode* root,int* arr,int* pi)
{
    if(root == NULL)
    return;

    arr[(*pi)++] = root->val;//思考，这个小括号是否可以省略？
    PreOrder(root->left,arr,pi);
    PreOrder(root->right,arr,pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
    int n = *returnSize = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int) * n);
    int i = 0;//思考：这里为什么要传地址
    PreOrder(root,arr,&i);

    return arr;
}

  • 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

思考1：这个小括号是否可以省略？
不能，语法优先级问题。
思考2：这里为什么要传地址？
使用递归，要改变一个固定空间的i值，要传入地址或者搞一个全局变量。

  • 二叉树的中序遍历(左子树、根、右子树)
void InOrder(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

在这里插入图片描述

拓展练习题：二叉树的中序遍历LINK

  • 二叉树的后序遍历(左子树、右子树、根)
void PostOrder(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

在这里插入图片描述

拓展练习题：二叉树的后序遍历LINK

2.树的节点个数接口

  • 思想1：分置思路
    在这里插入图片描述
int TreeSize(Tree* root)
{
	if (root == NULL)
	{
		return 0;
	}
	
	return TreeSize(root->left) + TreeSize(root->left) + 1;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
int TreeSize(Tree* root)
{
	return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}

  • 1
  • 2
  • 3
  • 4
  • size统计思路
//思考：如果用size进行统计结点个数，要定义为局部变量/全局变量/全局变量/指针变量？？？
//局部变量，否定，统计结果永远为0/1
//全局变量，可以，需要每次调用需要置为空size
//局部静态变量，否定，不能置空操作，多次调用之后会出问题
//指针变量：可以，每次也都需要置空


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

思考：size统计思路各种处理size方法的利弊。
如果用size进行统计结点个数，要定义为局部变量/全局变量/全局变量/指针变量？？？
//局部变量，否定，统计结果永远为0/1
//全局变量，可以，需要每次调用需要置为空size
//局部静态变量，否定，不能置空操作，多次调用之后会出问题
//指针变量：可以，每次也都需要置空

代码技巧：要想写好递归，需要控制好两个条件，

  • 子问题
  • 结束条件(返回条件)


对于本接口，那么需要把握好下面两个条件：

  • 子问题：一棵树的结点个数 = 左子树结点个数 + 右子树结点个数 + 1
  • 结束条件：NULL，返回0

拓展1：实现一棵树叶子结点个数：自己思考，参考代码如下

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

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

	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

拓展2：求树的第K层结点个数，参考代码如下：

int TreeSize_K(Tree* root,int k)
{
	if (root == NULL || k < 1)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}

	return TreeSize_K(root->left, k - 1) + TreeSize_K(root->right, k - 1);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

3.树的高度接口

思路：这里要求树的高度，那么就是对于一个子树的高度就是左子树的高度，右子树的高度取其大的进行返回 +1(这个1是指自己) 。

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

	int leftheight = TreeHeight(root->left);//思考：这里为啥不直接返回而是用变量记录的意义。
	int rightheight = TreeHeight(root->right);
	return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}

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

思考：这里为啥不直接返回而是用变量记录的意义
其意义在于，防止重复调用，这里其实就是一个不断多次重复的问题。

int TreeHeight(Tree* root)
{
	return root == NULL ? 0 : (TreeHeight(root->left) > TreeHeight(root->right) ? >TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1);
}

  • 1
  • 2
  • 3
  • 4

这样第一次多调用一次，那么第二层要多调用2^1 第三层要多调用2^2次 第四层要多调用2^3次…
在这里插入图片描述

4.树的查找接口

Tree* TreeFind(Tree* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->val == x)
	{
		return root;
	}

	Tree* left = TreeFind(root->left,x);
	if (left)
	{
		return left;
	}
	Tree* right = TreeFind(root->right,x);
	if (right)//思考，这里为什么要加这个if条件
	{
		return right;
	}

	return NULL;
}

  • 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

在这里插入图片描述

思考：至于为什么要加上if，防止空指针也被返回，如果没有if可能会提前返回出问题。
就是左子树返回后，会直接返回到上一级函数，没有机会执行右子树了。
在这里插入图片描述

拓展练习题：单值二叉树
LINK
在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)//如果走到空结点，直接返回true
    {
        return true;
    }

    if(root->left && root->val!=root->left->val)
    {
        return false;
    }
    if(root->right && root->val!=root->right->val)
    {
        return false;
    }

    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

  • 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

拓展练习题2：对称二叉树LINK
在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 bool _isSymme(struct TreeNode* q,struct TreeNode* p)
 {
    if(q == NULL && p == NULL)
    {
        return true;
    }

    if(q == NULL || p == NULL)
    {
        return false;
    }

    if(q->val != p->val)
    {
        return false;
    }

    return _isSymme(q->left,p->right) && _isSymme(q->right,p->left);
 }

bool isSymmetric(struct TreeNode* root) {
    return _isSymme(root,root);
}

  • 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

拓展练习题：另一颗树的子树LINK
在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isSameTree(struct TreeNode* root, struct TreeNode* subRoot) {
    if(root == NULL && subRoot == NULL)
    {
        return true;
    }

    if(root == NULL || subRoot == NULL)
    {
        return false;
    }

    if(root->val != subRoot->val)
    {
        return false;
    }

    return isSameTree(root->left,subRoot->left) && isSameTree(root->right,subRoot->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (root == NULL) {
        return false;
    }

    if (root->val == subRoot->val) {
        if(isSameTree(root, subRoot) == true)//思考：这里if的意义在哪里？
        {
            return true;
        }
    }

    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

  • 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

思考：上面if返回的意义在于，要把整个树的每一个结点都比较一遍，防止特殊情况出现。
比如：在这里插入图片描述

5.树的构建接口

Tree* TreeCreat(char* a, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	Tree* root = (Tree*)malloc(sizeof(Tree));
	if (root == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	root->val = a[(*pi)++];
	root->left = TreeCreat(a, pi);
	root->right = TreeCreat(a, pi);

	return root;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
test_TreeCreat()
{
	char* a = "abc##de#g##f###";
	int i = 0;
	Tree* root = TreeCreat(a, &i);
	PreOrder(root);
}

int main()
{
	//test_heap();
	//test_TopK();
	//test_HeapSort();
	//test_GenBTree();
	test_TreeCreat();
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

在这里插入图片描述

6.层序遍历接口

本质上是广度优先遍历
思路：

void TreeLevelOrder(Tree* root)
{
	Queue q;
	QueueInit(&q);
	if (root != NULL)
	{
		QueuePush(&q,root);
	}

	while (!QueueEmpty(&q))
	{
		Tree* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->val);

		if (root->left != NULL)
		{
			QueuePush(&q, root->left);
		}
		if (root->right != NULL)
		{
			QueuePush(&q, root->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
  • 25
  • 26
  • 27
  • 28

7.树的销毁

oid TreeDestroy(Tree* root)
{
	if (root == NULL)
	{
		return;
	}

	TreeDestroy(root->left);
	TreeDestroy(root->right);
	free(root);
}

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

在这里插入图片描述

待续。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/613419
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号