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

文章插图

当一棵k叉树上的结点数等于

文章插图

时，则称该树为满k叉树。例如，对于一棵深度为4的满二叉树，其结点数为24-1 ，即15；对于一棵深度为4的满三叉树，其结点数为

文章插图

，即40 。

具有n个结点的k叉树的最小深度为[logk(n(k-1)+1)]

设具有n个结点的k叉树的深度为h ，若在该树中前h-1层都是满的，即每一层的结点数都等于ki-1个（1≤i≤h-1），第h层（即最后一层）的结点数可能满，也可能不满，则该树具有最小的深度。根据性质3 ，此树的结点数n必然小于等于高度为h的满k叉树的结点数，同时必然大于高度为h-1的满k叉树的结点数，则深度h与n之间的关系为：

文章插图

可变换为 kh-1<n(k-1)+1≤kh
以k为底取对数后得 h-1<logk(n(k-1)+1)≤h
即 logk(n(k-1)+1)≤h<logk(n(k-1)+1)+1
因h只能是整数，所以 h=?logk(n(k-1)+1)?
因此得到具有n个结点的一般k叉树的最小深度为?logk(n(k-1)+1)? 。
注：?x?表示对x进行向上取整，其值为大于等于x值的最小整数。如x的值为4和4.3时，向上取整结果分别为4和5 。与此相反， ?x?表示对x进行向下取整，其值为小于等于x值的最大整数。如x的值为4.6和5时，向下取整结果分别为4和5 。
例如，对于二叉树，求最小深度的计算公式为?log2(n+1)? ，若n=20 ，则最小深度为5；对于三叉树，求最小深度的计算公式为?log3(2n+1)? ，若n=20 ，则最小深度为4 。