首页 > 代码库 > 二叉树节点个数题目[n0,n1,n2]
二叉树节点个数题目[n0,n1,n2]
若完全二叉树的节点个数为2N-1,则叶节点个数为()
A)N-1 B)2×N C)2N-1 D)2N
解析:
结点拥有的子树数为结点的度
证明:因为二叉树中所有结点的度数均不大于2,所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和:
n=no+n1+n2 (式子1)
另一方面,1度结点有一个孩子,2度结点有两个孩子,故二叉树中孩子结点总数是:
nl+2n2
树中只有根结点不是任何结点的孩子,故二叉树中的结点总数又可表示为:
n=n1+2n2+1 (式子2)
由式子1和式子2得到:
no=n2+1
完全二叉树的n1=0
所以,n = n0 + n0 - 1 + 1 = 2n0
二叉树: 节点数=边数+1
即n0+n1+n2 = n1+2*n2+1 ===>n0=n2+1
二叉树节点个数题目[n0,n1,n2]