题如下：若一棵完全二叉树共有950个结点,则该二叉树有几个度为一的结点.

Question

题如下：若一棵完全二叉树共有950个结点,则该二叉树有几个度为一的结点.

Answer 1

完全二叉树（结点数n>1)中结点若存在右孩子,则必存在左孩子,也就是结点要么有左右两个孩子,要么只有左孩子,不存在只有右孩子没有左孩子的结点,所以度为1的结点只能是只有左孩子的结点.完全二叉树中度为1的结点数只可能为0或1个.完全二叉数的最低层若有偶数个结点,则度为1的结点数为0个,若有奇数个结点则度为1的结点数为1个.
设完全二叉树的结点数n=950,深度为k,则k等于n以2为底取对数向下取整后加1,即k=10,也就是950个结点的完全二叉数有10层(根结点为第1层).1至9层为满二叉数,共有2的9次方减1,即511个结点.第10层的结点数为950减511,即439个结点.439为奇数,即度为1的结点数只有1个.
所以950个结点的完全二叉数有1个度为1的结点.
其实对于n(n>1)个结点的完全二叉树度为1的结点数根本就不用算,若n为偶数则有1个,若n为奇数则为0个.