满二叉树和完全二叉树到底有什么区别,他们定义不是差不多?

小开王子2022-10-04 11:39:541条回答

满二叉树和完全二叉树到底有什么区别,他们定义不是差不多?
满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点.
完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点.

已提交，审核后显示！提交回复

共1条回复

KAME至上共回答了13个问题 | 采纳率84.6%: 差别就在最后一层上,
满二叉树定义,除最后一层外,每一层上的所有节点有两个子节点,也就是说倒数第二层的每个节点都有两个子节点,那么最后一层的节点数一定是倒数第二层的2倍,所以最后一层一个节点都不能缺.
而完全二叉树,在最后一层的节点是可以缺少的,其节点数可能是倒数第二层节点数的2倍（满二叉树一定是完全二叉树）,也可能是1个,2个,只不过,这些缺的节点只能是最右边的.; 1年前

相关推荐

有n（n>0）个分支结点的满二叉树的深度为? 有n（n>0）个分支结点的满二叉树的深度为? 因为满二叉树只有度为2和0,有n个分支结点,所以n0+n2=2n+1,深度为log2（2n+1）+1,答案是log2（n+1）,哪里错了, 第二种想法,既然n为分支节点度为2,那就直接对n个结点求深度,求得log2n+1,之后再补上一层即log2n+2,好像也为错啊,分支节点下面肯定还有一层,加上就还原了,不可能出现加2层 为啥错了说明理由 带公式我也会带错无语了,还有就是怎么log一会有地一会变得没底了 log((2n+1)+1)=log(2n+2)=log(2*(n+1))这个底? log(n+1)+1=log(2*(n+1))这个底?log(n+1)+1 底是啥,看不懂啊 丁尹1年前1: 婆提达多共回答了15个问题 | 采纳率80%

答案应该是log(2*(n+1)),其中log表示以2为底的对数函数.
我看了你的想法,都没有错,但是计算貌似不对.
1、
因为满二叉树只有度为2和0,有n个分支结点,所以n0+n2=2n+1,深度为log((2n+1)+1),
log((2n+1)+1)=log(2n+2)=log(2*(n+1))
2、
既然n为分支节点度为2,那就直接对n个结点求深度,求得log(n+1),
之后再补上一层即log(n+1)+1,
log(n+1)+1=log(2*(n+1))

1年前查看全部

深度为h且有（）个结点的二叉树称为满二叉树. miaoxiaozhuo1年前1: lmm2008 共回答了16个问题 | 采纳率100%

如果根结点的层次为1
18题：C
19题：A

1年前查看全部

一颗深度为n（n＞1）的满二叉树中共有几个结点 lubing9871年前1: 我行霸道共回答了18个问题 | 采纳率88.9%

2的k次方-1

1年前查看全部

对一个满二叉树,有m个叶子结点,n个结点,深度为h,则（）.A.n=h+m B.h+m 对一个满二叉树,有m个叶子结点,n个结点,深度为h,则（）.A.n=h+m B.h+m 对一个满二叉树,有m个叶子结点,n个结点,深度为h,则（）.A.n=h+mx09x09x09B.h+m=2nx09x09x09C.m=h-1x09x09x09D.n=2h-1 渌汩涔1年前1: 雪浪花L 共回答了19个问题 | 采纳率89.5%

这个比较简单
零度的设为m,一度的为x,二度的节点为y,可得
m+x+y = n;
m = y + 1; (书上的公式)
代进去可得：m+x+m-1=n;
所以x=n-2m+1; (这就是度为1的节点个数)

1年前查看全部

若一棵满二叉树有2047个结点,则该二叉树中叶结点的个数为（）. 一定有奇迹1年前1: ranse9999 共回答了18个问题 | 采纳率94.4%

2047=2048-1=2的11次方 - 1 代表这个树有11层第11层的结点全是叶结点：有2的10次方个也就是 (1024个)

1年前查看全部

1.28 在深度为5的满二叉树中,叶子结点的个数为 A）32 B）31 C）16 D）15 1.28 在深度为5的满二叉树中,叶子结点的个数为 A）32 B）31 C）16 D）15 access中有关树的知识、希望能给详细答案? 教爷子1年前1: 鬼水凶灵共回答了19个问题 | 采纳率84.2%

