Question

若一棵二叉树只有叶结点和左右子树皆非空的结点,设叶结点的个数为k,则左右子树皆非空的结点个数是?

Answer 1

假设n0表示度为0的结点(叶子结点),n2表示度为2的结点(左右子树皆非空的结点),由二叉树的性质有：

n0 = n2 + 1

已知n0 = k,

则n2 = n0 -1 = k - 1

即左右子树皆非空的结点个数是(k-1).