计算机中树的度和算法树的度是啥意思怎么算( 二 )

由孩子结点和双亲结点的定义可知：在一棵树中，根结点没有双亲结点，叶子结点没有孩子结点，其余结点既有双亲结点也有孩子结点。如在图6-1的树中，根结点A没有双亲，叶子结点D、H、I、F、G没有孩子，或者说孩子均为空。
（4）结点的层数和树的深度
树既是一种递归结构，也是一种层次结构，树中的每个结点都处在一定的层次上。结点的层数（Level）从树根开始定义，根结点为第1层，它的孩子结点为第2层，以此类推。树中结点的最大层数被称为树的深度（Depth）或高度（Height）。如在图6-1的树中， A结点处于第1层， B、C结点处于第2层， D、E、F、G结点处于第3层， H、I结点处于第4层。 H、I结点所处的第4层为图6-1树中结点的最大层数，所以此树的深度为4 。
（5）有序树和无序树
若树中各结点的子树是按照一定的次序从左向右安排的，则称之为有序树，否则称之为无序树。如对于图6-3中的两棵树，若看作无序树，则是相同的；若看作有序树，则不同，因为根结点A的两棵子树的次序不同。又如，对于一棵反映父子关系的家族树，兄弟结点之间是按照排行大小有序的，所以它是一棵有序树。再如，对于一个机关或单位的机构设置树，若各层机构是按照一定的次序排列的，则为一棵有序树，否则为一棵无序树。因为任何无序树都可以当作任一次序的有序树来处理，所以以后若不特别指明，均认为树是有序的。

文章插图

两棵不同的有序树
（6）森林
森林是m(m≥0)棵互不相交的树的集合。例如，对于树中每个分支结点来说，其子树的集合就是森林。如在图6-1的树中，由A结点的子树所构成的森林为{T1,T2} ，由B结点的子树所构成的森林为{T11,T12,T13} ，等等。
树的性质

树中的结点数等于所有结点的度数加1

根据树的定义，在一棵树中，除树根结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向它的一个分支一一对应，所以除树根结点之外的结点数等于所有结点的分支数（即度数），从而可得树中的结点数等于所有结点的度数加1 。

度为k的树中第i层上至多有ki-1个结点（i≥1）

对于第一层显然是成立的，因为树中的第一层上只有一个结点，即整个树的根结点，而由i=1代入ki-1计算，也同样得到只有一个结点，即ki-1= k1-1=k0=1；假设对于第i-1层（i>1）命题成立，即度为k的树中第i-1层上至多有k(i-1)-1=ki-2个结点，则根据树的度的定义，度为k的树中每个结点至多有k个孩子，所以第i层上的结点数至多为第i-1层上结点数的k倍，即至多为ki-2*k= ki-1个，这与命题相同，故命题成立。