教学目的： 掌握二叉树的两种存储结构
教学重点： 链式存储结构
教学难点： 链式存储二叉树的基本操作
授课内容：
一、复习二叉树的
定义
二叉树的基本特征：每个结点的度不大于２。
二、
顺序存储结构
#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
| 结点编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 结点值 | 1 | 2 | 3 | 4 | 5 | 0 | 0 | 0 | 0 | 6 | 7 | 0 | 0 | 0 | 0 |
第i号结点的左右孩子一定保存在第2i及2i+1号单元中。
缺点：对非完全二叉树而言，浪费存储空间
三、链式存储结构
一个二叉树的结点至少保存三种信息：数据元素、左孩子位置、右孩子位置
对应地，链式存储二叉树的结点至少包含三个域：数据域、左、右指针域。
也可以在结点中加上指向父结点的指针域P。
对结点有二个指针域的存储方式有以下表示方法：
typedef struct BiTNode{
TElemType data;
struct BitNode *lchild,*rchild;
}BiTNode,*BiTree;
基于该存储结构的二叉树基本操作有：
Status CreteBiTree(BiTree &T);
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示的二叉树T。
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
四、总结本课内容
顺序存储与链式存储的优缺点。
