本文目录
- C语言 什么叫完全二叉树
- 完全二叉树与满二叉树的区别是什么
- 完全二叉树为什么最适合顺序存储结构
- 什么是完全二叉树
- 满二叉树和完全二叉树的区别
- 完全二叉树的定义
- 完全二叉树的叶子节点数公式是什么
- 完全二叉树叶子节点的算法
- 告诉了一棵完全二叉树的总结点个数，求叶子结点个数怎么计算谢谢帮助
C语言 什么叫完全二叉树
完全二叉树是一种特殊的二叉树。
定义：如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
例：
特点：
叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1。
完全二叉树第i层至多有2^（i-1）个节点，共i层的完全二叉树最多有2^i-1个节点。
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
完全二叉树与满二叉树的区别是什么
1、含义不同：
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
2、表示不同：
对于满二叉树，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。而完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。
对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
判断一棵树是否是完全二叉树的思路
1》如果树为空，则直接返回错
2》如果树不为空：层序遍历二叉树
2.1》如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
2.1》如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
2.2》如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空，且则该节点之后的队列中的结点都为叶子节点，该树才是完全二叉树，否则就不是完全二叉树；
以上内容参考：百度百科-完全二叉树
完全二叉树为什么最适合顺序存储结构
顺序存储充分利用满二叉树的特性，即每层的节点数分别为1、2、4、8等等2i+1，一个深度为i的二叉树最多只能包含2i-1个节点，因此只要定义一个长度为2i-1的数组即可存储这颗二叉树。
对于普通的不是满二叉树的，那些空出来的节点对应的数组元素留空即可，因此顺序存储会造成一定的空间浪费。如果是完全二叉树，就不会有空间浪费的情况；若是只有右子树，那么会造成相当大的浪费。
二叉树算法思路：
1、如果树为空，则直接返回错。
2、如果树不为空：层序遍历二叉树。
3、如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列。
4、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树。
5、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。
什么是完全二叉树
完全二叉树：满二叉树：完全二叉树，除最后一层可能不满以外，其他各层都达到该层节点的最大数，最后一层如果不满，该层所有节点都全部靠左排满二叉树，所有层的节点数都达到最大
满二叉树和完全二叉树的区别
满二叉树和完全二叉树的区别：
1、完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
2、对于满二叉树，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。而完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
扩展资料
性质
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为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。
参考资料：
百度百科-满二叉树
百度百科-完全二叉树
完全二叉树的定义
完全二叉树定义完全二叉树(Complete Binary Tree)若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
完全二叉树的叶子节点数公式是什么
完全二叉树的叶子节点数公式为：
设叶子节点数为n0, 度为1的节点数为n1，度为2的节点数为n2，总节点为n。
1、当n为奇数时（即度为1的节点为0个），n0= (n+1)/2。
2、当n为偶数（即度为1的节点为1个）， n0= n/2。
n1，n2，都可以求。
特殊类型：
1、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
2、完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。
3、完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。
相关术语：
1、结点：包含一个数据元素及若干指向子树分支的信息。
2、结点的度：一个结点拥有子树的数目称为结点的度。
3、叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。
4、结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。
5、树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。
以上内容参考 百度百科-二叉树
完全二叉树叶子节点的算法
设：度为i的结点数为ni，由二叉树的性质可知：n0 = n2 + 1……………………①式n = n0 + n1 + n2……………②式由①式可得 n2 = n0 - 1，带入②式得：n0 = （n + 1 - n1）/ 2由完全二叉树性质可知：如图，当n为偶数时，n1 = 1， n0 = n / 2
如图，当n为奇数时，n1 = 0，n0 = （n + 1）/2
将两式合并，写作：n0 = ⌊（n+1）/2⌋（向下取整符号不能丢）
扩展资料：
完全二叉树的特点:
1.叶子结点只可能在层次最大的两层上出现。
2.对任一结点，若其由分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1。
完全二叉树的性质：
1.具有n个结点的完全二叉树的深度为⌊log₂n⌋+1。
2.如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i，有：
（1）如果i=1，则结点i是二叉树的根节点，无双亲；如果i》1，则其双亲是结点⌊i/2⌋。
（2）如果2i》n，则结点i无左孩子；否则其左孩子是结点2i。
（3）如果2i+1》n，则结点i无右孩子；否则其右孩子是结点2i+1。
告诉了一棵完全二叉树的总结点个数，求叶子结点个数怎么计算谢谢帮助
前九层的结点就有2^9-1=511个
而第九层的结点数是2^(9-1)=256
所以，第十层的叶子结点数是699-511=188个
现在来算第九层的叶子结点个数：
由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。
因为第十层有188个，所以应该去掉第九层中的188 / 2=94个
所以，第九层的叶子结点个数是256-94=162，加上第十层有188个，最后结果是350个。
扩展资料：
二叉树性质
1、 在非空二叉树中，第i层的结点总数不超过
, i》=1；
2、深度为h的二叉树最多有
个结点(h》=1)，最少有h个结点；
3、对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
4、具有n个结点的完全二叉树的深度为
（注：[ ]表示向下取整）
5、有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果I》1，则其父结点的编号为I/2；
如果2*I《=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I》N，则无左孩子；
如果2*I+1《=N，则其右孩子的结点编号为2*I+1；若2*I+1》N，则无右孩子。
6、给定N个节点，能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。
7、设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i
参考资料来源：百度百科-二叉树