二叉树的定义
二叉树T：一个有穷的结点集合。
- 这个集合可以为空
- 若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
二叉树具体五种基本形态：
- 空二叉树；
- 只有根结点的二叉树；
- 只有根结点和左子树TL的二叉树；
- 只有根结点和右子树TR的二叉树；
- 具有根结点、左子树TL和右子树TR的二叉树。
二叉树的子树有左右顺序之分
几种特殊的二叉树
- 斜二叉树(Skewed Binary Tree)、退化二叉树
- 一条线的形状
- 完美二叉树(Perfect Binary Tree) / 满二叉树(Full Binary Tree）
- 所有子节点都是满的
- 完全二叉树(Complete Binary Tree)
- 子节点不一定满，但是从上到下，从左到右和满二叉树相同
几个重要性质
- 一个二叉树第 i 层的最大结点数为：\(2^{i-1}\) (\(i \ge 1\))
- 深度为k的二叉树有最大结点总数为： \(2^k - 1\) (\(k \ge 1\))
- 对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系 \(n0 = n2 +1\)
抽象数据类型定义
类型名称：二叉树
数据对象集：一个有穷的结点集合。
若不为空，则由根结点和其左、右二叉子树组成。
操作集： BT ∈ BinTree, Item ∈ ElementType，重要操作有：
- BinTree CreatBinTree( )：创建一个二叉树
- Boolean IsEmpty( BinTree BT )： 判别BT是否为空
- void Traversal( BinTree BT )：遍历，按某顺序访问每个结点
四种常用的遍历方法：
- void PreOrderTraversal( BinTree BT )：先序----根、左子树、右子树；
- void InOrderTraversal( BinTree BT )： 中序---左子树、根、右子树；
- void PostOrderTraversal( BinTree BT )：后序---左子树、右子树、根
- void LevelOrderTraversal( BinTree BT )：层次遍历，从上到下、从左到右
存储结构
顺序存储结构
按从上至下、从左到右顺序存储，适合完全二叉树，一般二叉树也可以采用这种结构，但会造成空间浪费
n个结点的完全二叉树的结点父子关系：
- 非根结点（序号 i > 1）的父结点的序号是 i/2
- 结点（序号为 i ）的左孩子结点的序号是 2i， （若 \(2*i \le n\)，说明有左孩子）;
- 结点（序号为 i ）的右孩子结点的序号是 2i+1， （若 \(2*i+1 \le n\)，说明有右孩子）;
链表存储
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode {
ElementType Data;
BinTree Left;
BinTree Right;
}