我的天~你都问了些什么人啊~就一楼的是对的~答案是16 叶子结点就是没有后件的结点~说白了~就是二叉树的最后一层~深度为K的二叉树~最多有2^k-1个结点~最多有2^(k-1)个结点~所以此题~最多有2^5-1=31个结点~最多有2^(5-1)=16个叶子结点~

1年前查看全部

数据结构满二叉树问题？对一个满二叉树，m个树叶，n个结点，深度为h，则A.n=h+m B.h+m=2nC.m=h-1 D 数据结构满二叉树问题？ 对一个满二叉树，m个树叶，n个结点，深度为h，则A.n=h+m B.h+m=2nC.m=h-1 D.n=2h-1求高手解答，写出求解过程，感激不尽 小向1年前1: davi_lau 共回答了18个问题 | 采纳率88.9%

深度为 h 的满二叉树是：
第1层1个结点
第2层2个结点
第3层4个结点
第4层8个结点
...
第h层2^(h-1)个结点，最后一层都是树叶，所以 m = 2^(h-1)
（^ 是次方的意思）结点数目 n = 1 + 2 + 4 + 8 + ... + 2^(h-1) = 2^h - 1 选项 A、B、C 都不靠谱。
选项 D 的 h 如果是上标形式的，写成 2 的 h 次方，那就是答案了。

1年前查看全部

在深度为7的满二叉树中,度为2的结点个数为_________. 在深度为7的满二叉树中,度为2的结点个数为_________. 这里的度为2的结点个数是什么意思? hz921年前1: 条条大道通uu 共回答了17个问题 | 采纳率82.4%

度为2的节点就是该节点既有左子树,又有右子树
深度为7的满二叉树总共的节点数为2^7-1=127;
又因为是满二叉树,所以只有度为2的和度为0的节点
,叶子节点的数目为:2^(7-1)
=64,所以有度为2的结点个数为=127-64=63个.

1年前查看全部

(23) 在深度为5的满二叉树中,叶子结点的个数为______. (23) 在深度为5的满二叉树中,叶子结点的个数为______. A.32 B.31 C.16 D.15 caobi38381年前1: sky01101011 共回答了22个问题 | 采纳率81.8%

（23）[答案]C
[考点]数据结构与算法
[评析]
首先搞清楚满二叉树与完全二叉树之间的区别,前面已解释过.
依次从上到下,可得出：
第1层结点数为1；
第2层结点数为2*1=2；
第3层结点数为2*2=4；
第n层结点数为2的n-1次幂,如图所示

1年前查看全部

二叉树结点计算问1、深度为m的满二叉树有几个结点?2、设二叉树根结点的层次为0,对含有100个根结点的二叉树,可能的最 二叉树结点计算 问1、深度为m的满二叉树有几个结点? 2、设二叉树根结点的层次为0,对含有100个根结点的二叉树,可能的最小树身为多少?怎么计算? andycws1年前1: 念奴娇ktly 共回答了25个问题 | 采纳率84%

1.深度为m的满二叉树有2^m-1个结点.
因为满二叉树的定义为:一颗深度为k且有2^k-1个结点的二叉树称为满二叉树.
2.若要树深为最小,显然要使除最后一层外的每一层都有尽可能多的结点,即要二叉树为完全二叉树.
由二叉树的一个重要性质:具有n个结点的完全二叉树的深度为[log2n]+1.(这是在根节点层次为1时,若为0,将+1去掉即可)
log2n是以2为底n的对数
[log2n]为不大于log2n的最大整数
可知,含有100个(根)结点的二叉树,(应该没"根"字吧)
可能的最小树深为[log2 100 ]+1
二叉树根结点的层次为0时,可能的最小树深为[log2 100 ]
即为6.
可以这样计算:确定最小树深当且仅当二叉树为完全二叉树时出现,设深度为k,(此时设二叉树根结点的层次为0)有:
2^0+2^1+2^2+...+2^(k-1)

1年前查看全部

深度为6的满二叉树中,度为2的结点个数是31还是63? 明月如霜人如画1年前1: ricardo17 共回答了16个问题 | 采纳率87.5%

满二叉树除最后一层外都是2个结点,那么第一层1个结点,第二层2个,第三层4个,第四层8个,第五层16个,第六层度为0,所以共31个

1年前查看全部

