Question

写一个算法，计算给定二叉树的叶结点数。

Answer 1

【答案】：(1)数据结构
采用二叉树的链接表示。
(2)算法
int num_of_leaves(BinTree t){ /*计算二叉树的叶结点个数*/
if(t==NULL)return 0; /*空树,返回0*/
if(t-＞llink==NULL&&t-＞rlink==NULL)return 1;
/*根结点是树叶,返回1*/
return num_of_leaves(t-＞llink)+num_of leaves(t-＞rlink);
/*返回"左子树的叶结点数+右子树的叶结点数"*/
}
(3)代价分析
该算法访问每个结点各一次，时间代价为O(n)，空间代价为O(h)。