二叉树和堆

树概念及结构（了解）

树的概念（看看就行）

树是一种 非线性 的数据结构，它是由 n （ n>=0 ）个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的 。 有一个特殊的结点，称为根结点 ，根节点没有前驱结点。除根节点外，其余结点被分成 M(M>0) 个互不相交的集合 T1 、 T2 、 …… 、 Tm ，其中每一个集合 Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有 0 个或多个后继 因此，树是递归定义 的。

注意，二叉树习惯把问题切分为子问题

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

树的相关概念（了解）

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

树的表示（了解）

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

typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};

树在实际中的运用（表示文件系统的目录树结构）

二叉树概念及结构

概念

一棵二叉树是结点的一个有限集合，该集合 :

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

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

现实中的二叉树：

特殊的二叉树：（满二叉树是一种特殊的完全二叉树）

高度为h的满二茶树最多有多少节点

高度是h的完全二叉树节点范围

二叉树的性质（小题会用到）

n0=n2+1

根据这个式子和完全二叉树的特点（度为1的结点只有1个或0个）度意思是孩子个数

二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1. 顺序存储

完全二叉树适合顺序存储，可以看成数组，后边的堆就是顺序存储，左孩子下标=父亲下标*2+1，右孩子下标等于父亲下标*2+2

父亲下标=（孩子下标-1）/2-》以上只适用于完全二叉树，非完全二叉树适合链式存储

2. 链式存储

链式存储适合不连续的存储

堆的概念及结构（是数据结构，不是内存划分的那个堆）

堆是非线性结构，完全二叉树

大堆：树中任意一个父亲都>=孩子      小堆：树中任意一个父亲都<=孩子    

底层物理结构是数组，逻辑结构是完全二叉树

注意：小堆不代表底层数组是升序的，仅仅是任意父亲与孩子之间满足关系而已

所以小堆的根就是整个堆的最小值

这道题就是将给的值进行顺序排列，从第一层往下写，最后观察是否满足堆的规则，可以看到这个是大堆，满足任意父亲大于=孩子

这里有几道选择题可以做做，答案全是c，因为很简单，就不赘述了

堆的实现

堆向下调整算法（logN）

void AdjustDown(HPDataType* a, int n, int parent)//a是数组首元素地址，n是元素个数，parent是父亲下标
{int child = parent * 2 + 1;//求出左孩子下标while (child < n)（孩子下标超过数组元素个数，说明已经越界，跳出循环）{if (child + 1 < n && a[child + 1] <a[child])//首先判断是否有右孩子，并且找出小的那个孩子{++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);// 继续往下调整parent = child;child = parent * 2 + 1;}else{break;//不需要再调整}}
}

假设是小堆调整

基本思想：向下调整算法前提下边是小堆或者大堆，如果是小堆，把（左右孩子）小的往上调，大的往下调；如果是大堆，把（左右孩子）大的往上调，小的往下调-》基本思路就是大/小的往下沉，小/大的往上调

堆的向上调整算法（假设是小堆）(logN）

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//父亲下标while (child > 0)//循环结束条件孩子下标=0{if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else//满足小堆的特点，父亲小于孩子，就跳出{break;}}
}

向上调整算法的思路也很简单，以小堆为例，孩子小于父亲就交换，可以看出每轮交换结束任意一个非叶子节点和其两个孩子都满足父亲小于孩子。

总结：两种调整算法都需满足堆的特性，向上调整需满足前面的数据是堆，向下调整需满足下面的数据是堆，整体思路就是让每个节点都满足父亲大于等于孩子（大堆），父亲小于等于孩子（小堆）

上述具体代码处有解释，包能学会代码

堆的创建

从倒数第一个非叶子结点开始调（也就是最后一个叶子节点的父亲）

最后一个叶子结点下标是n-1，其父亲就是（(n-1)-1）/2，调整到i=0位置结束

为什么可以这样调整呢，假设期望调整为大堆，每一轮循环调整都是将三个数中最大的调整为父亲，两个儿子都比当前节点小，从倒数第一个父亲开始到第一个父亲，每次调整都满足这个关系-》父亲>=两个儿子，父亲小就往下调，儿子大的就往上调。最后成为一个名副其实的大堆

可以将三个数据看成一个整体更好理解（父节点+两个孩子节点）基本思想就是父亲恒大于或者小于孩子

           调整前                                             调整后

向上调整建堆

从第二个数据开始向上调整，每次都可以把前面的数据看成堆，调整到最后一个数据，下标是i=n-1结束

建堆时间复杂度（记住结论即可）

堆的插入

void HeapPush(HP* php, HPDataType x)
{assert(php);// 扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);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 HeapPop(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);
}

先交换第一个和最后一个数据，再删除最后一个数据，再从第一个元素位置向下调整，接着重复这个过程

堆的应用

堆排序（时间复杂福是N*logN）

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

升序：建大堆

降序：建小堆

2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

 //升序
void HeapSort(int* a, int n)
{// 建堆 （大堆）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;}
}

堆排序思路很简单，就是先建堆（在原数组上建堆就可以），升序建大堆，大堆第一个数据总是最大的，然后将第一个数据和最后一个数据交换，end--，将前面的数据看成一个数组，再次选出最大的和最后一个交换，再end--，循环往复这个过程，就能得到升序数组了

测试排序数组，先测降序

升序

topk问题

