完全二叉树和满二叉树 完全二叉树的定义

满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,.(这个似乎很好想像出来) 完全二叉树——只有最下面的两层结点度小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树;(这个,就说从满二叉树里,最下一层的叶子,如果是从右往左拿掉叶子,不论多少,都是完全的,如果不是从右往左拿,而是在中间拿掉了一个,就是不完全的)

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

完全二叉树的定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树. 特点:叶子结点只可能在层次最大的两层上出现;对任一结点,若其右分支下子孙的最大层次为l,则其左分支下子孙的最大层次必为l 或l+1 满二叉树:一棵深度为k,且有2的(k)次方-1个节点的二叉树 特点:每一层上的结点数都是最大结点数

差别就在最后一层上,满二叉树定义,除最后一层外,每一层上的所有节点有两个子节点,也就是说倒数第二层的每个节点都有两个子节点,那么最后一层的节点数一定是倒数第二层的2倍,所以最后一层一个节点都不能缺.而完全二叉树,在最后一层的节点是可以缺少的,其节点数可能是倒数第二层节点数的2倍(满二叉树一定是完全二叉树),也可能是1个,2个,只不过,这些缺的节点只能是最右边的.

首先要了解什么是满二叉树,什么是完全二叉树.(1)满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点(最后一层上的无子结点的结点为叶子结点).也可以这样理解,除叶子结点外的所有结点均有两个子结点.节点数达到最大值.所有叶子结点必须在同一层上.(2)完全二叉树:若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树.所以说,满二叉树是完全二叉树的特例,因为满二叉树已经满了,而完全并不代表满.因此,这句话是对的.

我认为是的 定义:一棵深度为k且有2的k次方减1个结点的二叉树是满二叉树.深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树.可见,满二叉树是结点数最多的完全二叉树.

因为满二叉树也符合完全二叉树每个结点有而且只有两个子孙的定义

不是,但满二叉树是完全二叉树

满二叉树定义:一棵深度为k,且有2的(k)次方-1个节点的二叉树 如果已知深度k,那么叶数为2的(k-1)次方个叶子 如果已知总节点数n (n = 2的(k)次方- 1),那么叶数为(n + 1) / 2 比如一个深度为3的满二叉树,一共有7个节点(第1层1个,第2层2个,第3层4个),叶子数为4 (4 = 2的(3 - 1)次方, 4 = (7 + 1) / 2 完全二叉树的定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树 完全二叉树的叶子数为(n + 1) / 2取下整 例如5个节点的完全二叉树,第二层2个节点,其中右节点为叶子;第三层2个节点都是叶子

完全二叉树是一棵满二叉树