结点为什么在深度为7的满二叉树中,度为2的结点个数为多少和深度为5的满二叉树有几个叶子结点的算法不同 润物丝宇1年前1: 可乐加冰的感觉共回答了11个问题 | 采纳率72.7%

就是叶子-1个
满二叉树就是
除最后一层外,每一层上的所有结点都有两个子结点（最后一层上的结点为叶子结点）.也可以这样理解,除叶子结点外的所有结点均有两个子结点

1年前查看全部

在深度为5的满二叉树中,叶子结点的个数为多少? 山东猪八戒1年前1: 68593165 共回答了16个问题 | 采纳率81.3%

在满二叉树的第k层上有：2的k次方减再1个结点 (树的最大层次称为树的深度,没有后件的结点称为叶子结点.) 深度为5的满二叉树的叶子结点为31个

1年前查看全部

每次都随机从满二叉树选一个点,这个点以及其children都被删掉.求全部删空的次数期望
每次都随机从满二叉树选一个点,这个点以及其children都被删掉.求全部删空的次数期望
原题：the juarez cartel is being investigated by the federales.the n members of the cartel are organized in a perfect binary tree.each day,the federales select a node uniformly at random from the tree.they then arrest this node and all nodes below it,due to incriminating information obtained about subordinates.all arrested nodes are removed from the tree.
what is the expected number of days until all nodes are removed?hint:for each node v,let xv be an indicator random variable that is 1 if v is arrested before any of its ancestors and 0 otherwise.use linarity of expectation.
翻译：jc被federales***.jc有n个成员而且可以构成一个完全二叉树.每天,f都从所以节点里面随机选一个节点,然后***那个节点以及所以在它下面的节点.然后这些节点都会从树中删除.
问：所有节点都***所需要的天数的期望是多少?提示：任意节点v,设xv为一个随机变量,xv=1如果v再所以其父节点被***前被***,xv=0其他情况.运用线性期望.

阿俊11881年前0: 共回答了个问题 | 采纳率

查看全部

对于一棵满二叉树,m个树叶,n个结点,深度为h,则这3者之间有关系 山东笑三少1年前1: 蓝梦傲雪共回答了21个问题 | 采纳率95.2%

m=2^h-1
n=(2^h)-1

1年前查看全部

设二叉树根结点的层次为1,一棵深度为h的满二叉树中的结点个数是（） A．2h B．2h-1 C．2h-1 D．2h+1 涛声晓筑1年前1: xtempler 共回答了22个问题 | 采纳率86.4%

2(h)方 - 1
由于B和C是一样的,所以不知道那个表示h 方

1年前查看全部

请教数据结构填空题1、对一棵深度为19的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为（）？2、设某无向图中顶 请教数据结构填空题 1、对一棵深度为19的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为（）？ 2、设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=（）？ 3、设一组记录关键字序列为（80，70，33，65，24，56，48），则用筛选法建成的初始堆（小顶堆）为（）？ 上海居不易1年前1: 爱情龟共回答了22个问题 | 采纳率81.8%

1、51/2下取整，双亲节点为编号为25。
2、图中所有顶点的度之和为边的二倍，所以e=d/2.

1年前查看全部

在深度为7的满二叉树中,度为2的结点个数为多少?麻烦把过程写出来. 逸仙泉1年前1: metalogan 共回答了14个问题 | 采纳率78.6%

满二叉树：只每个节点的度只有可能是0或2.因此此题就是用总节点数减去叶节点数:
2^7-1-2^6=2^6-1

1年前查看全部

能给一个通俗化,口语化一点的完全二叉树和满二叉树的定义吗,自己自学——说实在的真的很难看懂! 能给一个通俗化,口语化一点的完全二叉树和满二叉树的定义吗,自己自学——说实在的真的很难看懂! 幻魇の假肥猫你的答案中的完全二叉树不怎么懂～～ druan1年前1: 伊飘儿共回答了14个问题 | 采纳率92.9%

满二叉树:除了叶节点,每个父亲节点都有两个子树的,满满的二叉树
完全二叉树:所有节点集中在树左边的二叉树,就是说除了叶节点,每个节点都只有左节点或者有两个节点,而没有只有右节点情况

1年前查看全部

满二叉树和完全二叉树到底有什么区别,他们定义不是差不多?

共1条回复

相关推荐

大家在问