【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

前言：

之前我们学习了顺序表、链表以及栈和队列这些数据结构，但这些数据结构都是线性的（一对一）。接下来要学习非线性的数据结构——树（二叉树），相比前面的，树的结构更加复杂，话不多说，直接进入正题吧。

一、树的概念及结构

1.树的概念

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

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

现实中的树和数据结构中的树，例如：

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

2.树的相关概念

树的相关概念是指树的根、分枝和叶子等等之间的联系，与人类的亲缘关系类似。

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A是一对6，所以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）棵互不相交的树的集合称为森林；

注意：在计算节点的层次的时候，从最上面的节点往下数可以从0开始，也可以从1开始，但是更推荐从1开始。
因为树可能是空树、只有一个节点的树或者是有多个节点的树，如果从0开始计算，那么节点的层次（或者说树的高度）当为0时到底是空树还是只有一个节点的树不易分清，所以为了方便数树的高度，从1开始比较好。

3.树的存储

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。（又称左孩子右兄弟表示法）

struct TreeNode
{int val;struct TreeNode* firstchild;struct TreeNode* nextbrother;
};

一个节点可以任意指向多个节点，这个节点的firstchild指针指向它的第一个孩子节点（没有则指向空指针），nextbrother指针指向它的兄弟节点（没有则指向空指针）。

先找到第一个孩子，（例如B是A的第一个孩子）然后此时的第一个孩子再找他的兄弟，直到为空指针结束。

TreeNode* Anode假设为节点A
找A的第一个孩子B节点：TreeNode* child = Anode->firstchild；
while(child)直到空结束
{
…………
child = child->nextbrother;
}

4.树在实际中的运用

我们平时使用电脑文件系统的目录就是树结构，打开此电脑，有D盘、C盘等，每层又有多个文件。

二、二叉树概念及结构

1.概念

一棵二叉树是结点的一个有限集合。
1.最多两个节点，也可以是1个或者0个
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出，二叉树不存在度大于2的结点，并且二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

现实中的二叉树：

2.特殊的二叉树

（1）满二叉树

概念：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为h，且结点总数是2^h - 1 ，则它就是满二叉树。

每一层都是满的：2^(i-1)个节点（i是某一层的位置）
F(h) = 2 ^ 0 + 2 ^ 1 + ……+2 ^ (h-2) + 2 ^ (h-1)等比数列求和

假设这个二叉树的节点是N个
N = 2 ^ h - 1 => h = log(N+1) （log以2为底）

（2）完全二叉树

概念：完全二叉树是在满二叉树的基础上变化的。假设它的高度是h，那么它的前h-1层是满的，最后一层可能是满的，也可能是不满的，并且它的最后一层必须从左到右是连续的。满二叉树是特殊的完全二叉树。

因此，完全二叉树的节点总个数是有范围的。当它为满二叉树时，也就是节点总个数最多的情况下，它的节点总个数是2^h - 1；当最后一层只有一个节点，也就是节点总个数最少的情况下，它的节点总个数是2 ^ (h-1)，所以节点范围：【2 ^ (h-1) ， 2 ^ h - 1】。

3.二叉树的性质

1.如果根节点的层数为1，则一个非空二叉树的第h层最多有2^(h-1)个节点；
2.如果根节点的层数为1，则深度为h的二叉树最多一共有2^h-1个节点；
3.对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2，则满足公式n0=n2+1；
4.若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log(n+1)

4.二叉树的存储

二叉树的存储方式分为顺序存储和链式存储。

(1)顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

使用数组存储时有一个规律：

可在任意位置通过下标找到父亲或者孩子
注意：前提是满二叉树或者完全二叉树才能用这个规律

所以，对于非完全二叉树，使用链式结构存储更适合。

总结：满二叉树或者完全二叉树适合用数组存储

(2)链式存储

二叉树的链式结构是用链表来表示一个二叉树，分为三个作用域（数据域和左右指针域），左右指针来存储左右孩子的地址。

三、二叉树的顺序结构及实现

1.二叉树的顺序结构

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

2.堆的概念及结构

堆：非线性结构的二叉树，更准确的说是完全二叉树。适合用数组存储。

堆分为两种：根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
小堆：树中任意一个父亲都<=孩子（比的是节点的值）
大堆：树中任意一个父亲都>=孩子

3.堆的实现

（1）初始化堆

初始化堆有两种方式。
第一种：把结构体指向的数组里面置空（没有元素），有效个数和容量置为0

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

第二种：接收外来数组的大小n，动态开辟大小为n的空间，把数据拷贝到结构体指向的数组里

void HPInitArray(HP* php, HPDataType* a, int n)
{assert(php);assert(a);php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->a == NULL){perror("malloc fail");exit(-1);}php->size = n;php->capacity = n;memcpy(php->a, a, sizeof(HPDataType) * n);for (int i = 1; i < n; i++){AdjustUp(php->a, i);}

