树的定义和相关概念
树的定义：n个结点的有限集合（n>=0），n=0为空树
树的度：树中所有结点的度的最大值
叶子结点（终端结点）：度为0
孩子结点：直接后驱
哦双亲结点：该结点的直接前驱
树的深度（高度）：树中叶子结点所在的最大层次
二叉树：一个结点最多只有两个孩子，左右分区明确
满二叉树：深度为k且含有2^k-1个结点
完全二叉树：深度为k且含有<=2^k-1个结点
满二叉树一定为完全二叉树，完全二叉树不一定为满二叉树
二叉树的存储方式
顺序存储：数组
用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号
数组中下标为i的结点的左孩子下标为2i，右孩子下标为2i+1，双亲结点的下标为i/2
#define MAX 100 //一维数组最多存放100个元素
typedef char datatype;
typedef struct
{
datatype SqBiTree[MAX+1]; //0号单元不用
int nodemax; //数组中最后一个结点的下标
}BiTree;优点：容易查找，用结点的物理次序反映结点之间的逻辑关系
缺点：插入和删除结点时要移动大量的结点，空间浪费严重
仅适用于：完全二叉树和满二叉树
链式存储：二叉链表
每个结点除自身数据外，最多只有两个孩子，所以设计三个域，数据域，左孩子域，右孩子域
typedef datatype char;
typedef struct node
{
datatype data; //数据域
struct node* LChild; //指向左孩子
struct node* RChild; //指向右孩子
}BiTNode，*BiTree;优点：插入、删除灵活 (不必移动节点，只要改变节点中的指针)
缺点：查找结点时链式存储要比顺序存储慢，检索必须沿链进行，不能随机存取
两种存储方式的比较：
1.顺序存储：
分配固定的内存空间
增加/删除结点的时间复杂度为O(n^2)
方便查找结点
2.链式存储：
动态分配内存空间
插入/删除结点的时间复杂度为O(n)
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
二叉树的遍历
将二叉树中的结点按一定规律进行线性化的操作
四种遍历方式：
先序：ＤＬＲ
中序：ＬＤＲ
后序：ＬＲＤ
均是递归定义，在各子树的遍历中，必须按照相应的遍历次序规律对子树的各结点进行遍历
代码balabala...也可以用访问次数来区别：
无论先序、中序、后序，遍历时的搜索路线是相同的：从根节点出发，逆时针延二叉树外缘移动，对每个节点均途经三次。
先序：第一次经过节点时访问。（ABCD）
中序：第二次经过节点时访问。（BADC）
后序：第三次经过节点时访问。（BDCA）
还有一种是层序遍历，一层层节点依次遍历（队列实现）
先序的非递归遍历
判断栈是否为空或子树是否为空，若不为空，就访问左孩子入栈，直至左孩子为空，若左孩子为空，就出栈，然后访问右孩子，入栈，就这样不断的循环。
void PreOrder(BiTree root)
{
SeqStack *s; //创建栈
BiTree p; //保存出栈结点
InitStack(s); //初始化栈
p=root; //定义用来指向当前访问结点的指针
//直到当前结点为ＮＵＬＬ且栈空时结束循环
while(p!=NULL||IsEmpty(s))
{
while(p!=NULL)
{
visit(p->data); //从根结点开始输出当前结点
push(S,p); //将其入栈
//置左孩子为当前结点，直至其没有左孩子及当前结点为NULL
p=p->LChild;
}
if(!IsEmpty(s)
{
//如果当前结点为NULL且栈非空，则将栈顶结点出栈
Pop(S,&p);
//置右孩子为当前结点，循环
p=p->RChild;
}
} 哈夫曼树（最优二叉树）与编码
前缀编码：同一字符集中任何一个字符的编码都不是另一个字符编码的前缀（最左字串）
哈夫曼编码是可以使信息压缩达到最短的二进制前缀编码