满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k)-1，则它就是满二叉树。国外(国际)定义:abinarytreeTisfullifeachnodeiseitheraleaforpossessesexactlytwochildnodes.大意为：如果一棵二叉树的结点要么是叶子结点，要么它有两个孩子结点，这样的树就是满二叉树。

中文名：满二叉树

外文名：FullBinaryTree（国内外定义不同，有歧义）

类别：二叉树

性质：树度为0或2

1、基本信息

定义：

国内：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k)-1，则它就是满二叉树。也就是说，满二叉树不存在度为1的结点。

国外(国际)定义:abinarytreeTisfullifeachnodeiseitheraleaforpossessesexactlytwochildnodes.

大意为：如果一棵二叉树的结点要么是叶子，要么这个结点有两个孩子结点，这样的树就是满二叉树。

由于种种原因，导致了同一个名词在国内外有2种不同的定义。他们之间的差别是非常大的。下面是详细的分析。

从图形形态上看，满二叉树外观上是一个三角形。

从数学上看，满二叉树的各个层的结点数形成一个首项为1，公比为2的等比数列。

因此由等比数列的公式，满二叉树满足如下性质。

1、一个层数为k的满二叉树总结点数为：。因此满二叉树的结点树一定是奇数个。

2、第i层上的结点数为：

3、一个层数为k的满二叉树的叶子结点个数（也就是最后一层）：

满二叉树的结点要么是叶子结点，度为0，要么是度为2的结点，不存在度为1的结点。

因此，右图中这个二叉树也是满二叉树。但是按照国内的定义，它却不是满二叉树。

美国以及国际上所定义的满二叉树，即fullbinarytree,和国内的定义不同，美国NIST给出的定义为：Abinarytreeinwhicheachnodehasexactlyzeroortwochildren.Inotherwords,everynodeiseitheraleaforhastwochildren.Forefficiency,anyHuffmancodingisafullbinarytree.

满二叉树的任意节点，要么度为0，要么度为2.换个说法即要么为叶子结点，要么同时具有左右孩子。霍夫曼树是符合这种定义的，满足国际上定义的满二叉树，但是不满足国内的定义.

2、确定使用

在国际交流场合，包括学术会议发表论文等都应该使用美国和国际定义.在国内的各种考试场合，比如研究生考试/软考/计算机等级考试等，都应该使用国内教材的定义.在校学生的校级考根据所在学校采用教材情况而定.