精华内容
下载资源
问答
  • 这里说一下自己的答案,如果m叶子的完全二叉树最多有2m个节点。推导如下: 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ /\ 8 9 10 如上图所述,假设m=8,也就是叶子节点是8...
    这里说一下自己的答案,如果有m个叶子的完全二叉树最多有2m个节点。推导如下:
    
    					 1
    				   /   \
    				  2	    3
    				 /	\   / \
    			    4    5 6   7
    			  / \  / \ / \ /\
    			 8  9 10 
    如上图所述,假设m=8,也就是叶子节点是8个完全的二叉树,那么它最大有2*8个节点。
    现在用数学方法推导:
    	(1)因为第一层最多有2^(1-1) = 1个叶子节点,那么第h层最多有2^(h-1)个叶子节点。所以我们首先可以根据m来得出我们的完全二叉树可以最多有多少层:
    		2^(h-2) <= m <= 2^(h-1);
    首先我们找到了处于m=8在的最大的二叉树的层数是5(2^(5-2)<= m <= 2^(5-1))(2)因为找到了最大的层数,因为是完全二叉树,所以倒数第二层以上的树肯定是一个满二叉树了,那么倒数二层以上的节点一共有2^(h-1)-1个节点。
    	(3)那么还剩下倒数最后一层的节点数,我们只需要把它们求出来就可以知道所有的节点了。那么我们假设最后一层有x个节点。但是请注意这个x必定是一个奇数。为什么呢?假设最后一层的节点数是一个偶数的话。就比方说上面图的8,9两个节点,那么我完全可以在节点5下加一个左子树(因为增加一个左子树不会增加叶子节点数),所以就可以在不增加叶子节点的情况下增加一个节点)。在拿一个例子来说:
    					1
    				   / \
    				  2   3
    				 / \  /\
    				4  5 6  7
    假设我现在是m=4,那么根据2^(h-2) <= m <= 2^(h-1)得出h=3,那么倒数第二层以前的树是满二叉树,所以有2^2-1个节点,然后最后一层因为也是个偶数,所以我完全可以在4节点下增加一个左子树,也可以保证是m=4比如下面这个图:
    					1
    				   / \
    				  2   3
    				 / \  /\
    				4  5 6  7
    			   /
    			  8
    所以我们得出最后一层的叶子节点数必定是一个奇数的。所以我们假设最后一层的节点数是x,那么我们可以通过(x+1)/2得出上一层不是叶子节点的个数。那么根据倒数第二层的
    中所占有的节点个数是2^(h-2)。可以得出倒数第二层中剩余的叶子节点数是
    		2^(h-2)-(x+1)/2;
    那么又因为一共有m个叶子节点;所以可以得出:
    		2^(h-2)-(x+1)/2 + x = m;
    		//两边同时乘以2得出
    		2^(h-1)-1+x=2m;
    		推出
    		x = 2m-2^(h-1)+1;
    		然后加上倒数第二层总的节点个数:
    		x+2^(h-1)-1 = 2m-2^(h-1)+1+2^(h-1)-1=2m
    所以推出:
    		如果有m个叶子节点的完全二叉树,那么其最多有2m个节点
    
    展开全文
  • 性质:叶子节点=度数2的节点+1 证明:总节点数n,叶子节点n0,度数为1的节点n1,度数为2的节点n2 那么:n=n0+n1+n2  n=n1+2*n2+1 //通过枝来看 ... 再来一题,124叶子节点完全二叉树最多有多少个节点

    性质:叶子节点=度数2的节点+1

    证明:总节点数n,叶子节点n0,度数为1的节点n1,度数为2的节点n2

    那么:n=n0+n1+n2

                n=n1+2*n2+1 //通过枝来看

    所以:n0=n2+1

    然后根据题意:800=2*n0-1+n1 对于完全二叉数n0等于1或0,这里肯定是1,OK,n0=400

      再来一题,124个叶子节点的完全二叉树,最多有多少个节点?

      n=2*n0-1+n1 最大248

    展开全文
  • 先再读一遍题目,里面最多”两字,也就是说能满足条件的完全二叉树不止一种,要找出结点最多的那个 评论里的人几乎都认为答案唯一且为247,评论里的观点是:非叶节点数目 = 叶节点+1 这观点并不是完全正确的...

    在网上看到这个问题,在讨论答案到底是248,还是247,评论普遍认为是247,但我觉得答案是248

    先再读一遍题目,里面有“最多”两个字,也就是说能满足条件的完全二叉树不止一种,要找出结点最多的那个

    评论里的人几乎都认为答案唯一且为247,评论里的观点是:非叶节点数目 = 叶节点-1

    这个观点并不是完全正确的,它需要加上一个前提,就是完全二叉树的最右非终结结点的子树个数是二

    下面我按照最右非终结结点的子树是二和一两种情况进行分析:

    一、最右非终结结点的子树个数是二
    在这里插入图片描述
    除去第n层的全部结点数: 2 n − 1 − 1 2^{n-1} - 1 2n11

    总结点数: 2 n − 1 − 1 + S 2^{n-1} - 1+S 2n11+S
    由此,可以得到:非叶节点数 = 总结点数 − S − T -S-T ST = 2 n − 1 − T − 1 2^{n-1}-T-1 2n1T1——————1

    第n-1层结点数: S / 2 + T S/2 +T S/2+T 2 n − 2 2^{n-2} 2n2
    由此,得到等式: S / 2 + T = 2 n − 2 S/2 +T=2^{n-2} S/2+T=2n2
    将等式变型得到:叶结点数= S + T = 2 n − 1 − T S+T=2^{n-1}-T S+T=2n1T——————————————2

    将1,2两式联立(将最后得到的数值进行比较),得:非叶节点数目 = 叶节点-1

    二、最右非终结结点的子树个数是一
    在这里插入图片描述
    除去第n层的全部结点数: 2 n − 1 − 1 2^{n-1} - 1 2n11

    总结点数: 2 n − 1 − 1 + S 2^{n-1} - 1+S 2n11+S
    由此,可以得到:非叶节点数 = 总结点数 − S − T -S-T ST = 2 n − 1 − T − 1 2^{n-1}-T-1 2n1T1——————1

    第n-1层结点数: ( S + 1 ) / 2 + T (S+1)/2 +T S+1/2+T 2 n − 2 2^{n-2} 2n2
    由此,得到等式: ( S + 1 ) / 2 + T = 2 n − 2 (S+1)/2 +T=2^{n-2} S+1/2+T=2n2
    将等式变型得到:叶结点数= S + T S+T S+T= 2 n − 1 − T − 1 2^{n-1}-T-1 2n1T1————————————2

    将1,2两式联立(将最后得到的数值进行比较),得:非叶节点数目 = 叶节点

    最终结论:
    当完全二叉树的最右非终结结点子树个数为一时,非叶节点数目 = 叶节点;
    当完全二叉树的最右非终结结点子树个数为二时,非叶节点数目 = 叶节点-1

    所以,再回到题目本身,我们也要分两种情况讨论:
    1.最右非终结结点子树个数为二时,非叶结点数 = 124 − 1 = 123 =124-1=123 =1241=123
    二叉树结点总数 = 124 + 123 = 247 =124+123=247 =124+123=247
    S = 120 , T = 4 S=120,T=4 S=120,T=4 (相加后就是题目要求的叶节点的总数,S和T不清楚的再看一下上面的图)
    第n-1层结点数量为: 64 64 64(即 S / 2 + T S/2+T S/2+T
    64 64 64 2 6 2^{6} 26,符合完全二叉树的特点

    2.最右非终结结点子树个数为一时,非叶结点数 = 124 =124 =124
    二叉树结点总数 = 124 + 124 = 248 =124+124=248 =124+124=248
    S = 121 , T = 3 S=121,T=3 S=121,T=3 (相加后就是题目要求的叶节点的总数)
    第n-1层结点数量为: 64 64 64(即 ( S + 1 ) / 2 + T (S+1)/2+T (S+1)/2+T
    64 64 64 2 6 2^{6} 26,符合完全二叉树的特点

    又因为题目要求最大总结点数,取第二种情况,答案: 248 248 248


    不好意思,之前由于本人的疏忽,本题的结论有一些错误,推导过程没有问题,现已修改过来,对于给大家理解时带来的误导和不便十分抱歉。
    感谢zonezn指出本文结论中的错误!

    展开全文
  • 二叉树 深度为m的二叉树最多节点

    千次阅读 2021-02-12 22:53:18
    深度为m的二叉树最多节点数为2^m-1。 求最多节点数,则设该二叉树为满二叉树。 每层节点数为: 层数 节点数 1 1 2 2 3 4 4 8 … … m 2^(m-1) 利用等比数列求和公式,即可求出。

    深度为m的二叉树最多节点数为2m-1。
    求最多节点数,则设该二叉树为满二叉树。
    每层节点数为:

    层数节点数
    11
    22
    34
    48
    m2m-1

    利用等比数列求和公式,即可求出2m-1。

    展开全文
  •    一棵10层的二叉树最多包含多少个结点?    注意当一棵二叉树只有一结点时为一层。 【答案提交】    这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一整数,在提交答案时只填写这...
  • 完全二叉树的节点计算基本是几类,要么是求完全二叉树中的叶子节点个数或者度为1或者2的节点的个数。 其实这些问题根本上一一类问题,求解方法也是基本相同的。 先把题列出来: 一棵完全二叉树具有1000个结点,...
  • 1.n个节点二叉树最多可以有多少层? A.n/2 B.log(n) C.n-1 D.n 答案解析: D 假设从根节点开始,根节点的层数为1,每一层一个节点,则n层。
  • ...这么无聊的题。...2.这棵树最大层次为7,前六层为满二叉树,第六层里8个节点没有子树,sum=63+48=111. 如果还是没有明白看牛客网解析 主要是要明白完全二叉树定义+一点想象。 完全二叉树是由满二叉...
  • 1、重新排列1234使得每一数字都在原来的位置上,一共几种排法? 正确答案:9种 解析:考察数学基础之排列与组合 1.用枚举法解决,可以排出2143,2341,2413,3142,3412,3421,4123,4312,4321共9种排法 2.另外,也...
  • 一棵包含2019结点的二叉树最多包含多少个叶结点? 【答案提交】 这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一整数,在提交答案时只填写这整数,填写多余的内容将无法得分。 答案  ...
  • 二叉树最多节点

    千次阅读 2020-04-18 20:48:39
    题目 问题描述  一棵10层的二叉树最多包含多少个结点?  注意当一棵二叉树只有一...分析题目,已知二叉树为十层,最多包含多少个节点,那么就是求满二叉树所有结点数。 代码分析 结果为1023 public s...
  • 给定一棵完全二叉树的根节点root,返回这棵树的节点个数。如果完全二叉树的节点数为N,请实现时间复杂度低于O(N)的解法。给定树的根结点root,请返回树的大小。 二分的思想。看完全二叉树的最后的最右一个节点的位置...
  • = 0,所以第一层为i=0),所以第六层的结点数最多为2^5=32,根据题意第六层9叶子结点,推测出还有第七层,所以第六层结点数减去9叶子结点,剩下的23结点都左右子树,故第七层23*2=46结点,总的结点数=2^0+2...
  • 一棵包含2019结点的二叉树最多包含多少个叶结点? 【输入】 没有输入。 【输出】 输出一整数。 【提示】 把答案放在输出语句中输出,例如C/C++语言可以用printf或cout。 **注意:**需要输出的是一整数,...
  • 高度为n的平衡二叉树最少需要多少个节点?高度为n的平衡二叉树最少需要多少个节点?参考 高度为n的平衡二叉树最少需要多少个节点? 设f(n)为高度为n的平衡二叉树最少含有的节点数,则:f(1) = 1;f(2) = 2; f(3) = ...
  • = 0,所以第一层为i=0),所以第六层的结点数最多为2^5=32,根据题意第六层23叶子结点,推测出还有第七层,所以第六层结点数减去23叶子结点,剩下的9结点都左右子树,故第七层9*2=18结点,总的结点数=2^0+2...
  • 题目:一棵10层的二叉树最多包含多少个结点? 一棵10层的二叉树最多包含多少个结点?  注意当一棵二叉树只有一结点时为一层。 答案提交  这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一...
  • 二叉树所有层中最多节点个数 解题思路:根据题意可知,要想获得二叉树中每一层的节点个数,需要对二叉树进行层序遍历,并在层序遍历的过程中记录每一层具有多少个节点。因此可以在层序遍历每一个节点的时候为每...
  • 面试题:完全二叉树699个节点,则叶子节点有多少个? 怕记不住,先上结论: 假设一个二叉树有n个节点: 度为0的节点个数是n0 度为1的节点个数是n1 度为2的节点个数是n2 则如下公式成立: n0 ...
  • 已知完全二叉树有30个节点,则整个二叉树有_1--度为1的节点。 解答: 完全二叉树:除了最外层,其余层上的节点数目都达到最大值,而第h层上的节点集中存放在左侧树中。  n0是度为0的节点总数(即叶子节点数)...
  • 第一层最多有1个节点完全二叉树的叶节点只可能出现在后两层如果完全二叉树有6层,则前5层是满二叉树,总节点数目为16+8+4+2+1+8=39如果完全二叉树有7层,则前6层是满二叉树, 前六层总节点数目为32+16+8+4+2+1=6
  • 完全二叉树节点个

    千次阅读 2019-01-07 12:15:25
    文章目录完全二叉树节点个完全二叉树实现遍历借助完全二叉树的特点完全二叉树的层数原理第一种情况第二种情况实现时间复杂度关于作者 完全二叉树节点个数 最简单的解法就是遍历这棵树,时间复杂度是O(N),如果只是...
  • 今天在牛客网上做了一题,是关于完全二叉树在某一层的节点的个数问题,题目不难,但是由于水平太渣,调试了好久才ac. 题目是这样的。 一棵树,输出某一深度的所有节点则输出这些节点,无则输出EMPTY。该...
  • 1.N个节点的二叉树的最低高度和最高高度? 2.N个节点完全二叉树的最低高度或者最高高度? 3.N个节点的m叉树的最小高度和...7.给定完全二叉树在某层n个叶子节点,则完全二叉树最多和最少节点个数? 8.给定完全二...
  • 平衡二叉树的最少最多节点

    千次阅读 2019-01-28 10:31:21
    对于高度为n的平衡二叉树: 最少需h(n)结点,做多需要2^n-1结点。 h(n)=h(n-1)+h(n-2)+1 h(0)=0 h(1)=1 h(2)=2
  • 给出一个完全二叉树,求出该树的节点个数 解题思路 最直观的一种解法:遍历整颗完全二叉树,记录每一个节点 class Solution { public int countNodes(TreeNode root) { if (root == null){ return 0; } ...
  • 递推关系 A(1)=1 A(2)=2 A(n+2)=A(n+1)+A(n)+1 子树高度为n+1,n以及根节点 你可以照这以此类推就可以得出答案了。算下A(4)=7     设f(n)为高度为n的平衡二叉树最少含有的节点数,则:f(1) = 1;f(2) = 2...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 47,745
精华内容 19,098
关键字:

完全二叉树最多有多少个节点