void PrintTopK(const char* filename, int k)
{// 1. 建堆--用a中前k个元素建堆FILE* fout = fopen(filename, "r");if (fout == NULL){perror("fopen fail");return;}int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc fail");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}// 前k个数建小堆for (int i = (k - 2) / 2; i >= 0; --i){AdjustDown(minheap, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minheap[0]){// 替换你进堆minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}printf("\n");free(minheap);fclose(fout);
}// fprintf  fscanfvoid CreateNDate()
{// 造数据int n = 10000000;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() + i) % 10000;//表示数据最大值也小于10000fprintf(fin, "%d\n", x);}fclose(fin);
}int main()
{CreateNDate();//PrintTopK("data.txt", 10);return 0;
}

TopK问题思路也很简单，就是先造n个数据并写入文件-》将前k个数建立一个小堆-》将剩余n-k个元素和堆中第一个数据比较，大于就交换，然后从第一个数据向下调整，直到数据流最后一个数据被读取结束，堆中存放的是我们造的数据前100大元素，堆顶是第100大元素

如图是前10大数据

堆实现完整代码

Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include<time.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);void Swap(HPDataType* p1, HPDataType* p2);
void HeapPrint(HP* php);
void HeapInit(HP* php);void HeapDestroy(HP* php);//堆的销毁
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);//堆顶元素
bool HeapEmpty(HP* php);//堆的判空

Heap.c

#include"Heap.h"void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child]< a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}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[child] <a[parent]){Swap(&a[child], &a[parent]);// 继续往下调整parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPush(HP* php, HPDataType x)
{assert(php);// 扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);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 HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}void HeapPop(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 HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"int main()
{int a[] = { 65,100,70,32,50,60 };HP hp;HeapInit(&hp);//堆初始化for (int i = 0; i < sizeof(a)/sizeof(int); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);//打印堆int k = 5;//打印前K大数据while (!HeapEmpty(&hp) && k--){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestroy(&hp);return 0;
}

二叉树链式结构的实现

二叉树的遍历

再看二叉树基本操作前，再回顾下二叉树的概念， 二叉树是：

前序遍历：根 左子树 右子树（局部和宏观都满足这个顺序才行）

中序遍历：左子树  根 右子树

后序遍历：左子树 右子树 根

层序遍历：一层一层往后遍历

记住！！二叉树基本上都是递归实现的，递归看似复杂实际上也就是大问题化小问题，只需在意每个子问题的解法

比如前序遍历代码，确实会一层一层展开递归，但是每一层递归都是先判空，然后打印根，递归左子树，递归右子树

如何理解递归

递归不要太在意递归展开图，要不然很复杂的题目根本没时间想展开图，先找相同子问题，比如后序遍历就是先递归左子树，再递归右子树，再打印根，我们写这一个函数，内部是层层递归实现的，所以我们只关心某一个子问题如何解决，再注意一下递归函数出口（根节点结束），基本上就实现递归的功能了

手动构建二叉树的代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>// 不是增删查改，学习二叉树结构
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;int val;
}BTNode;BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->val = x;node->left = NULL;node->right = NULL;return node;
}void PrevOrder(BTNode* root) {if (root == NULL) {printf("NULL ");return;}printf("%d ", root->val);PrevOrder(root->left);PrevOrder(root->right);
}void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}// 节点个数
//int TreeSize(BTNode* root)
//{
//	static int size = 0;
//	if (root == NULL)
//		return 0;
//	else
//		++size;
//
//	TreeSize(root->left);
//	TreeSize(root->right);
//
//	return size;
//}//int size = 0;
//int TreeSize(BTNode* root)
//{
//	if (root == NULL)
//		return 0;
//	else
//		++size;
//
//	TreeSize(root->left);
//	TreeSize(root->right);
//
//	return size;
//}int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}// 叶子节点个数
int TreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL){return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}// 第k层的节点个数
int TreeKLevel(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1){return 1;}return TreeKLevel(root->left, k - 1)+ TreeKLevel(root->right, k - 1);
}int main()
{// 手动构建BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;PrevOrder(node1);printf("\n");InOrder(node1);printf("\n");PostOrder(node1);printf("\n");printf("%d\n", TreeSize(node1));//size = 0;printf("%d\n", TreeSize(node1));return 0;
}

该代码包括前中后序基本代码和求结点个数/叶子结点个数/第k层节点个数

前中后序很简单，我们说一下求总结点和叶子结点

求总结点有三种办法

第一种，结点是空返回0，反之++size-》递归左子树-》递归右子树

每一个栈帧都是执行这个过程，走到空节点返回栈帧，逐层返回，最后一次返回第一个栈帧

size=6，没想明白的可以画一下递归展开图，根据原理很好画的，这里我画图不好看就不画了（画图之后就很好理解了，递归初期要多画图，慢慢理解领悟递归的魅力）

第二次打印size要置空，因为size是全局变量，只有main函数结束才会销毁，不置空会打印12，也可以将size定义成静态全局变量（也是出main函数才会销毁，不可定义成局部静态，因为作用域是局部的，外边访问不到），是一个道理

最简洁写法 是空返回0，非空返回自身+左子树+右子树，没想明白可以画图，递归划分成子问题-》分治思想-》求当前树结点-》自身结点+左子树+右子树，左子树也看成自身结点+左子树+右子树，右子树也是自身结点+左子树+右子树-》加完之后层层返回得到总结点

求叶子结点个数也很简单，就是控制两个出口（节点为空返回0，叶子结点返回1），如果不是空节点和叶子结点，进入左子树递归+右子树递归，最后层层返回也就是叶子结点之和

还有一些二叉树oj题，可以直接在力扣上搜题目，可以练习一下

感谢大家的支持！！！这是基础部分讲解后续有新的会补充的