前言

二叉树是树形结构的基础，也是面试高频考点。本文使用C语言实现二叉树，包含：
堆是基于数组实现的完全二叉树，属于顺序结构；二叉树本文实现链式二叉树。
本文包含：
1.堆：大顶堆、堆初始化、插入、删除、堆排序、TOPK问题
2. 链式二叉树：结点定义、前/中/后序递归遍历、队列实现层序遍历
3. 完整可运行C代码

堆

堆的概念

堆本质是完全二叉树，但是它不用指针链式存储，而是用数组顺序存储。
堆满足一个核心性质：父子结点之间有大小关系，分为两种：

1. 大堆：任意一个父结点的值 ≥ 左右孩子结点的值
   堆顶（数组第一个元素）是整个堆里最大值
2. 小堆：任意一个父结点的值 ≤ 左右孩子结点的值
   堆顶是整个堆里最小值
   

堆的实现

向上调整算法ADjustUp

1.先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后
2.插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可

向下调整算法ADjustDown

1.将堆顶元素与堆中最后⼀个元素进⾏交换
2.删除堆中最后⼀个元素
3.将堆顶元素向下调整到满⾜堆特性为止

TOP-K问题

1.⽤数据集合中前K个元素来建堆
求前k个最⼤的元素，则建⼩堆
求前k个最⼩的元素，则建⼤堆
2.⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素
将剩余N-K个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素

链式二叉树

概念

链式二叉树，就是用指针链接的方式存储二叉树，不再像堆那样用数组顺序存储。
每一个结点独立开辟内存，结点内部包含三部分
1.数据域：存放结点的数据
2. 左指针：指向左孩子结点
3. 右指针：指向右孩子结点

链式二叉树的实现

函数递归栈帧图

层序遍历