先去看视频的笔记[树]（https://www.jianshu.com/p/551f7c111207
）
1.定义
树是n(n>= 0)个节点的有限集，n = 0时称为空树，在任意一颗非空树中：（1）有且仅有一个特定的称为根的节点
（2）当n > 1时，其余结点可分为m(m> 0)个互不相交的有限集T1、T2、 ..... Tm，其中每一个集合本身又是一棵树，并且称为根的子树
2.二叉树的性质
2.1在二叉树的第i层至多有2的i - 1次方个结点
2.2深度为k的二叉树至多有2的k次方 -1个结点
2.3对任意一棵二叉树T,如果其终端结点数为n0,度为2的节点数为n2,则n0 = n2+1。
2.4具有n个结点的完全二叉树的深度为[log 2 n] + 1;
2.5如果对一棵有n个结点的完全二叉树（其深度为[log 2 n] + 1）的结点按层序编号（从第一次到第[log 2 n] + 1层，每层从左到右），对任一结点 i ，（1<= i <= n）有
2.5.1如果i = 1,则结点i 是二叉树的根，无双亲,如果i > 1,则其双亲是结点 [i / 2]
2.5.2如果 2i > n,则结点i 无左孩子（结点i 为叶子结点）；否则其左孩子是结点2i;
2.5.3 如果 2i+ 1 > n,则结点i 无右孩子，否则其右孩子是结点2i + 1;
3二叉树的建立
/* 按前序输入二叉树中结点的值（一个字符) #表示空树，构造二叉链表表示二叉树T*/
void CreateBiTree(BiTree *T){
TElemType ch;
scanf("%c",&ch);
if(ch == '#')
*T = NULL;
else{
*T = (BiTree) malloc(sizeof(BiTNode));
if(!*T)
exit(-1);
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
4.线索二叉树
我们把指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树
实现
typedef enum {Link,Thread} PointerTag; //当Link == 0时表示指向左右孩子指针
//Thread == 1 表示指向前驱或后继的线索
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild,*rchild;
PointerTag LTag;
PointerTag RTag;
}BiThrNode,*BiThrTree;
中序遍历进行中序线索化
BiThrTree pre;// 全局变量 ，始终指向刚刚访过的结点
void InThreading(BiThrTree p){
if(p){
InThreading(p->lchild);
if(!p->lchild){
p->LTag = Thread;
p->lchild = pre;
}
if(!pre -> rchild){
pre->RTag = Thread;
pre->rchild = p;
}
pre = p;
InThreading(p->rchild);
}
}
遍历代码
/* T指向头结点，头结点左链lchild 指向根结点，头结点右链rchild指向中序遍历的*/
// 最后一个结点，中序遍历二叉线索链表表示的二叉树T
Status InOrderTraverse_Thr(BiThrTree T){
BiThrTree p;
p = T->lchild; // p 指向根结点
while(p != T){ // 空树或遍历结束时，p == T
while(p->LTag == Link) // 当LTag == 0时循环到中序序列第一个结点
p = p ->lchild;
printf("%c",p->data);
while(p->RTag == Thread && p->rchild != T){
p = p->rchild;
printf("%c",p->data);
}
p = p->rchild;
}
return OK;
}
5.树、森林与二叉树的转换
5.1 树转换为二叉树步骤
5.1.1加线，在所有兄弟结点加一条连线
5.1.2去线，对树中每一个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线
5.1.3层次调整，以树的根节点为轴心，将整棵树顺时针旋转一定角度，使之结构分明（其实就是把它摊开）
5.2森林转换为二叉树
5.2.1把每棵树转换为二叉树
5.2.2第一棵树不动，从第二棵二叉树开始，依次把后一棵树的根节点作为前一棵树的根节点的右节点，用线连接起来后就是二叉树
]
5.3二叉树转换为树
5.3.1加线，就是左孩子的n个右孩子结点都作为此节点的孩子，用线连接起来
5.3.2去线，删除原二叉树中国所有结点与其右孩子结点的连线
5.3.3层次调整
5.4二叉树转换为森林
5.4.1 从根节点开始，若右孩子存在，则把与右孩子结点的连线删除，在查看分离后的二叉树，若右孩子存在，则连线删除
5.4.2再将每棵分离后的二叉树转换为树即可!!
6树和森林的遍历
6.1树的遍历
1.先根遍历树，先访问树的根结点，然后依次先先根遍历根的每棵子树（二叉树的前序遍历）
2.后根遍历，（二叉树的中序遍历）
6.2森林的遍历
1.前序遍历：（二叉树的前序遍历）
2.后序遍历：（二叉树的中序遍历）
7赫夫曼树及其应用
带权路径长度WPL最小的二叉树称为赫夫曼树
权：即为百分比
应用：用于压缩，通过重新编码，减少占用的存储空间
