树
树的定义
- 树是一种非线性数据结构，它是若干结点的集合。
- 是由唯一的根和若干不相交的子树组成的。
- 子树又是一颗树，因此树的定义是递归的。
- 树的结点数目可为0，此时称之为空树。
树的基本术语
- 结点（结点包含数据元素和指向子树的分支）
- 路径：一个结点和另一个经过的边和结点的序列
- 根（根结点）：一棵树的顶点
- 结点的度：结点拥有子树和分支的个数。
- 树的度：树中结点度的最大值。
- 叶子结点（终端结点）：度为0的结点。
- 分支结点（非终端结点）：度不为0的结点。
- 孩子：结点的子树的根。
- 双亲（父结点）：指向该结点的结点。
- 兄弟：拥有相同父结点的孩子互称兄弟。
- 祖先：从根到某结点路径上的所有结点，都称为该结点的祖先。
- 子孙：以某结点为根的子树的所有结点都为该结点的子孙。
- 层次：从根开始，为第一层，根的孩子为第二层，根的孩子的孩子为第三层，以此类推。
- 树的高度（树的深度）：树中结点的最大层次。
- 堂兄弟：双亲不同但双亲在同一层的结点之间互称堂兄弟。
- 有序树：树中结点的子树从左到右是有次序的，不能交换，这样树叫有序树。
- 无序树：树中结点的子树没有顺序
- 丰满树（理想平衡树）：除最底层外，其他层都是满的树。
- 森林：若干棵不相交的树的集合。
对与结点深度和高度的理解
- 结点的深度是指根结点到该结点路径上结点的个数
- 从某结点往下走到终端结点可有多条路径，最长的那条路径上结点的个数为该结点在树中的高度。
- 根结点的高度为树的高度
树的储存结构
- 顺序储存结构
链式储存结构
- 孩子储存结构（本质上是图的邻接表储存结构）
- 孩子兄弟储存结构
