数据结构与算法-树
一、基本概念
树(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)或高度