树的基本术语
节点的度与树的度
● 树中某个节点的子树的个数称为该节点的度
● 树中各节点的度的最大值称为树的度
● 通常将度为 m 的树称为 m 次树
所以树中的所有节点中, 最大的度 , 称为树的度 , 称为 m 次树
分支节点与叶节点
● 度不为零的节点称为非终端节点 ,又叫分支节点
● 度为零的节点称为终端节点或叶节点
● 在分支节点中,每个节点的分支数就是该节点的度
● 如对于度为1的节点 , 其分支数为1,被称为单分支节点;
对于度为2的节点,其分支数为2 , 被称为说分支节点; 其余类推.
路径与路径长度
● 对于任意两个节点 di 和 dj , 若树中存在一个节点序列 di, di1,di2 , ..., din, d j. 使得序列中除 di外的任一节点都是其在序列中的前一节点的后继 ,则称该节点序列为由 di 到d j 的一条路径
● 路径的表示 : 路径所通过的节点序列(di,di1,di2,...,dj)
● 路径长度等于路径所通过的节点数目减1 (即路径上分支数目,路径上的线条数目)
孩子, 父母,兄弟,祖先...
● 每个节点的后继 , 被称作该节点的孩子节点(或子女节点).相应地 ,该节点被称作孩子节点的双亲结点(或父母节点)
● 具有同一双亲的孩子节点互为兄弟节点
● 每个节点的所有子树中的节点称为子孙节点
● 从树根节点到达节点的路径上经过的所有节点被称作该节点的祖先节点.
节点的层次和树的高度
● 树中的每个节点都处在一定的层次上
● 节点的层次从树根开始定义,根节点为第一层,它的孩子节点为第二层,以此类推
• 一个节点所在的层次为其双亲节点所在的层次加一
● 树中节点的最大层次称为树的高度(或树的深度).
森林
● n (n>0) 个互不相交的树的集合称为森林.
● 只要把树的根节点删去就成了森林.
● 只要给 n 棵独立的树加上一个节点,并把这n棵树作为该节点的子树 , 则森林就变成了树.