Question

C语言的题目求助

设一颗完全二叉树共有699个结点，则在该二叉树中的叶子结点数为?(详细说明，谢谢！！)

Answer 1

设n为总节点数，n0是度为0的结点总数，n1是度为1的结点总数，n2是度为2的结点总数，二叉树中只有这三种度的节点。所以n=n0+n1+n2。
又由二叉树的性质可知：n0=n2+1，即：n2=n0-1，带入上式有：n=2*n0+n1-1
而根据完全二叉树的定义，可以知道n1只可能是0或1；当总节点数为偶数时，n1=1，当总结点数为奇数时，n1=0。
因为总结点数为699为奇数，所以n1=0。带入到n=2*n0+n1-1有n0=(n+1)/2=350。
度为0的节点即叶子节点，所以叶子节点数为350。
够详细了吧。。。

Answer 2

分析如下：
叶子节点n0,度为1的节点n1,度为2的节点n2
根据题意可知
n0 + n1 + n2 = 699;
根据二叉树的特点有
n0 = n2 + 1;
根据完全二叉树的特点有
n1 = 1或者0
推出
n1 + 2n2 = 698
当n1 = 0时
有n0= 350
n1 = 0
n2 = 349
当n1 = 1时
有n0= 349
n1 = 1
n2 = 348
但是当总结点为奇数时，只能是第一种情况，这是由完全二叉树的性质决定的

Answer 3

还可以这样理解，因为此二叉树是完全二叉树，故一定满足下面的性质。
如果一个节点的编号是i,且有2*i<=n，其中n为此二叉树总的节点数，则有
编号为2*i的节点是编号为i的节点的左孩子节点，相应地如果有2*i+1<=n，
则说明存在编号为i的节点的右孩子节点。
运用此性质，由于699是奇数，则有699/2=349，即编号为349的节点为最后一个非叶节点，它有右孩子节点。以后的节点全部都是叶子节点，叶子节点数为：699-349=350。（350----------------699）
归根结底考察的都是二叉树最基本的性质。
明白吗？有事发我邮箱：let610@163.com.

Answer 4

树的节点数和层数是有关的，2^k-1 吧，记得是。699应该是10层了，第十层的没有满。完全二叉树，所以前九层满，有512个节点，剩下187个是第十层左侧的，他们的母节点（是这个名字不……）应该是94个（最后一个节点只有一个子节点），第九层的节点数是256个（2^（k-1）），所以还有162个节点没有子节点，即叶子节点。叶子节点数是，162+187。不知道对不对