树的概念及结构

树的概念

树的概念来源于我们的生活

这个就是一个比较标准的树

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

• 有一个特殊的结点，称为根结点，根结点没有前驱结点

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

• 因此，树是递归定义的

树的相关概念

节点的度

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

叶子节点或终端节点

度为0的节点称为叶子节点

非终端节点或分支节点

度不为0的节点

双亲节点或子节点

若一个节点含有子节点，则这个节点称为其子节点的父节点

孩子节点或子节点

一个节点含有的子树的根节点称为该节点的子节点

兄弟节点（亲兄弟）

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

树的度

一棵树中，最大的节点的度称为树的度

这个树的度就为3

节点的层次

从根开始定义起，根为第1层，根的子结点为第2层，以此类推。这里并没有非常严格的定义，但一般情况下，我们从1开始

为什么从1开始？如果从0开始，空树就得认为是-1了。

那为什么数组要从0开始呢？为了方便寻址

树的高度或深度

树中节点的最大层次

树的高度为4

堂兄弟结点

双亲在同一层的结点互为堂兄弟

结点的祖先（直系亲属）

从根到该结点所经分支上的所有结点

子孙

以某结点为根的子树中任一结点都称为该结点的子孙

森林

由m（m>0）棵互不相交的树的集合称为森林。多棵树，就可以叫森林

我们以后会学并查集，就是森林。

树是递归定义的

任何一棵树的构成都是由两个部分构成

递归定义：大问题拆解成小问题，小问题拆解成更小的问题，直到不能拆解为止。

树与非树？

树它的子树之间是不能连接的。

树的实现

树应该怎么去实现呢？我定义几个指针呢？

已经明确了树的度

没有明确树的度

我们用顺序表来实现，我们以后C++会学到

左孩子右兄弟表示法

树在实际中的运用

表示文件系统的目录树结构

二叉树的概念及结构

特殊的二叉树

满二叉树

每一层都是满的

一个高度为h的满二叉树有多少个节点呢？

完全二叉树

这种是连续的

这种就不连续了

二叉树的存储

顺序（数组）存储

这种虽然逻辑比较抽象，但方便储存。而且很好找孩子

局限性

• 只适合满二叉树或完全二叉树

• 如果是非完全二叉树，你就得这样做

浪费空间

• 非完全二叉树就适合用链式结构存储

链式存储

我们后面讲非完全二叉树会讲，我们先来讲完全二叉树，这个简单一些。

二叉树的结构及实现

顺序结构（数组）

堆

堆的概念及结构

首先，它是一个完全二叉树。其次，它的父亲和孩子之间有一个大小关系。

• 大堆

• 小堆

那，小堆是不是升序，大堆是不是降序？不一定

我换个位置它是不是依然是小堆啊。

堆要求的是父子之间的大小关系，兄弟之间有没有规定大小关系啊？没有，所以堆并不代表有序。

用途

堆排序、TOP K问题。我们之后都会讲到。

特点

根是最小（最大）的，它可以用来找极值，找极值就可以用来作排序。那它做排序的特点是什么呢？效率高。

堆的实现

堆本质上是一个完全二叉树

定义堆的结构

//定义堆的结构
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

初始化

void HPInit(HP* php)
{
	php->a = NULL;
	php->size = php->capacity = 0;
}

销毁

void HPDestroy(HP* php)
{
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

向上调整

//向上调整
void AdjustUp(HPDataType* a,int child)
{
	int parent = (child - 1) / 2;
	while (child > 0 && a[child] < a[parent])
	{
		Swap(&(a[child]), &(a[parent]));
		child = parent;
		parent = (child - 1) / 2;
	}
}

向上调整可以保证你建的堆是正确的，如果你建的是小堆，它可以保证父节点比子节点小。

插入

void HPPush(HP* php, HPDataType x)
{
	//检查容量
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : (php->capacity) * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a,newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}

		php->a = tmp;
		php->capacity = newcapacity;

	}
	//先插入尾部
	php->a[php->size++] = x;
	//再向上调整
	AdjustUp(php->a,php->size-1);
}

