algorithm - 二叉树计算叶子的数量

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

正如@jeffrey greenham 所说，我们可以使用递归

int countleaves(struct node* root){

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

}

Answer 3

这里的主要思想是使用递归：

一个节点的叶子数是它的左子节点的叶子数和它的右子节点的叶子数之和。