返回主页
已有1条笔记
[数据结构 P2070] 若平衡二叉树的高度为 6 ，且所有非叶结点的平衡因子均为 1 ，则该平衡二叉树的结点总数为（ ）。
未通过
若平衡二叉树的高度为 6 ，且所有非叶结点的平衡因子均为 1 ，则该平衡二叉树的结点总数为（ ）。
A. 10
B. 20
C. 32
D. 33
上面问题的答案是：
加入错题本
个人笔记
方法一：递推
本题默认叶结点...
用户登录可进行刷题及查看答案
方法一：递推
本题默认叶结点高度为 1 ，采用归纳法思路，从高度为 1 的平衡二叉树进行递推，假设左子树比右子树高。
构造高度为3的平衡二叉树时，左子树为高度为2的平衡二叉树，右子树为高度为1的平衡二叉树。
设高度为 n 的平衡二叉树结点数为 Cn ，可得递推式： Cn=Cn−1+Cn−2+1 。
递推计算出 C6=20 。
本题选B。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案
暂无评论，来抢沙发