Swap

void Swap(HPDataType* s1,HPDataType* s2)
{
	HPDataType tmp = *s1;
	*s1 = *s2;
	*s2 = tmp;
}

删除

Pop删除，要求删除堆顶的数据(根位置)。那我能不能直接挪动覆盖删除？（头删）

不行

怎么办？把最小的子孙和最大的祖先换一下，再删除孙子

此时它的左子树和右子树是不是都是小堆啊？

然后我们使用一个向下调整算法（左右孩子是小堆才能这么玩）

void AdjustDown(HPDataType* a, int n, int parent)
{
    //找出左右孩子里面小的那个，把它和根节点交换
	//假设法
	int child = parent * 2 + 1;
	while (child < n)   // child >= n说明孩子不存在，调整到叶子了
	{
		//找出小的那个孩子
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			//把它和父节点交换
			Swap(&a[parent], &a[child]);
			//parent往下走
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

1. 我们找出左右孩子里面小的那个，把它和根节点交换

2. 同样的步骤

那我们Pop的意义在哪儿？我们是不是把第二小的2换到堆顶上了？那如果我们不断Pop，那堆里面的数据是不是就被从小到大依次取出来了？（是不是就有序了？）（TOP K问题）但是这并不是排序，排序是从根本上把内容改变了。

void HPPop(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);
}

计算向上调整和向下调整的时间复杂度

先来回顾一下完全二叉树的层数

满二叉树的层数是log₂(N+1)

完全二叉树我们就要分两种情况来分析了

• 上限（最多有多少的节点）

满二叉树

• 下限（最少有多少的节点）

向上调整

我们在这个地方向上插入，最多（最差情况）走高度次

也就是logN次，忽略那些边边角角。

向下调整

也是一样的---logN次

堆的应用

堆排序

怎么做？如果用堆这个数据结构，那是不是要再额外开一块空间啊？（空间复杂度是O（N））

能不能直接把这个数组变成堆呢？可以

向上调整建堆

我们那个函数没传结构体就是为这里做准备

我直接把这个数组看成一个完全二叉树，然后复用咱们向上调整的逻辑

也可以向下调整

//向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(a,n,i);
}

假设我们这里要建大堆

• 如果左子树是大堆，右子树也是大堆

那我们这里直接向下调整是不是就行了？

• 但是，左子树不是大堆，右子树不是大对，这时怎么办呢？

我可以想办法让它变成大堆。我可以对它的左右子树分别在进行向下调整啊。

我们以刚刚的左子树为例

那是不是要求它的左右子树也都为大堆，才能向下调啊？

这时，它就想到了一种方法------倒着调（我要调整这个我得保证它的子树是大堆，我要调整它的子树我又得保证它的子树的子树是大堆，那我干脆一步到位，我直接倒着调）。

我们是不是从这些叶子开始调啊？

但是这些叶子都不需要调（因为他们根本没有子树）

所以我们从倒数的第一个非叶子节点（最后一个节点的父亲）开始调

1. 先对这棵树进行调整

2. 再调这个

3. 再调这个

4. 再调这个

5. 再调这个

最后就达到我们的目的了，左右子树都是大堆

然后就可以按我们之前的向下调整来弄了

弄完就是这个样子

向下调整建堆的效率会比向上调整更高

• 向下时间复杂度------O(N)
• 向上-------O(NlogN)

我们的堆就构建完了，那我们现在来写一个降序的堆排序。

降序建大堆还是小堆？

不能建大堆

举个例子

这里的9排好了，那你是不是要找次大的数？那你其他的是不是也要按堆来排，那是不是又是兄弟变父子啊？和刚刚的覆盖（头删）是不是一样？关系全乱了，你怎么找？重新建堆？代价太大了

所以，我们建小堆。我们还是头和尾交换，然后用向下调整，我找到了第2小的数，和倒数第二个数交换，以此类推

