如何统计叶子结点的数目

该算法的递归形式比较容易实现。

具体的代码块如下:

int leaf(BiTree root)

{

static int leaf_count = 0; --->在递归调用时只进行一次初始化。

if (NULL != root) {

leaf(root->lchild);

leaf(root->rchild);

if (root->lchild == NULL

&& root->rchild == NULL)

leaf_count++;

}

return leaf_count;

}

1，该算法的代码模块的独立性算是设计的比较好的。

1.1，耦合比较底，传入树的树根，返回树的叶子节点的个数。

1.2，内聚比较高，模块中的代码比较紧密。容易阅读，易维护。

2，该算法是用递归实现的，效率肯定不是很高。

3，该算法是在对树的后序遍历的基础上实现的。如果该节点的左子树，再右子树，

最后是根节点。

一棵树度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1，则这棵树的叶子节点个数为多少?

解:因为任一棵树中，结点总数=度数+1，所以:

n0+4+2+1+1 = (n0*0 + 1*4 + 2*2 + 3*1 + 4*1)+1

则:n0=8

其中:n0表示叶子结点。

B-tree中，每个结点包含:

1、本结点所含关键字的个数;

2、指向父结点的指针;

3、关键字;

4、指向子结点的指针;

对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为叶子节点，相应的，根结点中关键字的个数为1~m-1;非根结点至少有[m/2]([]，向上取整)个子结点，相应的，关键字个数为[m/2]-1~m-1。