文章目录前言堆堆的概念堆的实现向上调整算法ADjustUp向下调整算法ADjustDownTOP-K问题链式二叉树概念链式二叉树的实现函数递归栈帧图层序遍历前言二叉树是树形结构的基础也是面试高频考点。本文使用C语言实现二叉树包含堆是基于数组实现的完全二叉树属于顺序结构二叉树本文实现链式二叉树。本文包含1.堆大顶堆、堆初始化、插入、删除、堆排序、TOPK问题2. 链式二叉树结点定义、前/中/后序递归遍历、队列实现层序遍历3. 完整可运行C代码堆堆的概念堆本质是完全二叉树但是它不用指针链式存储而是用数组顺序存储。堆满足一个核心性质父子结点之间有大小关系分为两种大堆任意一个父结点的值 ≥ 左右孩子结点的值堆顶数组第一个元素是整个堆里最大值小堆任意一个父结点的值 ≤ 左右孩子结点的值堆顶是整个堆里最小值堆的实现向上调整算法ADjustUp1.先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后2.插⼊之后如果堆的性质遭到破坏将新插⼊结点顺着其双双亲往上调整到合适位置即可向下调整算法ADjustDown1.将堆顶元素与堆中最后⼀个元素进⾏交换2.删除堆中最后⼀个元素3.将堆顶元素向下调整到满⾜堆特性为止TOP-K问题1.⽤数据集合中前K个元素来建堆求前k个最⼤的元素则建⼩堆求前k个最⼩的元素则建⼤堆2.⽤剩余的N-K个元素依次与堆顶元素来⽐较不满⾜则替换堆顶元素将剩余N-K个元素依次与堆顶元素⽐完之后堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素链式二叉树概念链式二叉树就是用指针链接的方式存储二叉树不再像堆那样用数组顺序存储。每一个结点独立开辟内存结点内部包含三部分1.数据域存放结点的数据2. 左指针指向左孩子结点3. 右指针指向右孩子结点链式二叉树的实现函数递归栈帧图层序遍历