Question

C语言求树中的叶子结点数

为什么共包含结点30个？从头到尾都没看懂，求大神

Answer 1

有从上至下和从下至上两种方式可以统计树的节点数。
设叶子节点（度为0的节点）数为x：
从上至下时，度为n的节点有n个子节点，再加上根节点，总结点数量为1+4×1+3×2+2×3+1×4+0×n=21
从下至上时，节点数为度为0~4的所有节点数相加，总节点数量为1+2+3+4+n=10+n
所以有21=10+n，得n=11.

追问

总结点数量为1+4×1+3×2+2×3+1×4+0×n=21 什么意思。我还是没看懂。怎么乘的。怎么可以这样乘。。。。 新手

追答

度为n的结点有n个子节点，m个度为n的节点就有n×m个子节点，统计度为0~n的节点的子节点数并相加，再加上根节点，就是树的总节点数。

Answer 2

void leafBTree(BTree *T,int &m)
{
if(T!=NULL)
{
if((T->lchild==NULL)&&(T->rchild==NULL))
m++;
leafBTree(T->lchild,m);
leafBTree(T->rchild,m);
}
}