为什么完全二叉树中度为1的结点只能是1或0?

为什么完全二叉树中度为1的结点只能是1或0?~

满二叉树的所有节点的度都是2或者0，没有度为1的节点。
完全二叉树，可以看做是满二叉树在最后一层从右往左砍掉一些节点。
如果从满二叉树中在最后一层自左向右砍掉的节点数是偶数，那么该完全二叉树中度为1的节点数就是0。
如果砍掉的节点数是奇数，那么该完全二叉树中就有且仅有一个节点的度为1.
完全二叉树：
若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
满二叉树 :
又叫Full Binary Tree. 除叶子节点外，每一层上的所有节点都有两个子节点(最后一层上的无子结点的结点为叶子结点)。也可以这样理解，除叶子结点外的所有节点均有两个子节点。节点数达到最大值。所有叶子结点必须在同一层上.

两者的区别：
完全二叉树：除最后一层可能不满以外，其他各层都达到该层节点的最大数，最后一层如果不满，该层所有节点都全部靠左排满二叉树：所有层的节点数都达到最大

完全二叉树，可以看做是满二叉树在最后一层从右往左砍掉一些节点。注意，满二叉树的所有节点的度都是2或者0，没有度为1的节点。
如果从满二叉树中在最后一层自左向右砍掉的节点数是偶数，那么该完全二叉树中度为1的节点数就是0。如果砍掉的节点数是奇数，那么该完全二叉树中就有且仅有一个节点的度为1.

因为二叉树所有结点滴个数都不大于2，所以结点总数n=n0+n1+n2 (1)

