树是一种一对多的逻辑结构，树的子树之间没有关系。
度：结点拥有的子树数量。
树的度：树中所有结点的度的最大值。
结点的深度：从根开始，自顶向下计数。
结点的高度：从叶结点开始，自底向上计数。
树的性质：①树的结点数等于所有结点的度数加1；②度为m的树中第i层上至多有mi-1个结点（i>=1）；③度为h的m叉数至多有(mh-1)/(m-1)个结点；④具有n个结点的m叉树的最小高度为[logm(n(m-1)+1)]。
树的表示方法：
①双亲表示法（顺序表示法）：根节点parent=-1
typedef char ElemType;
typedef struct TNode{
ElemType data; //结点数据
int parent; //该结点双亲在数组中的下标
}TNode; //结点数据类型
#define MaxSize 50
typedef struct{
TNode nodes[MaxSize]; //结点数组
int n; //结点数量
}Tree; //树的双亲表示结构
②孩子表示法：把每个孩子的孩子结点排列起来存储成一个单链表，n个结点就有n个单链表，n个单链表的头指针又存储在一个顺序表（数组）中
typedef char ElemType;
typedef struct CNode{
int child; //该孩子在表头数组的下标
struct CNode *next; //指向该结点的下一个孩子结点
}CNode,*Child; //孩子结点数据类型
typedef struct{
ElemType data; //结点数据域
Child firstchild; //指向该结点的第一个孩子结点
}TNode; //孩子结点数据类型
#define MaxSize 100
typedef struct{
TNode nodes[MaxSize]; //结点数据域
int n; //树中的结点个数
}Tree; //树的孩子表示结构
③孩子兄弟表示法：分别指向孩子结点和兄弟结点，其结点结构为：
typedef char ElemType;
typedef struct CSNode{
ElemType data; //该结点的数据域
struct CSNode *firstchild,*rightsib; //指向该结点的第一个孩子结点和该结点的右兄弟结点
}CSNode; //孩子兄弟结点数据类型
二叉树：①每个结点最多有两棵子树；②左右子树有顺序。
二叉树的种类：①斜二叉树；②满二叉树；③完全二叉树。
满二叉树是绝对的等腰三角形，每一个非叶子结点都有两个子树，而完全二叉树的结点个数随意，只需满足其层序遍历的序号与满二叉树相同即可。
二叉树的顺序存储：用一组地址连续的存储单元依次自上向下，自左至右存储完全二叉树上的结点元素，非完全二叉树需在对应空缺编号处保留数组空位，这是一种极其浪费的存储方式。
二叉树的链式存储：
①二叉链表：两个指针指向左右孩子结点。其实现为：
typedef struct BiTNode{
ELemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
②三叉链表：在二叉链表的基础上添加一个指针指向双亲。
二叉树的遍历：按某种次序依次访问树中的每个结点，使得每个结点均被访问人一次，而且仅被访问一次。
有以下四种方法：
①先序遍历：a.访问根节点；b.先序遍历左子树；c.先序遍历右子树。
递归实现：
void PreOrder(BiTree T){
if(T!=NULL){
printf("%c",T->data); //访问根节点
PreOrder(T->lchild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}
非递归实现：在实现过程中利用了栈的思想
void PreOrder(BiTree b){
InitStack(s);
BiTree p=b; //工作指针p
while(p||!IsEmpty(s)){
while(p){
printf("%c",p->data);
Push(s,p); //进栈
p=p->lchild;
}
if(!IsEmpty(s)){
p=P0p(s);
p=p->rchild;
}
}
}
②中序遍历：a.中序遍历左子树；b.访问根节点；c.中序遍历右子树。
递归实现：
void InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild); //递归遍历左子树
printf("%c",T->data); //访问根节点
InOrder(T->rchild); //递归遍历右子树
}
}
非递归实现：
void InOrder(BiTree b){
InitStack(s);
BiTree p=b;
while(p||!IsEmpty(s)){
while(p){
Push(s,p);
p=p->lchild;
}
p=Pop(s);
printf("%c",p->data);
p=p->rchild;
}
}
③后序遍历：a.后序遍历左子树；b.后序遍历右子树；c.访问根节点。
递归实现：
void PostOrder(BiTree T){
if(T!=NULL){
PostOrder(T->lchild); //递归遍历左子树
PostOrder(T->rchild); //递归遍历右子树
printf("%c",T->data); //访问根节点
}
}
非递归实现：
void PostOrder(BiTree b){
InitStack(s);
BiTree p=b,r=NULL; //工作指针p，辅助指针r
while(p||!IsEmpty(s)){ //从根节点到最左下角的左子树都入栈
if(p){
Push(s,p);
p=p->lchild;
}
else{
GetTop(s,p); //取栈顶，不是出栈
if(p->rchild&&p->rchild!=r) //如果栈顶存在右子树且未被访问过，就去访问
p=p->rchild;
else{ //不存在右子树或者被访问过，则出栈
Pop(s,p);
printf("%c",p->data);
r=p;
p=NULL;
}
}
}
}
④层序遍历：从上向下逐层遍历，在同一层中，从左到右对结点逐个访问。
层序遍历没有递归实现，只有非递归实现：其采用了队列的思想
void LevelOrder(BiTree b){
InitQueue(Q);
BiTree p;
EnQueue(Q,b); //根结点入队
while(!IsEmpty(Q)){ //队列不空循环
DeQueue(Q,p) //队头元素出队
printf("%c",p->data);
if(p->lchild!=NULL)
EnQueue(Q,p->lchild);
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
如何将一棵树转化成二叉树：①将同一结点的各个孩子用线串起来；②将每个结点的子树分支，从左往右，除了第一个以外全部删除。
将二叉树转化成树：将二叉树从上到下分层，并调节成水平方向，之后是正向转化的逆过程。
一个重要结论：n个结点的二叉链表，每一个结点都有指向左右孩子的结点指针，所以一共有2n个指针，而n个结点的二叉树一共有n-1条分支，也就是存在2n-(n-1)=n+1个空指针。
线索二叉树：指向前驱和后继的指针称为线索，加上线索的二叉链表就称为线索链表，相应的二叉树就称为线索二叉树。对二叉树以某种次序遍历使其变成线索二叉树的过程叫作线索化。
下面我们以中序遍历作为例子，实现线索二叉树，并对其遍历：
线索二叉树的实现：
typedef struct ThreadTNode{
ELemType data;
struct ThreadTNode *lchild,*rchild;
int ltag,rtag; //tag=0指向孩子，tag=1指向前驱或者后继
}ThreadTNode,*ThreadTree;
void InThread(ThreadTree &p,ThreadTree &pre){
//pre指向中序遍历时上一个刚刚访问过的结点，初值为NULL
if(p){
InThread(p->lchild,pre);
if(p->lchild==NULL){
p->lchild=pre;
p->ltag=;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild=p;
pre->rtag=;
}
pre=p;
InThread(p->rchild,pre);
}
}
对线索二叉树进行中序遍历：
void InOrderTraverse(ThreadTree T){
ThreadTree p=T;
while(p){
while(p->ltag==) p=p->lchild;
printf("%c",p->data);
while(p->ltag==&&p->rchild){
p=p->rchild;
printf("%c",p->data);
}
p->rchild;
}
}
哈夫曼树中相关概念：
权：树中结点相关的数值；
路径长度：从树中某个结点到另一个结点之间的分支数目（经过的边数）；
带权路径长度：从树的根结点到任意结点的路径长度与该结点权值的乘积；
树的带权路径长度：树中所有结点带权路径长度的和。
哈夫曼树的定义：含有n个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树，也称为最优二叉树。