二叉树的概念

二叉树是n(n>=0)个结点的有限集合
1）n=0时，二叉树为空
2）n>0时，由根结点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树也分别是一棵二叉树

特点：

1. 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点
2. 二叉树的左右子树不能任意颠倒，如果某结点只有一棵子树，一定要指明它是左子树还是右子树

二叉树 VS 度为2的有序树：
1）二叉树可以为空，而度为2的有序树至少有三个结点
2）二叉树的孩子结点始终有左右之分，而度为2的有序树的孩子结点次序是相对的

斜树：所有结点都只有左子树的二叉树称为左斜树，所有结点都只有右子树的二叉树称为右斜树

1. 每一层只有一个结点
2. 斜树的结点个数与其深度相同

满二叉树：一棵高度为h，且含有2^h-1个结点的二叉树为满二叉树【在一棵二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上】

1. 叶子只能出现在最下一层
2. 只有度为0和度为2的结点

完全二叉树：设一个高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1～n的结点一一对应时，称为完全二叉树

1. 深度为k的完全二叉树在k-1层是满二叉树
2. 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在左侧连续的位置
3. 如果有度为1的结点，只可能有一个，且该结点只有左孩子
   

完全二叉树的性质：

二叉排序树：一棵二叉树，若树非空则具有如下性质：对任意结点若存在左子树或右子树，则其左子树上所有结点的关键字均小于该结点，右子树上所有结点的关键字均大于该结点

平衡二叉树：树上任意结点的左子树和右子树的高度差不超过1

二叉树的性质：