树与二叉树
4.1. 树
定义
树是 \(n\) 个节点的有限集合，\(n=0\) 时称为空树。任意一棵非空树应该满足：
- 有且仅有一个特定的称为 根 的节点。
- 当 \(n>1\) 时，其余节点可分为 \(m(m>0)\) 个互不相交的有限集合 \(T_1,T_2,...,T_m\) ，其中每个集合本身又是一棵树，并且称为根节点的 子树。
基本术语
于 \(k\) 而言，从 \(A\) 到 \(k\) 唯一路径（\(A-B-E-K\)）上的任意节点，都是 \(k\) 的 祖先节点，\(k\) 是他们的 子孙节点。路径上最接近 \(k\) 的 \(E\) 是 \(k\) 的 双亲节点，\(k\) 是 \(E\) 的 孩子节点。根 \(A\) 是树中唯一没有双亲的节点。有相同 双亲节点 的节点称为 兄弟节点，例如 \(k\) 和 \(E\)。
节点的度 是指一个节点的子节点的个数。树的度 是树中节点的最大度数。
度大于0的节点称为 分支节点（非终端节点），度为0的节点称为 叶子节点（终端节点）。
节点的层次 从树根开始定义，根节点为第1层，以此类推，上图中的树层次为4。
节点的深度 是从根节点开始 自顶向下 逐层累加的。
节点的高度 是从叶子节点开始 自底向上 逐层累加的。
树的高度 是树中节点的最大层次数。
有序树 是指树中节点的子树从左到右有次序，不可交换。反之则称为 无序树。
路径 是指两个节点间所经过的节点序列，路径长度 是该路径所经过的边的个数。
森林 是指多棵不相交的树的集合
性质
- 树中节点数等于所以节点的度数加1。（所有子节点数+1个根节点数）
- 度为 \(m\) 的树中第 \(i\) 层上至多有 \(m^{i-1}\) 个节点（\(i\ge 1\)）。
- 高度为 \(h\) 的 \(m\) 叉树至多有 \(\frac{m^h-1}{m-1}\) 个节点。
4.2. 二叉树
定义
一种特殊的树，每个节点至多只有两棵子树（二叉树的度最大为2），且是一棵有序树，子节点不可颠倒次序。
特殊二叉树
- 满二叉树
高度为 \(h\) 的二叉树，若为满二叉树则有 \(2^h-1\) 个节点，即树中每层都含有最多的节点。
- 完全二叉树
简而言之，就是其它层皆满，最后一层从左到右铺设节点但没有铺满的二叉树。
- 二叉排序树
左子树上所有节点的关键字均小于根节点的关键字；右子树上的所有节点的关键字均大于根节点的关键字。
- 平衡二叉树
二叉树上的任一节点的左子树和右子树深度之差不超过1。
性质
- 非空二叉树上的叶子节点数等于度为2的节点数加1（\(n_0=n_2+1\)）。
- 非空二叉树上第 \(k\) 层最多有 \(2^{k-1}\) 个节点。\((k\ge1)\)
- 高度为 \(h\) 的二叉树至多有 \(2^h-1\) 个节点。\((k\ge1)\)
存储
- 顺序存储：适合满二叉树和完全二叉树。
- 链式存储：适合不规则二叉树。