首页 > 代码库 > 二叉树节点个数题目[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]