5.1 树和二叉树的定义
树（Tree）是n（n≥0）个结点的有限集，它或为空树（n = 0）；或为非空树，对于非空树T：
（1）有且仅有一个称之为根的结点；
（2）除根结点以外的其余结点可分为m（m＞0）个互不相交的有限集T1, T2, …, Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。
二叉树的定义
二叉树（Binary Tree）是n（n≥0）个结点所构成的集合，它或为空树（n = 0）；或为非空树，对于非空树T：
（1）有且仅有一个称之为根的结点；
（2）除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。
为何要重点研究每结点最多只有两个 “叉” 的树？
二叉树的结构最简单，规律性最强；
可以证明，所有树都能转为唯一对应的二叉树，不失一般性。
5.2 案例引入
无
5.3 树和二叉树的抽象数据类型定义
CreateBiTree(&T,definition)
初始条件；definition给出二叉树T的定义。
操作结果：按definition构造二叉树T。
PreOrderTraverse(T)
初始条件：二叉树T存在。
操作结果：先序遍历T，对每个结点访问一次。
InOrderTraverse(T)
初始条件：二叉树T存在。
操作结果：中序遍历T，对每个结点访问一次。
PostOrderTraverse(T)
初始条件：二叉树T存在。
操作结果：后序遍历T，对每个结点访问一次。
5.4 二叉树的性质和存储结构
满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。
二叉树的顺序存储
实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。
二叉树的链式存储
typedef struct BiNode{
TElemType data;
struct BiNode *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree;
typedef struct TriTNode
{ TelemType data;
struct TriTNode *lchild,*parent,*rchild;
}TriTNode,*TriTree;
5.5 遍历二叉树和线索二叉树
遍历定义——指按某条搜索路线遍访每个结点且不重复（又称周游）。
遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。
遍历规则
口诀：
DLR—先序遍历，即先根再左再右
LDR—中序遍历，即先左再根再右
LRD—后序遍历，即先左再右再根
先序遍历算法
Status PreOrderTraverse(BiTree T){
if(T==NULL) return OK; //空二叉树
else{
cout<<T->data; //访问根结点
PreOrderTraverse(T->lchild); //递归遍历左子树
PreOrderTraverse(T->rchild); //递归遍历右子树
}
}
中序遍历算法
Status InOrderTraverse(BiTree T){
if(T==NULL) return OK; //空二叉树
else{
InOrderTraverse(T->lchild); //递归遍历左子树
cout<<T->data; //访问根结点
InOrderTraverse(T->rchild); //递归遍历右子树
}
}
后序遍历算法
Status PostOrderTraverse(BiTree T){
if(T==NULL) return OK; //空二叉树
else{
PostOrderTraverse(T->lchild); //递归遍历左子树
PostOrderTraverse(T->rchild); //递归遍历右子树
cout<<T->data; //访问根结点
}
}
时间效率:O(n) //每个结点只访问一次
空间效率:O(n) //栈占用的最大辅助空间
二叉树的建立
void CreateBiTree(BiTree &T）{
cin>>ch;
if (ch==’#’) T=NULL; //递归结束，建空树
else{
T=new BiTNode; T-＞data=ch; //生成根结点
CreateBiTree(T-＞lchild); //递归创建左子树
CreateBiTree(T-＞rchild); //递归创建右子树
}
}
二叉树遍历算法的应用
int NodeCount(BiTree T){
if(T == NULL ) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int LeadCount(BiTree T){
if(T==NULL) //如果是空树返回0
return 0;
if (T->lchild == NULL && T->rchild == NULL)
return 1; //如果是叶子结点返回1
else return LeadCount(T->lchild) + LeadCount(T->rchild);
}
二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？
——可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。
线索化二叉树
先序线索二叉树
中序线索二叉树
后序线索二叉树
5.6 树和森林
树的存储结构－－二叉链表表示法
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
树和森林的转换。。。
5.7 哈夫曼树及其应用
。。。。。