Question

C语言，二叉树的问题

1.如果一个二叉树有70个叶子结点，与80个度为1的结点。求此二叉树的总结点！

2.如果一个完全二叉树有500个结点，则有多少个叶子 结点！

求计算方法。。

Answer 1

性质：对任何一棵二叉树，度为0的结点(即叶子结点)总是比度为2的结点多一个
所以问题1中，总结点：N = 70 + 80 + 69 = 219

问题2：
深度为9的满二叉树，结点合是：511
深度为8的满二叉树，结点合是：255
由上知要求的这棵树，深度为9，但最后一层不满，
则最后一层的叶子结点数为：500-255＝245
则倒数第二层的叶子结点数为：128-123＝5
则此树总共叶子结点数为：245+5=250个

Answer 2

1.219
二叉树的几点只有 0 1 2 三种度数
2度节点 数等于0度节点（即叶子节点）减1
n=n0+n1+n2=70+80+69=219
2.250
满二叉树下 节点数（n）与深度（m）的关系是
n=1+2+4+……+2^(m-1)=(2^m)-1
因为完全二叉树 的节点数n 2^(m-1)-1<n<=2^m-1
所以 m=9 深度为9 满二叉树的叶子是 256 节点一共是511
完全二叉树节点少了11 256-11 =245 因为两个叶子 有一个父亲 11/2 =5 本来的父亲没了孩子 成为叶子 245+5=250