满二叉树

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

国外(国际)定义:a binary tree T is full if each node is either a leaf orpossesses exactly two childnodes.

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

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

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

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

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

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

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

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

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

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

美国以及国际上所定义的满二叉树，即full binary tree,和国内的定义不同，美国NIST给出的定义为：A binary tree in which each node has exactly zero or two children. In other words, every node is either a leaf or has two children. For efficiency, any Huffman coding is a full binary tree.

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

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