樹節點的演算法

Ⅰ 寫一個演算法，計算給定二叉樹的葉結點數。

【答案】：(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)。