树
1.性质：树中的结点数等于所有结点的度数加1
2.二叉树 ：每个结点最多两个度 左右子树
3.二叉树的性质 ：非空二叉树上的叶子结点树等于度为2的结点数加1
一、逻辑结构：
1.满二叉树 最多结点的二叉树（叶结点一定在最后一层） 每一层都满
2.完全二叉树 结点与满二叉树一一对应
3.二叉排序树 左子树上所有结点关键字均小于该结点，右子树所有结点关键字均大于该 结点
4.平衡二叉树 任意节点的左子树与右子树的深度之差不超过1
二、存储结构：
1.顺序存储 （数组存储）
用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。
逻辑关系的表示 在完全二叉树中，结点i的左子树为2i，右子树为2i+1
对于非完全二叉树，补为结点为空的完全二叉树
顺序存储在最坏的情况下会非常浪费存储空间，比较适合完全二叉树
2.链式存储 （链表存储）
用链表来存放一颗二叉树，二叉树中每个结点用链表的一个链结点来存储
左孩子指针域+数据域+右孩子指d针域
typedef struct BiTnode{
ElemType data;
struct BiTnode *lchild, *rchild;
}BiTnode, *BiTnode;
含有n个结点的二叉链表中，有n+1个空链域
三、二叉树的遍历---按某条路径访问树中的每个结点，树的每个结点均被访问一次，而且只访问一次。
1.先序遍历 根-左-右 （左子树比右子树先访问）
先序遍历--时间复杂度 O（n）
void PreOrder(BiTree T){
if(T!=NULL){ //根结点非空
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
2.中序遍历 左-根-右
中序遍历--时间复杂度 O（n）
void InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}
3.后序遍历 左-右-根
后序遍历--时间复杂度 O（n）
void PostOrder(BiTree T){
if(T!=NULL){
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}
4.中序遍历的非递归算法--借助栈（任何一个递归算法都可以转换为非递归算法）
算法思想：
初始时依次扫描根节点的所有左侧结点并将他们一一进栈；
出栈一个结点，访问它；
扫描该结点的右孩子结点并将其进栈；
依次扫描右孩子结点的所有左侧结点并一一进栈；
反复该过程直到栈空为止。
void InOrder2(BiTree T){
InitStack(s); //初始化
BiTree p=T;
while(p||!IsEmpty(s)){
if(p){ //p非空
push(s,p);
p=p->lchild;
}else{
Pop(s,p);
visit(p);
p=p->rchild;
}
}
}
5.层次遍历--借助队列
算法思想：
初始将根入队并访问根结点；
若有左子树，则将左子树的根入队；
若有右子树，则将右子树的根入队；
然后出队，访问该结点；
反复该过程直到队列为空
void levelOrder(BiTree T){
InitQueue(Q);
BiTree p;
EnQueue(Q,T);
while(!isEmpty(Q)){
DeQueue(Q,p);
visit(p);
if(p->lchild!=NULL)
EnQueue(Q,p->lchild);
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
6.先序/后序遍历序列+中序遍历序列可以确定唯一一棵二叉树
后序+先序不可以确定一棵二叉树
层次+中序可以确定一棵二叉树
四、线索二叉树
1.线索化 若无左子树，则将左指针指向其前驱结点；
若无右子树，则将右指针指向其后继结点。
标志域tag 0 指针域指向孩子结点
1 指针域指向前后结点
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表，线索化的二叉树称为线索二叉树。
2.类型
先序线索二叉树
中序线索二叉树（常用）
后序线索二叉树
3.中序线索二叉树
a)寻找前驱结点的方法
若左指针为线索，则其指向结点为前驱结点
若左指针为左孩子，则其左子树的最右侧结点为前驱结点
b)寻找后继结点的方法
若右指针为线索，则其指向结点为后驱结点
若右指针为右孩子，则其右子树的最左侧结点为后驱结点
c)中序线索二叉树线索化：
void Inthread(ThreadTree &p,ThreadTree &pre){
if(p!=NULL){
Inthread(p->lchild,pre);
if(p->lchild==NULL){
p->lchild=pre;
p->ltag=1;
}
pre=p;
Inthread(p->rchild,pre);
}
}
五、树的存储结构
1.双亲表示法
2.孩子表示法
3.孩子兄弟表示法 二叉表示法 （左孩子右兄弟）
六、树与二叉树的转换
每个结点左指针指向它的第一个孩子结点，右指针指向它在树中相邻兄弟结点。
七、森林与二叉树的转换
将每一棵树转换为二叉树，将每棵二叉树的根依次作为上一棵二叉树的右子树。
八、树和森林的遍历
1.树的遍历
a）先根遍历 树的先根遍历序列与这棵树对应二叉树的先序遍历序列相同
b）后根遍历 树的后根遍历序列与这棵树对应二叉树的中序遍历序列相同
c）层次遍历
2.森林的遍历
a)先序遍历 若非空，则访问第一棵树的根节点，先序遍历第一棵树的子树森林，先序遍历除去第一棵树之后剩余的树构成的子树森林。（树的先根遍历访问每一棵树）--森林的先序遍历与对应二叉树先序遍历相同
b)中序遍历 树的后根遍历访问每一棵树--森林的中序遍历序列与二叉树对应的中序遍历序列相同
九、树的应用
1.并查集 一种简单的集合表示
通常用树的双亲表示法作为并查集的存储结构。
2.二叉排序树 中序遍历序列是一个递增的有序序列 左<根<右
3.平衡二叉树的查找效率是最高的
平均查找长度取决于树的高度
4.平衡二叉树的判断
利用递归的后序遍历过程
a.判断左子树是一平衡二叉树
b.判断右子树是一平衡二叉
c.判断以该结点为根的二叉树为平衡二叉树
判断条件--若左子树和右子树均为平衡二叉树，且左子树与右子树高度差的绝对值小于等于1，则平衡。
5.哈夫曼树---哈夫曼树也称最优二叉树，含有n个带权叶节点带权路径长度最小的二叉树
a）带权路径长度
b）路径长度---边的个数
c）结点的权---结点被赋予的数值
d）树的带权路径长度 ---树中所有叶节点的带权路径长度之和
e）哈夫曼树的构造算法
（1） 将n个结点作为n棵仅含有一个根节点的二叉树，构成森林F；
（2）生成一个新节点，并从F中找出权值最小的两棵树作为左右子树，且新节点的权值为两棵子树之和；
（3） 从F中删除这两个树，并将新生成的树加入到F中
（4） 重复bc步骤，直到F中只有 一棵树为止
6.前缀编码 没有一个编码是另一个编码的前缀