作业帮 > 数学 > 作业

完全二叉树的定义,

来源:学生作业帮 编辑:拍题作业网作业帮 分类:数学作业 时间:2024/03/29 21:02:15
完全二叉树的定义,
完全二叉树定义完全二叉树(Complete Binary Tree)若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树.完全二叉树是由满二叉树而引出来的.对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树.若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树.完全二叉树特点叶子结点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1;出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下:var tree:array[1..n]of longint;{n:integer;n>=1}对于tree[i],有如下特点:(1)若i为奇数且i>1,那么tree的左兄弟为tree[i-1];(2)若i为偶数且i1,tree的双亲为tree[i div 2];(4)若2*i
再问: 我还是看不明白,能否把完全二叉树的所有情况列举下来,除满二叉树外,然后拍个照给我
再答: 满二叉树(Full Binary Tree):  除最后一层无任何子节点外,每一层上的所有结点都有两个子结点(最后一层上的无子结点的结点为叶子结点)。也可以这样理解,除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.

一颗树深度为h,最大层数为k,深度与最大层数相同,k=h;  它的叶子数是: 2^h   第k层的结点数是: 2^(k-1)   总结点数是: 2^k-1 (2的k次方减一)   总节点数一定是奇数。

完全二叉树(Complete Binary Tree)  若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。   完全二叉树是由满二叉树而引出来的。对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。