问题4、对于任何一棵非空的二叉树,若度为2的结点数有 n2个,叶子数n0必定为n2+1。试证明此结论是正确的。 证明:∵二叉树中全部结点数n=no+n1+n2 (叶子数+1度结点数+2度结点数=全部结点数 又:二叉树中全部结点数n=B+1(总分支数+根结点) (除根结点外,每个结点必有一个直接前趋,即一个分支) 而总分支数B=n1+n2(1度结点必有1个直接后继,2度结点必 有2个) 由此可得:mo+n1+2=n1+2n2+1,即no=2+1
6 问题4、对于任何一棵非空的二叉树，若度为2的结点数有 n2个，叶子数n0必定为n2＋1。试证明此结论是正确的。 证明：∵ 二叉树中全部结点数n＝n0+n1+n2 (叶子数＋1度结点数＋2度结点数=全部结点数) 又∵二叉树中全部结点数n＝B+1 ( 总分支数＋根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支） 而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必 有2个) 由此可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1
问题5、针对二叉树,回答下列问题: (1)具有n个结点的非空二叉树的最小深度是多少?最 大深度是多少? (2)具有n个结点的完全二叉树中有多少个叶子结点? 有多少个度为2的结点? (3)具有n个叶子结点的完全二叉树中共有多少个结 点? 答:(1)其最小深度是1og2(n+1)+1,最大深度是n (2)具有n个结点的完全二叉树中有n/2叶子结点, 有n/211个度为2的结点 (3)具有n个叶子结点的完全二叉树中共有2n0 个结点或2n0-1个结点
7 问题5、针对二叉树，回答下列问题： (1)具有n个结点的非空二叉树的最小深度是多少？最 大深度是多少？ （2）具有n个结点的完全二叉树中有多少个叶子结点？ 有多少个度为2的结点？ （3）具有n0个叶子结点的完全二叉树中共有多少个结 点？ 答:(1)其最小深度是log2(n+1)-1，最大深度是n。 (2)具有n个结点的完全二叉树中有n/2叶子结点， 有n/2-1个度为2的结点。 （3）具有n0个叶子结点的完全二叉树中共有2n0 个结点或2n0-1个结点