又因为度为1和度为2的结点分别有1个子树和2个子树，所以，二叉树中子树结点就有n(子）=n1+2n2

二叉树中只有根节点不是子树结点，所以二叉树结点总数n=n(子）+1 即 n=n1+2n2+1 (2)

结合（1）式和（2）式就得n0=n2+1

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，则 ：

①n= n0+n1+n2 （其中n为完全二叉树的结点总数）；又因为一个度为2的结点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他结点都有父结点，

②n= 1+n1+2*n2 ；由①、②两式把n2消去得：n= 2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。

简便来算，就是 n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。

扩展资料：

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）

(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。

一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。

参考资料：百度百科---完全二叉树

因为二叉树所有结点滴个数都不大于2，所以结点总数n=n0+n1+n2 (1)

又因为度为1和度为2的结点分别有1个子树和2个子树，所以，二叉树中子树结点就有n(子）=n1+2n2

二叉树中只有根节点不是子树结点，所以二叉树结点总数n=n(子）+1 即 n=n1+2n2+1 (2)

结合（1）式和（2）式就得n0=n2+1

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，则 ：

①n= n0+n1+n2 （其中n为完全二叉树的结点总数）；又因为一个度为2的结点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他结点都有父结点，

②n= 1+n1+2*n2 ；由①、②两式把n2消去得：n= 2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。

简便来算，就是 n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。

扩展资料：

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）

(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。

一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。

百度百科-百度百科-完全二叉树

看图~ 6-12的那个结点就是度为一的结点~ 只有一个~ 所谓度就是结点的后面有几个分叉~ 即直接后驱~完全二叉树的定义：二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的节点都连续集中在最左边~  图中的8、9、10、11、12就是第h层上的结点~即最后一层上的结点~二叉树定义第 h 层所有的节点都连续集中在最左边，图中结点6与7就不能发生下面的情况：6结点只有一个左子树，而7结点也有子树，以为都要从左边排~ 必须排在6结点的右子树上，也就是说最后一层的结点的最后一个要么是度为1，要么度为2。自己理解吧~ 希望能帮到忙~

满二叉树的所有节点的度都是2或者0，没有度为1的节点。

完全二叉树，可以看做是满二叉树在最后一层从右往左砍掉一些节点。

如果从满二叉树中在最后一层自左向右砍掉的节点数是偶数，那么该完全二叉树中度为1的节点数就是0。

如果砍掉的节点数是奇数，那么该完全二叉树中就有且仅有一个节点的度为1.

完全二叉树，可以看做是满二叉树在最后一层从右往左砍掉一些节点。注意，满二叉树的所有节点的度都是2或者0，没有度为1的节点。
如果从满二叉树中在最后一层自左向右砍掉的节点数是偶数，那么该完全二叉树中度为1的节点数就是0。如果砍掉的节点数是奇数，那么该完全二叉树中就有且仅有一个节点的度为1.

---

龙川县17215081139： 为什么完全二叉树如果有度为1的节点,只可能有一个,各位大神帮帮忙啊 - ？
敛蓝迪素： 序遍达二叉树: void inordertraverse(bitree t) /*中序遍历右子树*/ } else { lsub=bitreedepth(t->lchild);/ else { *t=(bitree)malloc(sizeof(bitnode)); /*生成根结点*/ if(; if(t==null) { return 0:rsub)+1; if(ch=='#') *t=null; createbittree(&((*t)->/存在则加1算出他的...

龙川县17215081139： 一颗完全二叉树上有1001个结点,求叶子节点个数有种方法为什么能直接除以2向上取整就可以获得正确答案501了, - ？
敛蓝迪素：[答案] 二叉树性质:n0 = n2 + 1 因为n0 + n1 + n2 = 1001 所以2n2 + 1 + n1 = 1001 由于该等式右边为奇数,左边的n1只能是偶数 又因为完全二叉树中度为1结点个数n1要么是0要么是1 所以只能是0 因此n2 = 500 所以n0 = 501

龙川县17215081139： 数据结构问题:一棵完全二叉树有100个结点,度为一的结点有几个,叶子结点有几个? - ？
敛蓝迪素： 根据二叉树的性质:对于一棵非空的二叉树,如果叶子节点数为n0,度为2的结点数为n2,则no=n2+1. 根据完全二叉树的定义可得:在完全二叉树中度为1的结点n1只能取两种情况,要么为0,要么为1. 所以:n0+n1+n2=100 又n0=n2+1; 2n2=99-n1; 因为结点数为整数,所以n1=1,n2=49,n0=50 所以度为1的结点有一个,叶子结点有50个

龙川县17215081139： 一个具有53个节点的完全二叉树,其度为一的结点个数为 - ？
敛蓝迪素： 设二叉树中度为0、1、2的结点个数分别为n0, n1, n2 因此n0 + n1 + n2 = 53 按照二叉树的性质n0 = n2 + 1 代入得:2n2 + 1 + n1 = 53 因为完全二叉树中度为1的结点个数最多1个,因此满足上式只能是n1 = 0 即度为1结点个数为0

龙川县17215081139： 一棵完全二叉树共有360个结点,该二叉树中度为1的结点数为 - ？
敛蓝迪素： 总结点数=叶子结点数+度为1的结点数+度为2的结点数. 叶子结点数=度为2的结点数+1.:对于一个完全二叉树来说,度为一的结点树,只有0,或者1,两种可能. 公式一:叶子结点树=度为2的结点树+1.=总结点数/2 公式二:总结点树=度为...

龙川县17215081139： 二叉树算法 - ？
敛蓝迪素： 二叉树是没有度为1的结点.完全二叉树定义:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层从右向左连续缺若干结点,这就是完全二叉树.完全二叉树叶子结点的算法:如果一棵具有n个结点的深...

龙川县17215081139： 求高手入入入!!!数据结构 关于二叉树 一棵124个叶结点的完全二叉树,最多有?结点? 答案给的 - ？
敛蓝迪素： 一棵124个叶结点的完全二叉树,假设n0为叶子结点数,n1为度为1结点数,n2为度为2结点数,则有总结点数为n0+n1+n2;而n2=n0-1=123;且完全二叉树中度为1的结点只能为一个或0个,所以总结点数为124+1+123=248个

龙川县17215081139： 已知完全二叉树有30个结点那么整个二叉树有几个度为1的结点 - ？
敛蓝迪素： 度为1的结点个数为1,因为完全二叉树度为1的定点个数不是0就是1,而对于二叉树,度为0的结点的个数比度为2的结点的个数多1,所以度为0和度为2结点个数之和为基数,总节点数为30,所以有一个度为1的结点

龙川县17215081139： 只有一个结点的二叉树度为0. 对不对为什么 - ？
敛蓝迪素： 对的,在二叉树的示意图中:椭圆表示二叉树的结点. 而结点拥有的子树棵数称为结点的度.树中所有结点的度的最大值就是树的度.因为只有一个结点的二叉树没有子树,故它的结点的度及树的度都为零.

龙川县17215081139： 二叉树结点计算 - ？
敛蓝迪素： 1.深度为m的满二叉树有2^m-1个结点. 因为满二叉树的定义为:一颗深度为k且有2^k-1个结点的二叉树称为满二叉树. 2.若要树深为最小,显然要使除最后一层外的每一层都有尽可能多的结点,即要二叉树为完全二叉树.由二叉树的一个重要性质...