二叉樹計數葉數

Question

假設你已經有基本的二叉樹程序isempty（bt），root（bt），left（bt）和right（bt）。編寫一個過程isLeaf（bt），如果二叉樹bt是葉節點，則返回true;如果不是，則返回false。

這是我有：

proc isLeaf(bt) 
if (isEmpty(bt)) 
error('The binary tree is empty.'); 
elseif (left(bt) < right(bt)) 
return true; 
else return false; 

然後寫了一個程序numLeaves（BT）返回二叉樹BT葉子的數量。

這是我有：

proc numLeaves(bt) 
if (isEmpty(bt)) 
error ('The binary tree is empty.'); 
elseif (count left(bt) + right(bt)); 
return (left(bt) + right(bt); 

請你能正確嗎？

Answer 1

您將瞭解很少什麼，如果你不嘗試解決這個自己，但只是供人們來這裏尋找一個答案：

boolean isLeaf (BinaryTree bt) { 
    return !isempty(bt) && isempty(left(bt)) && isempty(right(bt)); 
} 

int numLeaves (BinaryTree bt) { 
    if (isempty(bt)) 
     return 0; 
    else if (isLeaf(bt)) 
     return 1; 
    else 
     return numLeaves(left(bt)) + numLeaves(right(bt)); 
} 

Answer 2

這裏的主要思想是使用遞歸：

節點擁有的葉子數量是其左子節點具有的葉子數和右子節點具有的葉子數之和。

Answer 3

正如@jeffrey格林漢姆說，我們可以使用遞歸

int countleaves(struct node* root){ 

if(root!=null) 
{ 
countleaves(root->left); 
if(root->left==NULL&&root->right==NULL) 
{ 
count++; 
} 
countleaves(root->right); 
} 

}