//堆排序
//O(N*logN)
void HeadSort(int* a, int n)
{
	//向上调整建堆
	/*for (int i = 1;i<n;i++)
	{
		AdjustUp(a,i);
	}*/
	//向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a,n,i);
	}
	int end = n - 1;
	while (end > 0)
	{
		//把根和最小孙子进行交换
		Swap(&a[0], &a[end]);
		//向下调整
		AdjustDown(a, end, 0);
		--end;
	}
	
}

建堆算法的时间复杂度

• 向下调整建堆的时间复杂度

我们以最坏的情况（调整次数最多的情况）---满二叉树 来分析

我们来回顾一下向下调整建堆的过程：

向下调整建堆是从哪儿开始调？

是不是倒数第一个非叶子节点啊?

我们要研究它整个堆的调整次数，我们是不是应该一层一层来看啊？

所以时间复杂度是O（N）

• 向上调整建堆

为什么这两个时间复杂度差这么多呢？

• 向下调整

• 向上调整

我们再来从整体的角度看一下堆排序

从今往后我们用向上调整建堆还是向下调整建堆啊？我们是不是就不会再去使用向上调整建堆了？

那我们来看向下调整建堆，堆排序的时间复杂度

上面是O(N),这个的时间复杂度是多少？

首先，比如我们要排升序,建大堆,然后把根和尾交换。

把最后一层排好，消耗的时间的复杂度是多少？

除了最后一个节点，剩下的每一个节点都要走一次向下调整

这个过程和向上调整建堆的次数是一样的

都是，节点数量多，调整次数多，节点数量少，调整次数少。

它算出来的公式和这个公式是一样的

TOPK问题

N个数，找最大的前K个（N>>K）

方法1

这个方法有个致命缺陷

你怎么办？有人说：“我分四次取，每次取出那一批里最大的前十个，再从这40个中选出最大的前十个。”

那这样你怎么办？

方法2

我们来实现一下

void createData()
{
	//打开文件
    char* data = "Data.txt";
	FILE* fin = fopen(data,"w");
	printf(data);
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	//写入数据
	srand(time(NULL));
	for (int i = 0; i < 1000; i++)
	{
		int data = (rand() % 100000) + i;
		fprintf(fin,"%d\n",data);
	}

	//关闭文件
	fclose(fin);
	fin = NULL;
}

//TOP K
void TOPK()
{
	int k;
	printf("请输入K：");
	scanf("%d", &k);

	//造一个变长数组来存放数据
	int* kminheap = (int*)malloc(k*sizeof(int));
	if (kminheap == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}

	//先读取k个数据
	FILE* fin = fopen("data.txt", "r");
	if (fin == NULL)
	{
		perror("fopen");
		return;
	}
	for (int i = 0;i<k;i++)
	{
		//读取文件中的数据
		fscanf(fin, "%d", &kminheap[i]);
	}

	//用这k个数据建小堆
	for (int i = (k-1-1)/2;i >= 0;i--)
	{
		AdjustDown(kminheap,k,i);
	}

	//把剩下的n-k个数据输入，比堆顶大的插入
	int tmp = 0;
	while (fscanf(fin,"%d",&tmp) > 0)
	{
		if (tmp > kminheap[0])
		{
			//就把它覆盖到堆顶
			kminheap[0] = tmp;
			AdjustDown(kminheap,k,0);
		}
	}

	printf("最大的%d个数为：",k);
	for (int i = 0; i < k ; i++)
	{
		printf("%d ",kminheap[i]);
	}
	printf("\n");
}

int main()
{
	createData();
	TOPK();
	return 0;
}

怎么检测自己是否生成对了呢？

如果都在就对了

算一下时间复杂度：

建一个K个数的小堆是不是O（K）啊？

​​​​​​

剩下的N-K个数（假设极端情况下）每一个数都比它大，都要进堆，进堆是logK

所以是O（（N - K）*logK）

合计：O（N）

简单总结一下

我们在二叉树的顺序结构中讲了这三个东西

它比我们之前的数据结构难在哪儿呢？

我们之前的数据结构只是把它存起来，这个还可以用来排序，多了一点功能性。

下一篇我们将来学习二叉树的链式结构。

作者水平有限，如有错误，欢迎指正！