满二叉树

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

又叫Full Binary Tree. 除叶子节点外，每一层上的所有节点都有两个子节点(最后一层上的无子结点的结点为叶子结点)。也可以这样理解，除叶子结点外的所有节点均有两个子节点。节点数达到最大值。所有叶子结点必须在同一层上.

如果一颗树深度为d，最大层数为k

它的叶子数是: 2^d

第k层的节点数是: 2^(k-1)

总节点数是: 2^k-1 (2的k次方减一)

总节点数一定是奇数。

定义介绍

美国以及国际上所定义的满二叉树 ，即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.换个说法即要么为叶子结点，要么同时具有左右孩子。霍夫曼树是符合这种定义的，满足国际上定义的满二叉树，但是不满足国内的定义.

是程序算法中的一种算法模式。

在二叉树中出现空的子树（包括树叶）上增加空的树叶，使其成为满二叉树的二叉树称之为扩充二叉树。

完全二叉树(Complete Binary Tree)

若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

1

/ \

2 3

\ /

4 5 是均衡二叉树，因为它去掉叶结点及相应的树枝后，

变成了：

1

/ \

2 3 ，这是一个二叉树。

1

/ \

2 3

而 \ / \ 则不是，因为它去掉叶结点及相应的树枝后，

4 5 6

/

7

变成了：

1

/ \

2 3

\

4

很显然，这并不是一个完全二叉树。