Question

关于数据结构的问题

23. 具有五层结点的二叉平衡树至少有__b__个结点。
A. 10 B. 12 C. 15 D. 17
问题:怎么得到b,请给出过程
可否把图给出,就是大概的也行

Answer 1

如果你把二叉平衡树的定义看懂了,其实自己就可以把这个图画出来
"平衡二叉树上的任何节点的左子树和右子树的深度的差值只能是－1、0或1"
所以5层结点的平衡二叉树,根结点的左子树和右子树深度分别为4,4或4,3或3,4
因为取最少个数,咱们取4,3
再看二级结点,深度为4的二级结点的左子树和右子树深度分别为3,3或3,2或2,3
取最少个数3,2
再看三级结点,深度为3的三级结点的左子树和右子树深度分别为,2,2或2,1或1,2
取最少个数2,1
同理可求出其他子树的结点最少个数即可

*
丨
*
丨
*-*
丨
* ---这个是根结点
丨
*-*-*
丨
*-*
丨
*
丨
*