数据结构与算法-树
一、基本概念
树(tree)是n(n>=0)个结点的有限集合它：
- 或者是一棵空树（n=0），空树中不包含任何结点。
- 或者是一颗非空树，此时有且仅有一个特定的称为根(root)的节点。
- 当 n>1 时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、...、Tm，其中每一个本身又是一棵树，并且称为根的子树(sub tree)。
- 如图：a是一颗空树，b是只有一个根结点的树，c是一颗有10个结点的树，其中A是根结点，其余的结点分成3个不相交的结合：T1={B,E,F}、T2={C,G}、T3={D,H,I,J}，每个结合都是一棵树，且都是根的子树。
- 生活案例：树、单位组织架构、族谱、文件系统
结点的度和树的度
- 结点拥有的子树的数目称为结点的度(Degree)。
- 度为0的结点称为叶子(leaf)或终端结点。
- 度不为0的结点称为非终端结点或分支结点，除根结点之外的分支结点也称为内部结点。
- 树内各结点的度的最大值称为树的度。
结点的层次和树的深度
- 结点的层次(level)从根开始定义，层次数为1的结点是根结点，其子树的根的层次为2。
- 树种结点的最大层次数称为树的深度(Depth)或高度