一，树的概念及结构
1.树
4.结点的度：一个节点含有子树的个数称为该结点的度；如：A 的度为6.
5.叶节点或终端节点：度为0的节点称为叶节点；如：B
6.非终端结点或分支节点：度部位0的结点；如：D
7.双亲结点或父节点：若一个结点含有子节点，则这个节点称为其子节点的父节点；如：A是B的8.父节点。
8.孩子节点或子节点：一个结点含有的子树的根结点称为该节点的子节点；如：B是A的函子结点。
9.兄弟节点：具有相同的父结节点称为兄弟节点；如上图：B，C是兄弟节点。
10.树的度：一颗树中，最大使得节点称为树的度；如：上图树的度为6。
11.节点的层次：从根节点定义起，根为第一层，根的子节点为第二层，以此类推。
12.堂兄弟节点：双亲在同一层的节点互为堂兄弟。如：H，I互为堂兄弟。
13.节点的祖先：从根到该节点所经分支上的所有节点。如：A是所有节点的祖先。
14.子孙：以某节点为跟的子树中任意节点都称为该节点的子孙，如：所有的节点都是A的子孙。
15.森林：有m（m>0)棵互不相交的属的集合称为森林。
2.二叉树
1.二叉树结点度最大为2。
2.二叉树子树左右次序不能颠倒，二叉树是有序树。
（1）满二叉树
二叉树的每层节点数都达到最大值。
（2）完全二叉树
二叉树深度为h，除第n层外，其他层的节点数都达到最大，而且h层所有的结点都集中在左层。
（3）二叉树的性质
设根节点层数为1
1.非空二叉树i层最多有2^(n-1）个结点。
2.深度为h的二叉树最多有2^h -1个结点。
3.二叉树储存结构
1.顺序结构
用数组储存，物理上是数组，逻辑上是二叉树。
2.链式储存
用链表表示二叉树，表的每个节点由数据和左右指针（对应左右孩子）组成，可以分为二叉链表和三叉链表。
二叉链表 三叉链表
二叉树 二叉链表 三叉链表
二，实现二叉树顺序结构
1.堆
只有大堆和小堆
堆是完全二叉树
2.实现堆
创建结构体
//创建小堆
typedef int HPDataType;//以数组的形式实现完全二叉树typedef struct Heap
{HPDataType* a;//创建指针数组size_t capacity;//容量size_t size;//大小
}HP;初始化
类比顺序表
//初始化
void HPInit(HP* php)
{//断言,防止传递的指针为野指针assert(php);//初始化php->a = NULL;php->capacity = php->size = 0;
}销毁堆
//销毁
void HPDestroy(HP* php)
{//断言assert(php);//释放申请的内存free(php->a);php->a = NULL;//置空php->capacity = php->size = 0;
}插入数据
向上调整：先将数据插入到堆中，向上调整。找到子节点和这个子节点的父亲，比较大小。交换父亲和孩子结点的值，循环下去，child位于祖先结点时，循环结束。
void Swap(HPDataType* a, HPDataType* b)
{HPDataType tmp = *a;*a = *b;*b = tmp;
}void AdjustUp(HPDataType* a, size_t child)
{//找到子节点，以及这个孩子的父亲size_t parent = (child - 1) / 2;//比较父亲和孩子的大小while (child > 0){if (a[parent] > a[child]){Swap(&a[parent], &a[child]);}else{break;}child = parent;parent = (child - 1) / 2;}
}
//插入数据，保证堆还是小/大堆
void HPPush(HP* php, HPDataType x)
{//断言assert(php);//判断是否要扩容if (php->capacity == php->size){size_t newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;//realloc动态开辟空间HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}else{php->a = tmp;php->capacity = newcapacity;}}//插入数据php->a[php->size] = x;php->size++;//向上调整堆，保证其还是一个小堆AdjustUp(php->a, php->size - 1);
}打印“堆”
void HPPrint(HP* php)
{for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}删除堆顶的数据
将头结点和尾结点数据交换 然后size--，再向下调整。
AdjustDown(HPDataType* a, size_t size, size_t root)
{size_t parent = root;size_t child = parent * 2 + 1;//while (child < size){//找出孩子中较小的那一个,注意完全二叉树可能不存在右孩子//确定左右子树谁的值更小if (a[child] > a[child + 1] && child + 1 < size){//默认是左<右，这里是判断调整child++;}//如果孩子小于父亲就交换if (a[child] < a[parent]){Swap(&a[parent], &a[child]);}else{break;}//继续向下调整parent = child;child = parent * 2 + 1;}
}
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);
}判断堆是否为空
size指向数组下一位 如果为空则是空
bool HPEmpty(HP* php)
{assert(php);//用表达式的返回值来判断，为0就为空return php->size == 0;
}返回栈顶的值
size_t HPSize(HP* php)
{assert(php);//根据数组的性质，可直接返回size的值return php->size;
}堆的大小
直接用size的值
HPDataType HPTop(HP* php)
{assert(php);//堆不为空assert(php->size > 0);return php->a[0];
}堆排序
升序用大堆，降序用小堆。
以大堆为例
1.构造大堆，数组最大值就是根节点
2.顶端数与末尾数交换
3.反复执行2.
建造大堆：
首先将无序数组看做堆结构，按照综上到下，从左到右依次填入二叉树中。
从最后一个非叶子结点即6，比较她左右节点较大值如果比6大就交换位置。
例如这里6和9需要交换。
找到下一个非叶子节点4重复上述步骤
如此重复操作得到大堆 接下来进行排序
堆排序算法步骤
1.把无序数组构造成二叉树堆（以大堆为例）。
2.堆顶就是序列最大值，将堆顶与末尾元素交换，此时末尾就是最大值。
3.将剩余n-1个元素重新构造成一个堆，即重复1，2.
如此得到有序序列
堆排序不稳定
空间复杂度为O(1)
平均的时间复杂度为O(nlogn)
最坏情况下也稳定在O(nlogn)
void HeapAdjust(int* arr, int start, int end)
{int tmp = arr[start];for (int i = 2 * start + 1; i <= end; i = i * 2 + 1){if (i < end&& arr[i] < arr[i + 1])//有右孩子并且左孩子小于右孩子{i++;}//i一定是左右孩子的最大值if (arr[i] > tmp){arr[start] = arr[i];start = i;}else{break;}}arr[start] = tmp;
}
void HeapSort(int* arr, int len)
{//第一次建立大根堆，从后往前依次调整for(int i=(len-1-1)/2;i>=0;i--){HeapAdjust(arr, i, len - 1);}//每次将根和待排序的最后一次交换，然后在调整int tmp;for (int i = 0; i < len - 1; i++){tmp = arr[0];arr[0] = arr[len - 1-i];arr[len - 1 - i] = tmp;HeapAdjust(arr, 0, len - 1-i- 1);}
}
int main()
{int arr[] = { 9,5,6,3,5,3,1,0,96,66 };HeapSort(arr, sizeof(arr) / sizeof(arr[0]));printf("排序后为:");for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){printf("%d ", arr[i]);}return 0;
}
