二、二叉树的相关概念

1、满二叉树
    如果一颗二叉树的任何结点或者是树叶，或者恰有两颗非空子树，则此二叉树称为满二叉树。

2、扩充二叉树
    对于原来二叉树里度数为1的分支结点，在它下面增加一个空树叶；对于原来二叉树的树叶，在它下面增加两个空树叶，由此得到的二叉树称为扩充二叉树。
    扩充二叉树是一种满二叉树。

3、Huffman树
    给出m个实数W0,W1,…,Wm-1(m≥2)，求一个具有m个外部结点的扩充二叉树，每个外部结点ki有一个Wi与之对应，作为它的权，使得带权外部路径长度

4、完全二叉树
    如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
    堆实质上是一棵完全二叉树结点的层次序列，此完全二叉树的每个结点对应于一个关键码，根结点对应于关键码。

5、二叉搜索树
    如果一棵二叉树的每个结点对应于一个关键码，整个二叉树各结点对应的关键码组成一个关键码集合，并且此关键码集合中的各个关键码在二叉树中是按一定次序排列的，这时称此二叉树为二叉搜索树(Binary Search Tree,BST)。