AdjustUp 是向上调整算法，下面会分析。

（2）销毁堆

堆的销毁不必多说，与顺序表的销毁相同

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

（3）堆的插入

堆的插入采用顺序表的尾插（一个一个插入），因为数组的尾插效率高（还有尾删，后面也会用到）。插入数据要考虑扩容，因为前面初始化的时候空间大小为0。这里可以设置一个变量newcapacity，用条件操作符，如果容量为0，就给初始容量4，否则就是原来容量的两倍。扩容完插入新的数据，元素个数++。

void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* ptr = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (ptr == NULL){perror("realloc fail");exit(-1);}php->a = ptr;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);//向上调整
}

难道把外来的数据一个一个插入就行了吗？其实不然，我们插入数据后要使结构体指向的数组变成一个堆，这里要介绍一个算法。

向上调整算法

从最后一个叶子节点开始向上调整。以建小堆为例，插入一个新的数据为最后一个叶子节点，小堆的特点是父节点<=孩子节点，所以要先找到父节点。

公式：parent = (child - 1) / 2

我们知道，堆的实现虽然是二叉树，但它的存储方式本质是数组，空间是连续的，所以可以通过孩子节点下标找到父节点。这时孩子节点可以与父节点比较，如果父节点大于孩子节点，就交换，然后孩子节点向上到达父节点的位置，原来父节点到达它的父节点的位置。注意控制孩子节点的范围，孩子节点不可能是堆顶元素，否则就会越界，所以child>0。如果父子节点大小关系满足小堆特点，就跳出循环，此时该数组就是小堆了。

向上调整的前提：该数组原来是小堆或者大堆

既然如此，那插入一个数据前怎么知道这个数组已经是小堆或者大堆了呢？其实这里指针所指向的数组原来什么也没有，是一个一个插入数据的，而我每插入一个数据就调整一次，相当于说我要插入下一个数据时前面的数据已经调整为小堆了，那么插入下一个数据我就调整这个数据和它的父节点的关系就行了。

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[parent] > a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}

（4）堆的删除

删除堆的一个元素采用顺序表的尾删，但是这里要注意的是仅仅删除堆的最后一个元素是没有意义的。假如是小堆，那么它有个特点，它的堆顶元素一定是所以元素里最小的，所以应该删除堆顶元素。可是数组的头删要挪动数据，比较麻烦，所以这里把堆顶元素与最后一个元素交换，然后再尾删，就可以把最小的元素删除了。但是删除之后，堆顶的元素大小就不确定了，此时不一定是小堆。这里要介绍另一个算法。

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);
}

向下调整算法

从堆顶元素开始往下调整，因为前面的铺垫只改变了堆顶元素，所以堆顶元素是父节点，可以通过以下公式找到它的孩子节点：

左孩子：child = parent * 2 + 1
右孩子：child = parent * 2 + 2

那么问题来了，是选择左孩子还是选择右孩子？这里我们可以默认选择左孩子，然后加一个判断，如果左孩子的值大于右孩子的值，左孩子下标加1，变成右孩子。因为向下调整变成小堆父节点所要交换的节点是两个孩子节点中的较小的。接着比较父节点与孩子节点的大小关系，如果父节点大于孩子节点，就交换（父节点与孩子交换就是与较小的孩子节点交换），然后父节点到达孩子节点的位置，孩子节点到到达它的左孩子节点的位置。不满足条件说明此时是小堆就跳出循环。

注意：这里要控制一个细节，孩子节点下标的范围小于元素个数。同时，如果一个父节点只有一个孩子节点的情况下（只有左孩子），那么这个左孩子的下标加1就越界了。
child + 1 < n ——这个条件成立说明只有左孩子没有右孩子

void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]){                         child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

（5）获取堆顶元素/堆的元素个数/判空

//获取堆顶元素
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}
//获取堆的元素个数
int HPSize(HP* php)
{assert(php);return php->size;
}
//堆的判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

4.堆排序

我们要把堆里面的数据排序（以升序为例），有两种方式，一个是打印出来有序，另一个是原地使数组有序。

（1）堆排序版本1

把数据一个一个插入堆中，只要数组不为空就取堆顶元素，然后删除堆顶元素，直到把所有元素打印出来为升序。

void HeapSort(int* a, int n)
{HP hp;HPInit(&hp);int i = 0;for (i = 0; i < n; i++){HPPush(&hp, a[i]);}HPPrint(&hp);while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);}HPDestroy(&hp);
}

这个方法有缺点：
1.频繁的扩容造成空间复杂度的消耗
2.先要有一个堆的数据结构

（2）堆排序版本2——对数组原地排序

假如一个数组进行堆排序后还要使用，此时只对它打印出来排序就不适合了。所以要对数组原地进行堆排序，使数组的内容有序。

