二叉树计算叶子数量

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 greenham 所说，我们可以使用递归

int countleaves(struct node* root){

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

}