一道关于二叉树的题目

来源：百度知道 编辑：UC知道 时间：2024/05/24 00:37:19
高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于结点的最大深度，根结点的深度为0.如果某个均衡二叉树共有1381个结点，则该树的树高为( )
A10 B11 C12 D13

请写出具体怎么解题目
谢谢

在复习NOIP对吧，呵呵．．我记得这不是原题，原题结点总数是2381，选B.

本题
对于根结点深度为0，高度为h的二叉树共有（h+1）层.
结点总数为(11..1)B=(100..0)B-(1)B=(2^(h+2)-1)D
那么高度为(h-2)一层及以上应共有(2^h - 1)个结点，高度为h一层及以上最多有(2^(h+2)-1)个结点．则(2^h-1<1381)and(2^(h+2)-1>1381)得出h=9或10.选A.