《数据结构：顺序实现二叉树》

一、树

1、树的结构与概念

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

• 有一个特殊的结点，称为根结点，根结点没有前驱结点。
• 除根结点外，其余结点被分成 M(M>0)个互不相交的集合，其中每个集合又是一颗结构与树类似的子树。每颗自树的根结点有且只有一个 前驱，可以有0个或多个后继。因此树是递归定义的。

树形结构中，⼦树之间不能有交集，否则就不是树形结构

非树形结构：

• 子树是不相交的
• 除根结点外，每个结点有且仅有一个父节点
• 一颗N个结点的树有N - 1条边

2、树相关术语

• ⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点； 如上图：A是B的⽗结点
• ⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点； 如上图：B是A的孩⼦结点
• 结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，F的度为2，K的度为0
• 树的度：⼀棵树中，最⼤的结点的度称为树的度； 如上图：树的度为 6
• 叶⼦结点/终端结点：度为 0 的结点称为叶结点； 如上图： B、C、H、I… 等结点为叶结点
• 分⽀结点/⾮终端结点：度不为 0 的结点； 如上图： D、E、F、G… 等结点为分⽀结点
• 分⽀结点/⾮终端结点：度不为 0 的结点； 如上图： D、E、F、G… 等结点为分⽀结点
• 结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推；
• 树的⾼度或深度：树中结点的最⼤层次； 如上图：树的⾼度为 4
• 结点的祖先：从根到该结点所经分⽀上的所有结点；如上图： A 是所有结点的祖先
• 路径：⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列；⽐如A到Q的路径为：A-E-J-Q；H到Q的路径H-D-A-E-J-Q
• ⼦孙：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图：所有结点都是A的⼦孙
• 森林：由 m（m>0） 棵互不相交的树的集合称为森林；

二、二叉树

1、概念与结构

树形结构中，我们最常⽤的就是⼆叉树，⼀棵⼆叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。

二叉树具备以下特点：

• 1.⼆叉树不存在度⼤于 2 的结点
• 2. ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树

注意：对于任意的⼆叉树都是由以下⼏种情况复合⽽成的

2、满二叉树

⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为 K ，且结点总数是 2k − 1 ，则它就是满⼆叉树。

3、完全二叉树

完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K 的，有 n 个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。

二叉树性质

• 1）若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有 2ⁱ−1 个结点
• 2）若规定根结点的层数为 1 ，则深度为 h 的⼆叉树的最⼤结点数是 2^h − 1
• 3）若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度 h = ${\log }_2(n+1)$ ( log以2为底， n+1 为对数)

三、顺序二叉树存储结构

顺序结构存储就是使⽤数组来存储，⼀般使⽤数组只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费，完全⼆叉树更适合使⽤顺序结构存储。

现实中我们通常把堆（⼀种⼆叉树）使⽤顺序结构的数组来存储，需要注意的是这⾥的堆和操作系统虚拟进程地址空间中的堆是两回事，⼀个是数据结构，⼀个是操作系统中管理内存的⼀块区域分段。

四、实现顺序结构二叉树

⼀般堆使⽤顺序结构的数组来存储数据，堆是⼀种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备其他的特性。

1、堆的概念与结构

如果有⼀个关键码的集合K={ $k_0,k_1,\cdots ,k_{n-1}$，把它的所有元素按完全⼆叉树的顺序存储⽅式存储，在⼀个⼀维数组中，并满⾜： $K_i$<=$K_{2\ast i+1}$，i = 0、1、2… ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆叫做最⼩堆或⼩根堆。

堆具有以下性质

• 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；
• 堆总是⼀棵完全⼆叉树。

顺序二叉树性质

• 对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从0 开始编号，则对于序号为 i 的结点有：
• 1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点
• 2. 若 2i+1<n ，左孩⼦序号： 2i+1 ， 2i+1>=n 否则⽆左孩⼦
• 3. 若 2i+2<n ，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦

2、堆的实现

堆的底层结构为数组，因此定义堆的结构为：

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDateType;typedef struct Heap
{HPDateType* arr;int capacity;int size;
}HP;//初始化
void HPInit(HP* php);//销毁
void HPDesTroy(HP* php);//堆尾插入数据
void HPPush(HP* php, HPDateType x);//向上调整
void AdjustUp(HPDateType* arr, int child);//删除堆顶数据
void HPPop(HP* php);//向下调整
void AdjustDown(HPDateType* arr, int parent,int n);//取堆顶数据
HPDateType HPTop(HP* php);//判断堆是否为空
bool HPEmpty(HP* php);

堆的函数实现：

#include"Heap.h"//初始化
void HPInit(HP* php)
{assert(php != NULL);php->arr = NULL;php->capacity = php->size = 0;
}//销毁
void HPDesTroy(HP* php)
{assert(php != NULL);free(php->arr);php->arr = NULL;php->capacity = php->size;
}//交换
void swap(HPDateType* x, HPDateType* y)
{HPDateType tmp = *x;*x = *y;*y = tmp;
}//向上调整
void AdjustUp(HPDateType* arr, int child)
{assert(arr != NULL);int parent = (child - 1) / 2;while (arr[parent] > arr[child] && child > 0){swap(&arr[parent], &arr[child]);child = parent;parent = (child - 1) / 2;}
}//插入数据
void HPPush(HP* php, HPDateType x)
{assert(php != NULL);//判断空间够不够if (php->capacity == php->size){//增容int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDateType* tmp = (HPDateType*)realloc(php->arr, newcapacity*sizeof(HPDateType));if (tmp == NULL){perror("realloc fail");exit(1);}php->arr = tmp;tmp = NULL;php->capacity = newcapacity;}php->arr[php->size++] = x;AdjustUp(php->arr, php->size - 1);
}//删除数据
void HPPop(HP* php)
{assert(php != NULL);assert(php->size > 0);swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;AdjustDown(php->arr, 0,php->size);
}//向下调整
void AdjustDown(HPDateType* arr, int parent,int n)
{assert(arr != NULL);int child = (parent * 2) + 1;while (child < n){if (child + 1 < n && arr[child + 1] < arr[child]){child++;}if (arr[child] < arr[parent]){swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//取堆顶数据
HPDateType HPTop(HP* php)
{assert(php != NULL);assert(php->size > 0);return php->arr[0];
}//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php != NULL);return php->size == 0;
}

3、堆的排序

运用堆排序时间复杂度大大减小

void HeapSort(int* arr, int n)
{//µint i = 0;int parent = 0;int child = 0;for (i = (n - 1) / 2; i >= 0; i--){parent = i;child = parent * 2 + 1;while (child < n){if (child + 1 < n && arr[child + 1] < arr[child]){child++;}if (arr[child] < arr[parent]){int tmp = arr[child];arr[child] = arr[parent];arr[parent] = tmp;parent = child;child = parent * 2 + 1;}else{break;}}}for (i = n - 1; i > 0; i--){parent = 0;child = i;int tmp = arr[child];arr[child] = arr[parent];arr[parent] = tmp;child = parent * 2 + 1;while (child < i){if (child + 1 < i && arr[child + 1] < arr[child]){child++;}if (arr[child] < arr[parent]){tmp = arr[child];arr[child] = arr[parent];arr[parent] = tmp;parent = child;child = parent * 2 + 1;}else{break;}}}
}