设一颗二叉树中,度为2的结点数为9,则该二叉树的叶子节点的数目是?

hqmhqmhqm119 · 2018-4-30 01:57:05

n0=n2+1
证明：设二叉树T中度为1得结点数为n1，结点总数为n。由于T中所有结点度数均不大于2，因此，T中结点总数n=n0+n1+n2 (1)
再考虑树T的分支数。除了根结点外，其余每个结点都有一条向上的分支与双亲结点相连，因此总共有n-1(即总节点-根节点)条向上的分支。从另一个角度看，每个结点有其“度数”条向下的分支与孩子结点相连，因此总共有n1+2n2条向下的分支。因此有：n-1=n1+2n2 (2)
由(1)和(2)->n0=n2+1
因此答案为10

设一颗二叉树中,度为2的结点数为9,则该二叉树的叶子节点的数目是?

1 个回复