什么是完全二叉树

完全二叉树(Complete Binary Tree)

若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。

叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1

二叉树是一类非常重要的树形结构，它可以递归地定义如下：

二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n1和n2分别表示T，u(1)和u(2)的结点数，则有n=1+n1+n2 。u(1)和u(2)有时分别称为T的第一和第二子树。

因此，二叉树的根可以有空的左子树或空的右子树，或者左、右子树均为空。

在二叉树中，每个结点至多有两个儿子，并且有左、右之分。因此任一结点的儿子不外4种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一个右儿子。

满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树；完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。

满二叉树和完全二叉树的区别：

完全二叉树是深度为k，有n个结点的二叉树，当且仅当其每一个结点，都与深度为k的满二叉树中编号从1至n的结点逐一对应的二叉树。完全二叉树的叶子结点只可能在层次最大的两层上出现。

对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l或者I加1。满二叉树是一棵深度为k，且有2的k次方减1个节点的二叉树。满二叉树的每一层上的结点数都是最大结点数。

满二叉树与完全二叉树的关系：

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。完全二叉树是一种叶子结点只能出现在最下层和次下层且最下层的叶子结点集中在树的左边的特殊二叉树。

当树的深度相同时，若对树的结点按从上至下、从左到右的顺序进行编号，则在两种树上同一个位置上的结点的编号相同。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

以上就是关于什么是完全二叉树全部的内容，包括:什么是完全二叉树、为什么说“满二叉树也是完全二叉树”、满二叉树和完全二叉树的区别等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！