数据结构核心：树与堆的概念及存储实现
树的基本概念
树是一种非线性的数据结构，由 n（n>=0）个有限结点组成一个具有层次关系的集合。除了根结点外，其余结点被分成 M（M>0）个互不相交的集合 T1、T2……Tm，其中每一个集合 Ti 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，但可以有 0 个或多个后继。
因此，树是递归定义的。需要注意的是，在树形结构中，子树之间不能有交集，否则就不再符合树形结构的定义。
相关术语
- 结点的度：一个结点含有的子树的个数。
- 叶结点（终端结点）：度为 0 的结点。
- 分支结点（非终端结点）：度不为 0 的结点。
- 双亲/父结点：若一个结点含有子结点，则称为其子结点的父结点。
- 孩子/子结点：一个结点含有的子树的根结点。
- 兄弟结点：具有相同父结点的结点。
- 树的度：一棵树中最大的结点的度。
- 结点的层次：从根开始定义，根为第 1 层，根的子结点为第 2 层，以此类推。
- 树的高度或深度：树中结点的最大层次。
- 森林：由 m（m>0）棵互不相交的树的集合。
二叉树的定义与分类
基本概念
二叉树是每个节点最多有两个子节点的特性结构。常见的术语包括根节点、叶子节点、子树、深度和高度等。
常见类型
满二叉树与完全二叉树
满二叉树是指所有父节点都有两个子节点，高度为 h，最下面一层为叶子节点，总节点数量为 2^h - 1。
完全二叉树则不一定全满，节点数量范围在 [2^(h-1), 2^h - 1] 之间。
存储方式
顺序存储（数组表示）
顺序结构使用数组来存储，通常只适合表示完全二叉树。如果用于普通二叉树，会造成较大的空间浪费。在实际应用中，只有堆才会优先使用数组来存储，因为堆天然满足完全二叉树的性质。
链式存储（节点结构体/类）
二叉树的链式存储是用链表来表示一棵二叉树，通过指针指示元素的逻辑关系。通常每个结点包含三个域：数据域和左右指针域，左右指针分别指向该结点左孩子和右孩子的地址。
链式结构又分为二叉链和三叉链，红黑树等高级结构会用到三叉链。
