1.定义
一个有穷的结点集合。
这个集合可以为空 若不为空，则它是由根结点和称为其左子树TL和右子树TR的
两个不相交的二叉树组成。
2.特点
二叉树具体五种基本形态
二叉树的子树有左右顺序之分
3.特殊的二叉树
- 二叉树的几个重要性质
- 一个二叉树第 i 层的最大结点数为:2 (i-1)，i >= 1。
- 深度为k的二叉树有最大结点总数为: 2 (k) -1，k >= 1。
- 对任何非空二叉树 T，若n0表示叶结点的个数、n2是 度为2的非叶结点个数，那么两者满足关系n0 = n2 +1。
- 二叉树的的抽象数据类型定义
类型名称:二叉树
数据对象集:一个有穷的结点集合。若不为空，则由根结点和其左、右二叉子树组成。
操作集: BT BinTree, Item ElementType，重要操作有:
1、Boolean IsEmpty( BinTree BT ): 判别BT是否为空;
2、void Traversal( BinTree BT ):遍历，按某顺序访问每个结点;
3、BinTree CreatBinTree( ):创建一个二叉树。
6.常用的遍历方法有:
void PreOrderTraversal( BinTree BT ):先序----根、左子树、右子树;
void InOrderTraversal( BinTree BT ): 中序---左子树、根、右子树;
void PostOrderTraversal( BinTree BT ):后序---左子树、右子树、根
void LevelOrderTraversal( BinTree BT ):层次遍历，从上到下、从左到右
7.二叉树的存储结构
1.顺序存储结构
完全二叉树可以用数组来存储。
按从上至下、从左到右顺序存储n个结点的完全二叉树的结点父子关系
2.链表存储
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode{
ElementType Data;
BinTree Left;
BinTree Right;
}
