二叉树

树的存储表示

1、使用指针数组

弊端：只有根节点的度是6，其他结点小于6，就会浪费定义的指针

2、使用顺序表

优势：每个结点有几个孩子就插入几个孩子，不够就再扩容

C不太好表示

C++有一个库叫vector就是顺序表，vector<struct TreeNode*>subs

3、左孩子右兄弟表示法

windows文件目录就是一个森林

二叉树：

是一个特殊的树，结点的度最大为2

存储：

1、顺序存储

2、链式存储

完全二叉树：

前h-1层是满的，最后一层可以不满，但是从左到右必须连续存在

非完全二叉树就不适合数组结构存储，只适合链式存储

满二叉树：

结点的度都为2

二叉搜索树：

左子树小于右子树，不是完全二叉树

查找数字是只需要和根结点比大小，最多查找高度次

AVL树：

红黑树：

堆

堆逻辑结构是完全二叉树，存储结构是数组

堆不一定有序，孩子之间没有大小关系

以上都不是堆

数据结构的堆：

完全二叉树，是一个数据结构

操作系统的堆：

内存区域的划分

是不同学科里的同名名称

意义：

1、堆排序

时间复杂度为O(N*logN)，根是最大的，只需要调整高度次顺序

1000h=10（N）

100wh=20

100亿h=30

2、top k问题

N个数里面找最大前k个（N远大于k）

实践

思路：

push：

向上调整算法时间复杂度是高度次，也就是O(logN)。和向下调整算法一样

pop：

不能挪动删除

首尾交换，尾删掉原来的头结点，再对上面那个小三角使用向下调整算法，也就是选取根节点的最小子节点进行算法运算

将受到影响的最小子节点所在的树一直更新，循环使用算法运算直到到叶子结点

那么怎么判断到达叶子结点，先照旧算出子节点的下标值，再和size比较

这样子树都没有被破坏，依旧是小堆

Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;typedef struct Heap {HPDataType* a;int size;int capacity;
}HP;void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPush(HP* php, HPDataType x);
//规定删除根结点
void HPPop(HP* php);
HPDataType HpTop(HP* php);
size_t HPSize(HP* php);
bool HPEmpty(HP* php);

Heap.c

#define  _CRT_SECURE_NO_WARNINGS
#include"Heap.h"void HPInit(HP* php) {assert(php);php->a = NULL;php->capacity = 0;php->size = 0;
}void HPDestroy(HP* php) {assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}void Swap(HPDataType* p1, HPDataType* p2) {//只交换内部的值HPDataType* tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child) {//child和parent都是下标int parent = (child - 1) / 2;while (child > 0) {if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;//往上走}elsebreak;}
}void HPPush(HP* php, HPDataType x) {assert(php);if (php->capacity == php->size) {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;php->size++;//调整顺序AdjustUp(php->a, php->size - 1);
}void AdjustDown(HPDataType* a, int size, int parent) {int child = parent * 2 + 1;//child为小的孩子while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {//交换成小的孩子时，要保证父节点有右孩子++child;}if (a[parent] > a[child]) {Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else {break;}}
}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);
}HPDataType HpTop(HP* php) {assert(php);assert(php->size > 0);return php->a[0];
}size_t HPSize(HP* php) {assert(php);return php->size;
}bool HPEmpty(HP* php) {assert(php);return php->size == 0;
}

Test.c

#define  _CRT_SECURE_NO_WARNINGS
#include"Heap.h"int main() {int a[] = { 4,6,2,1,5,8,2,9 };HP hp;HPInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {HPPush(&hp, a[i]);}获取最小的前k个//int k = 3;//while (k--) {//	printf("%d\n", HpTop(&hp));//	HPPop(&hp);//}while (!HPEmpty(&hp)) {printf("%d ", HpTop(&hp));HPPop(&hp);}printf("\n");return 0;
}