数据结构：堆与链式二叉树详解

1. 堆的概念和定义

1.1 堆

定义：是特殊的二叉树，分为大堆和小堆。

• 大堆（大根堆）：根节点最大的堆。堆中某个结点的值总是不小于其父结点的值。
• 小堆（小根堆）：根节点最小的堆。堆中某个结点的值总是不大于其父结点的值。
• 堆总是一棵完全二叉树。

1.2 二叉树的性质

有 n 个结点的二叉树，从上到下从左到右从 0 开始依次编号，对于编号为 i 的结点有以下性质：

• i 结点的父结点：(i-1)/2
• i 结点的左孩子结点：2i+1
• i 结点的右孩子结点：2i+2
• 若 2i+1 或 2i+2 >= n，则没有左右孩子。

2. 堆的实现

typedef int HPDataType;
typedef struct Heap {
    HPDataType* a;
    int size;
    int capacity;
} HP;

// 默认初始化堆
void HPInit(HP* php);
// 利用给定数组初始化堆
void HPInitArray(HP* php, HPDataType* a, int n);
// 堆的销毁
void HPDestroy(HP* php);
// 堆的插入
void HPPush(HP* php, HPDataType x);
// 获取堆顶数据
HPDataType HPTop(HP* php);
// 删除堆顶的数据
void HPPop(HP* php);
// 判空
bool HPEmpty(HP* php);
// 求 size
int HPSize(HP* php);
// 向上调整算法
void AdjustUp(HPDataType* a, int child);
// 向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);

3. 实现链式二叉树

3.1 链式二叉树的概念

用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

typedef int BTDataType;
// 二叉链
typedef struct BinaryTreeNode {
    struct BinTreeNode* left;   // 指向当前结点左孩子
    struct BinTreeNode* right;  // 指向当前结点右孩子
    BTDataType val;             // 当前结点值域
} BTNode;

3.2 前中后遍历

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历 (Preorder Traversal)：访问顺序为 根结点、左子树、右子树。
2. 中序遍历 (Inorder Traversal)：访问顺序为 左子树、根结点、右子树。
3. 后序遍历 (Postorder Traversal)：访问顺序为 左子树、右子树、根结点。

3.3 遍历（举例）

• 前序遍历（根左右）：A ,B,D,NULL,NULL,NULL,C,E,NULL,NULL,F,NULL,NULL
• 中序遍历（左根右）：NULL,D,NULL,NULL,B,A,NULL,E,NULL,C,NULL,F,NULL
• 后序遍历（左右根）：NULL,NULL,D,NULL,B,NULL,NULL,E,NULL,NULL,F,C,A