例如：
原来的数组：65,100,70,32,50,60
排序后的数组：32,50,60,65,70,100

在排序前我们要建堆，那么是建小堆还是建大堆？
先来建小堆：
以升序为例，我们在前面的堆排序是打印出来的，用向上调整法是建小堆。这里也用建小堆的方法，小堆建成后堆顶的元素是最小的，所以这个元素排在数组的第一个；然后是次小的，依次从前往后排，直到把数组里的元素从前往后全部排完就是升序了。

但是先以建小堆的方法有缺陷：
分析：堆顶的元素是堆当中最小的依次对应数组从前往后排，每次排完一个数据，要从后面的数据中找出次小的，但问题在于排完的那个数据的后一个数据不一定是次小的，所以后面的数据要重新建堆，重新建的堆的堆顶元素就是次小的。而每次重新建堆使时间复杂度变大，造成效率很低。

向上调整法一个数据遍历时时间复杂度为：logN
有N个数据所以建堆的时间复杂度为：N * logN
每排完一个数据都要建堆一次时间复杂度为：N * (N * logN)
相当于建N次小堆

所以这里应该是建大堆，大堆的堆顶是堆中最大的元素，可是它排在数组的第一个位置，怎么让它到数组的最后一个位置呢？

在这步可以采用堆的删除的思路。把堆顶的元素与最后一个元素交换，这时最大的元素就到了它应该在的位置，然后接下来的步骤很关键，不是真的把最后一个元素删除，那最大的元素排在最后不就没了吗？所以这里我们可以定义一个变量end，它指向的是数组的最后一个元素，完成交换后向下调整，调整的范围是0（第一个元素）到end的有效个数，注意，这时end指向的那个元素不在调整的范围内。然后end减1，控制end>0循环，因为最后只有一个元素就不需要调整了，它是最小的。

//建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}//调整int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}

（3）优化堆排序版本2及时间复杂度的比较

相较于向上调整法建堆，使用向下调整法建堆的时间复杂度更优秀。前面我们都是使用向上调整法建堆，那么用向下调整法是怎么建堆的呢？

我们知道，用向上调整法建堆是从最后一个节点开始，找它的父节点然后进行比较完成建堆。

调整的执行总次数：每层数据个数 * 向上或向下移动的层数

向上调整法时间复杂度的计算
如图：

向下调整法建堆：
前面使用向下调整法是从堆顶开始向下调整，依次比较。这里不是从堆顶开始，而是从下面开始调整。找到最后一个父节点，（只要是父节点一定有孩子节点），然后进行比较、调整；接着再到前一个父节点进行前面的操作，最终建成堆。

找最后一个父节点：
最后一个孩子节点：child = n-1
有孩子找父亲：（child-1）/ 2
所以最后一个父节点：(n - 1 - 1) / 2

向下调整法时间复杂度的计算
如图：

通过对比：向上调整与向下调整的总次数相比多了2 ^ (h-1)，也就是说多了一层（最后一层）的计算。最后一层占比大约整体的一半，所以向下调整法建堆更好。

void HeapSort(int* a, int n)
{//建堆//选择向上调整——O(N*log(N))/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*///选择向下调整——O(N)int i = 0;for ( 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--;}
}

（4）TopK问题

假设有N个数据，找出最大的前K个

1.读取文件的前K个数据，在内存数组中建一个小堆
2.再依次读取后面的数据，跟堆顶元素比较，只要比堆顶元素大就替换堆顶元素进堆，然后向下调整
3.读完所有数据，堆里面的数据就是最大的前K个

这个方法很巧妙，建小堆这样堆顶的元素是堆中最小的，只要比它大就交换进堆。大的数据进堆往下沉在堆底，只有堆里面是最大的前K个才没有交换。当堆里面是最大的前K个时，因为是小堆，堆顶是堆中元素最小的，但是它又比不在堆里面的元素都要大。就算刚开始堆里面已经有K-1个元素在所有元素最大的前K个元素的范围内，进行向下调整保持小堆那么必然有一个元素在堆顶且这个元素小于后面的某个数据，读取到后面的那个元素就交换然后向下调整，最大的前K个就找到了。
如果是建大堆，大堆的堆顶元素是堆中最大的，比它大才能进堆，万一刚开始的堆建好后正好堆顶的元素是所有元素中最大的，那岂不是把所有元素都挡住了。

void PrintTopK(const char* file, int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail");return;}int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("minheap 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);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (minheap[0] < x){minheap[0] = x;AdjustDown(minheap, k, 0);}}for (i = 0; i < k; i++){printf("%d ", minheap[i]);}free(minheap);fclose(fout);
}
void CreateNDate()
{// 造数据int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = rand() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
int main()
{CreateNDate();PrintTopK("data.txt", 5);return 0;
}

感谢观看~