关于数据结构中一些二叉树的定义
1、满二叉树
定义：除最后一层的结点外，每一层的所有结点都有两个子结点。
另外一个定义：深度为k且有2^k-1个结点的二叉树。
满二叉树是一颗树深度为h，最大层数为k，且深度与最大层数相同，即k=h;
它的叶子数是： 2^(h-1)
第k层的结点数是： 2^(k-1)
总结点数是： 2^k-1 (2的k次方减一)
总节点数一定是奇数。
2、完全二叉树
如上图，完全二叉树只比满二叉树少了最后几个结点，所以满二叉树是一种特殊的完全二叉树。
完全二叉树是效率很高的数据结构，堆是一种完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。
3、最优二叉树（哈夫曼树，Huffman树）
首先，介绍树的带权路径长度，树的带权路径长度为树中所有叶子结点的带权路径长度之和。带权路径长度最小的二叉树称作最优二叉树或赫夫曼树。
注意：哈夫曼树不一定是完全二叉树！！
4、二叉排序树
二叉排序树（Binary Sort Tree）又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树，对于任意一个结点P而言： （1）若结点P的左子树不空，则左子树上所有结点的值均小于结点P的值； （2）若右子树不空，则右子树上所有结点的值均大于结点P的值； （3）结点P的左、右子树也分别为二叉排序树；
简单的准则：值的大小，左<根<右
5、二叉判定树
描述折半查找过程的二叉树为判定树。
判定树首先是一个二叉排序树，具有n个结点的判定树具有与具有n个结点的完全二叉树的深度完全相同，其深度为：
。
在折半查找时，查找成功不成功，和给定值比较的次数最多为
6、平衡二叉树
平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
转载自：http://blog.****.net/hehainan_86/article/details/11538383