1、二叉树的定义

二叉树T：一个有穷的结点集合( 这个集合可以为空 )

若不为空，则它是由根结点和称为其左子树TL和右子树TR的 两个不相交的二叉树组成。

• 二叉树具体五种基本形态 :

• 二叉树的子树有左右顺序之分 :

• 特殊二叉树 :

1、斜二叉树(Skewed Binary Tree)：

2、完美二叉树(Perfect Binary Tree) 满二叉树(Full Binary Tree）：

3、完全二叉树 (Complete Binary Tree) ：

有n个结点的二叉树，对树中结点按 从上至下、从左到右顺序进行编号， 编号为i（1 ≤ i ≤ n）结点与满二叉树 中编号为 i 结点在二叉树中位置相同

下图不是完全二叉树：

2、二叉树几个重要性质

• 一个二叉树第i 层的最大结点数为：2^( i-1 ) (i >=1)

• 深度为k的二叉树有最大结点总数为： 2^ k-1 (k>=1)

• 对任何非空二叉树 T，若n0表示叶结点的个数、n2是 度为2的非叶结点个数，那么两者满足关系n0 = n2 +1。
  

3、二叉树的抽象数据类型定义

类型名称：二叉树
数据对象集：一个有穷的结点集合。 若不为空，则由根结点和其左、右二叉子树组成。

操作集： BT属于 BinTree, Item 属于ElementType，重要操作有：

1、Boolean IsEmpty( BinTree BT )： 判别BT是否为空；
2、void Traversal( BinTree BT )：遍历，按某顺序访问每个结点；
3、BinTree CreatBinTree( )：创建一个二叉树。

常用遍历方法：

• void PreOrderTraversal( BinTree BT )：先序----根、左子树、右子树
• void InOrderTraversal( BinTree BT )： 中序---左子树、根、右子树
• void PostOrderTraversal( BinTree BT )：后序---左子树、右子树、根
• void LevelOrderTraversal( BinTree BT )：层次遍历，从上到下、从左到右

4、二叉树的存储结构

1. 顺序存储结构 :

2. 链表存储 :