树

树的定义

• 树是一种非线性数据结构，它是若干结点的集合。
• 是由唯一的根和若干不相交的子树组成的。
• 子树又是一颗树，因此树的定义是递归的。
• 树的结点数目可为0，此时称之为空树。

树的基本术语

• 结点（结点包含数据元素和指向子树的分支）
• 路径：一个结点和另一个经过的边和结点的序列
• 根（根结点）：一棵树的顶点
• 结点的度：结点拥有子树和分支的个数。
• 树的度：树中结点度的最大值。
• 叶子结点（终端结点）：度为0的结点。
• 分支结点（非终端结点）：度不为0的结点。
• 孩子：结点的子树的根。
• 双亲（父结点）：指向该结点的结点。
• 兄弟：拥有相同父结点的孩子互称兄弟。
• 祖先：从根到某结点路径上的所有结点，都称为该结点的祖先。
• 子孙：以某结点为根的子树的所有结点都为该结点的子孙。
• 层次：从根开始，为第一层，根的孩子为第二层，根的孩子的孩子为第三层，以此类推。
• 树的高度（树的深度）：树中结点的最大层次。
• 堂兄弟：双亲不同但双亲在同一层的结点之间互称堂兄弟。
• 有序树：树中结点的子树从左到右是有次序的，不能交换，这样树叫有序树。
• 无序树：树中结点的子树没有顺序
• 丰满树（理想平衡树）：除最底层外，其他层都是满的树。
• 森林：若干棵不相交的树的集合。

对与结点深度和高度的理解

1. 结点的深度是指根结点到该结点路径上结点的个数
2. 从某结点往下走到终端结点可有多条路径，最长的那条路径上结点的个数为该结点在树中的高度。
3. 根结点的高度为树的高度

树的储存结构

• 顺序储存结构

• 链式储存结构

  • 孩子储存结构（本质上是图的邻接表储存结构）
  • 孩子兄弟储存结构