几日前在微博上和清华一博士讨论起一道数据结构选择题，我非常信心满满地给出了答案并且以为是对的，却发现和他给的标准答案相去甚远，去wiki和NIST网站查了一下才知道，原来中国大陆教材中的定义和美国以及我国港澳台地区是完全不同的.本科时用的数据结构教材虽然也是国外的，但是由于当时学习没有注意这些概念，之后就受考研时国内教材和考试的荼毒太深了.

满二叉树

国内定义

   一棵深度为k且有2^k-1个结点的二叉树称为满二叉树.

严蔚敏《数据结构(C语言版)》124页

   国内教材都采用了以上定义，且在考研、计算机等级考试、软考等国家行为的考试中采取了这一定义,认为所谓满二叉树就是每一层的结点数都达到最多的二叉树。但实际上这一定义与国际通用的定义是不符的.

美国和国际定义

   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.

http://xlinux.nist.gov/dads/HTML/fullBinaryTree.html

   既美帝的意思是，任意结点，要么左右孩子都有，要么没有孩子，或者这样描述“任意节点，要么是叶子结点，要么是同时具备左右孩子的结点”, 这样的二叉树就是满二叉树.

完全二叉树

国内定义

   可以对满二叉树(此处指国内定义的满二叉树)的结点进行编号，约定编号从根结点起，自上而下，自左至右.由此可引出完全二叉树的定义.深度为k的，结点数为n的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1到n的结点一一对应时，称之为完全二叉树.

严蔚敏《数据结构(C语言版)》124页

   也就是国内定义的k层的完全二叉树，前k-1层是满的，符合国内满二叉树定义，最后一层的结点满足:

• 若它为右孩子，它的父亲一定有左孩子

• 对于某个结点，他的父结点左侧的所兄弟和所有堂兄弟，都同时有左右孩子

美国和国际定义

   A binary tree in which every level, except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.A complete binary tree has 2^k nodes at every depth k < n and between 2^n and 2^(n+1)-1 nodes altogether. It can be efficiently implemented as an array, where a node at index i has children at indexes 2i and 2i+1 and a parent at index i/2, with one-based indexing. If child index is greater than the number of nodes, the child does not exist.

http://xlinux.nist.gov/dads/HTML/completeBinaryTree.html

   文中的意思是说完全二叉树是除了最后一层可能没有完全填满，同时最后一层的结点，都是尽可能的往左，不可能出现有结点左边无兄弟的情形.

   这个定义上，中美终于达成了一致了，呵呵.

完美二叉树

   perfect binary tree是其实就是国内定义的满二叉树，似乎国内教材一般不会提及这个概念，所以下面就提供美帝的概念定义.

   A binary tree with all leaf nodes at the same depth. All internal nodes have degree 2.A perfect binary tree has 2^(n+1)-1 nodes, where n is the height. It can be efficiently implemented as an array, where a node at index i has children at indexes 2i and 2i+1 and a parent at index i/2.A complete binary tree may be seen as a perfect binary tree with some extra leaf nodes at depth n+1, all toward the left.

http://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html

后注

   建议本科学习采用国外教材，尤其应当多读原版英文教材.另外，堆结构说明的时候可以讲类似于完全二叉树.

建议继续学习：

1. 数据映射–平衡二叉有序树    (阅读：3433)
2. 二叉树迭代器算法    (阅读：3189)
3. STL笔记之二叉查找树    (阅读：3052)
4. 数据结构之treap    (阅读：2687)