关于叶子节点有n个，求平衡二叉树的深度最多是多少

叶子节点有n个，求平衡二叉树的深度最多是多少~

解析上说是1.5log（n+1），实际上用斐波纳皆数列推出来的：1，2，4，7，12.即是FN = F(N-1) +F(N-2) +1.因此你的话是对的。

假设Nh表示深度为h的平衡二叉树中含有的最少的结点数目。那么，N0=0，N1=1，N2=2，并且Nh=Nh-1+Nh-2+1。
根据公式先计算出N3
N3=2+1+1
计算出N4
N4=4+2+1
最后出结果
N5=7+4+1
这时候N5就等于12
N后面跟的数字就是深度

扩展资料：
高为h的BT, 其结点的数目在2^(h+1)-1和1/2(3^(h+1)1)之间, 叶的数目在2^h和3^h之间。
证明：BT退化为每个结点 (非叶) 只有两棵子树时, 结点的数目最少, 叶子也最少。设层号为i则各层结点数为2^(i-1)个, 那么高为h的BT最大层号是j时, 有h=j-1。
整个树的结点数为s=2^0+2^1+2^2+…+2^h, 故s=2^(h+1)-1。其叶子的个数是2^h。同理, 当BT每个非叶结点都有三棵子数时, 结点数目最多。此时结点数为：
s=3^0+3^1+3^2+⋯+3^h‚s=1/2(3^(h+1)−1)，其叶子的个数是3^h。

设根结点层次为1，则高度为h的平衡二叉树最少叶子结点个数就是Fibonacci数的F(h): 1,1,2,3,5,8,13,21,34,55,...
看n在哪个Fibonacci数之间就可以了，当然，利用Fibonacci数的通项公式也可以求出，只是比较麻烦点

---

恩平市15063138527： 关于叶子节点有n个,求平衡二叉树的深度最多是多少 - ？
鲜省痔疾： 设根结点层次为1,则高度为h的平衡二叉树最少叶子结点个数就是Fibonacci数的F(h): 1,1,2,3,5,8,13,21,34,55,...看n在哪个Fibonacci数之间就可以了,当然,利用Fibonacci数的通项公式也可以求出,只是比较麻烦点

恩平市15063138527： 数据结构题目:在有n个叶子结点的完全二叉树中,最多有多少个结点? - ？
鲜省痔疾：[答案] 假设0、1、2度的结点分别为n0、n1、n2个,二叉树的结点总数为T: 按照结点算:T = n0 + n1 + n2 (1) 按照边算:T = n1 + 2 * n2 + 1 (2) 所以(1) - (2)n0 = n2 + 1 在知道n0等于n的情况下,n2等于n - 1,所以 T = n0 + n1 + n2 = 2 * n + n1 - 1 由...

恩平市15063138527： 假设二叉树中所有非叶子结点都有左右子树,若有n个叶子结点,求该二叉树共有多 - ？
鲜省痔疾： 显然该二叉树为正则二叉树,没有度为1的结点,只有度为0的叶子和度为2的分支 按二叉树性质n0 = n2 + 1,因此度为2结点数为n - 1 于是该二叉树有2n-1个结点

恩平市15063138527： 有n个结点的二叉树,已知叶子结点个数为n0,回答下列问题:(1)写出求度为1的结点的个数n1的计算公式;(2)若此树是深度为k的完全二叉树,写出n... - ？
鲜省痔疾：[答案] (1)n1=n-2n0+1 (2)n=n0+2^(k-1) -1 (3)n=2n0-1 二叉树的第i层至多有2的 i -1次方个结点;深度为k的二叉树至多有2^(k) -1个结点;对任何一棵二叉树T,如果其终端结点数(即叶子结点数)为n0,度为2的结点数为n2,则n0 = n2 + 1.

恩平市15063138527： 求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标.要求写出简要步骤. - ？
鲜省痔疾：[答案] 根据完全二叉树的性质,最后一个结点(编号为n)的双亲结点的编号是en /2?,这是最后一个分支结点,在它之后是第一个终端(叶子)结点,故序号最小的 叶子结点的下标是en/2u+1

恩平市15063138527： 试求有n个叶结点的非满的完全二叉树的高度 - ？
鲜省痔疾： 因为 二叉树中,有这样一个性质,如果其终端结点数(也就是叶子节点)的个数为n0,度为2的结点数为n2,则n0=n2+1; 假设叶子节点有x个,则度为2的个数为 x-1: 所以: 2x-1 = n; 所以 x = (n+1)/2 (满二叉树) 所以 叶子节点个数为 :(n+1)/2 非终端结点为 : (n+1)/2-1

恩平市15063138527： 推导含有n个叶子结点的完全二叉树的深度 - ？
鲜省痔疾： 按照二叉树性质,n2 = n0 -1 = n -1 而度为1个结点个数为0 或者1,于是二叉树中结点个数可能是2n-1,也可能是2n个 因此如果度为1 结点个数为0,深度为下取整(log2(2n-1)) + 1 如果度为1结点个数为1,深度为下取整(log2(2n))+ 1 这两个值大多数时候相等,有时候可能会相差1

恩平市15063138527： n个结点的完全二叉树顺序存储,叶结点和非叶结点的个数、范围? - ？
鲜省痔疾： n个节点的完全二叉树,则根据公式2^N-1=n 算出N, 即层数.叶节点数:2^(N-1),非叶子节点数:2^(N-1)-1 范围就不用说了吧,非叶子:1----2^(N-1)-1 叶子:2^(N-1)---2^N-1 存储,可以用链表,也可以用数组.链表,每个节点一个左子节点,一个右子节点.数组,就按照顺序存储,并且建立两个指针,指针的关系是父节点与左子节点的关系...程序,书上有吧、、、、、

恩平市15063138527： 计算机二级 二叉树问题求解 - ？
鲜省痔疾： 假设有n个叶子节点,如果某个叶子节点又延伸出来m个叶子节点,则叶子节点数量就是n-1+m 所以看题中,假设一开始只有一个根节点(同时也是叶子节点),它的度为4,这时叶子节点数为1-1+4=4,这时有一个叶子节点度变成3,总的叶子节点数量就是4-1+3=6 类推下去,叶子节点总数为1+(4-1)+(3-1)+(2-1)*2+(1-1)*4=8 如果整理成另一个公式就是1+1*n1+2*n2...+m*nm-(n1+n2+n3...+nm),其中ni就是度为i的节点数量,用到题中就是1+1*4+2*2+3*1+4*1-(4+2+1+1)=8

恩平市15063138527： 平衡二叉树的具体算法 - ？
鲜省痔疾： 平衡二叉搜索树双称为AVL树,它也是一棵二叉搜索树,是对二叉搜索树的一种改进,或都是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.平衡因子(Balance Factor,BF)定...