一、树的基本概念
- 结点的度(degree)：结点拥有的子树数。
- 分支结点：度不为0的结点。
- 树的度：一棵树中各结点的度的最大值。
- 双亲(parents)：孩子结点的上层结点。
- 祖先：从根结点到该结点所经分支上的所有结点。
- 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。
- 结点的层次(level)：从根结点算起，根为第一层，根的孩子为第二层……。
- 堂兄弟：其双亲在同一层的结点互为堂兄弟。
- 深度(depth)：树中结点的最大层次。
- 有序树：将树中结点的各子树看成从左至右是有次序的，即不能互换。
- 无序树：将树中结点的各子树看成从左至右是无次序的，即可以互换。
二、二叉树
1、二叉树的性质
函数catalan():给定n个结点，能构成h(n)种不同的二叉树,h(n)=C(2n,n)/(n+1)
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。
在满二叉树中，叶节点的个数比分支结点的个数多1
完全二叉树:在最后一层，并不是所有节点都有两个子节点,最后一层所有的结点都连续集中在最左边。
具有n个结点的完全二叉树的深度是
2、二叉树的存储结构
2.1、顺序存储结构
#define MAXSIZE 100
typedef TElemType SqBiTree[MAXSIZE];
SqBiTree bt;二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。即用一维数组存储二叉树中的结点。用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适。一棵完全二叉树（满二叉树）如下图所示：
将这棵二叉树存入到数组中，相应的下标对应其同样的位置，如下图所示：
但是对于一般的非完全二叉树来说，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中，不存在的结点用NULL代替。
2.2、链式存储结构
二叉树的链式存储结构是指用链表来表示一棵二叉树。 二叉树的每个结点最多有两个孩子，因此，每个结点除了存储自身的数据外，还应设置两个指针分别指向左、右孩子结点。结点结构如下图所示：
typedef struct BiTNode{
TElemType data;
Struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;3、遍历二叉树
3.1、 二叉树的遍历方式
二叉树的遍历方式主要有先序遍历、中序遍历、后序遍历和层次遍历。
先序遍历
void PreOrderTraverse(BiTree T){
if(T){
printf("%c",T->data);//显示结点数据，可以更改为其他对结点的操作
PreOrderTraverse(T->lchild);//再先序遍历左子树
PreOrderTraverse(T->rchild)；//最后先序遍历右子树
}
}中序遍历和后序遍历同理。
层次遍历
>基本思想：从第一层开始，依此遍历每层，直到结束。
3.2、根据遍历序列确定二叉树
由二叉树的先序序列和中序序列、或由其后序序列和中序序列均能唯一地确定一棵二叉树。
根据定义，二叉树的先序遍历是先访问根结点，其次再按先序遍历方式遍历根结点的左子树，最后按先序遍历方式遍历根结点的右子树。也就是说，在先序序列中，第一个结点一定是二叉树的根结点。另一方面中序遍历是先遍历左子树，然后访问根结点，最后再遍历右子树。这样根结点在中序序列中必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是是根结点的右子树的中序序列。根据两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子树的第一个结点是右子树的根结点。这样就确定了二叉树的三个结点。同时，左子树和右子树的根结点又可以将左子序列和右子序列划分成两个子序列，如此递归下去，当取尽先序序列中的结点时，便可以得到一棵二叉树。
同理，由二叉树的后序序列和中序序列也可以唯一确定一棵二叉树。因为，依据后序遍历和中序遍历的定义，后序序列的最后一个结点，就如同先序序列的第一个结点一样，可将中序序列分为两个子序列，分别为这个结点左子树的中序序列和右子树的中序序列，后面的思想同上。
3.3、二叉树遍历的应用
（1）求表达式的值
int comp(BTNode *p)
{
int A,B;
if(p==NULL)
return 0;
else{
if(p->lchild!=NULL&&p->rchild!=NULL)
{
A=comp(p->lchild);
B=comp(p->rchild);
return op(A,B,p->data);
}
else
return p->data-'0';
}
}
//说明：函数int op(int A,int B,char C)返回的是以C为运算符，以A、B为操作数的算术的数值（2）、求二叉树的深度
算法步骤：
如果是空树，递归结束，深度为0，否则执行以下操作：
- 递归计算左子树的深度为m
- 递归计算右子树的深度为n
- 如果m大于n，二叉树的深度为m+1，否则为n+1
int Depth(BiTree T){
if(T==NULL)
return 0; //如果是空树，深度为0，递归结束
else
{
m = Depth(T->lchild);
n = Depth(T->rchild);
if(m>n)
return m+1;
else
return n+1;
}
}（3）、 交换左右子树
void Exchange(BiTree T)
{
BiTree temp;
if(T)
{
Exchange1(T->lchild);
Exchange1(T->rchild);
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
}
} （4）判断两棵树是否等价
int Is_equal( BiTree T1 , BiTree T2 )
{
int t=0;
if(NULL == T1 && NULL == T2)
{
t=1;
}
else
{
if(NULL !=T1 &&NULL != T2 )
{
if(T1->data == T2->data)
{
if(Is_equal(T1->lchild,T2->lchild))
{
t=Is_equal(T1->rchild,T2->rchild);
}
}
}
}
return t;
} （5）统计二叉树中叶子结点的数目
int NodeCount(BiTree T){
if (T==NULL)
{
return 0; //如果是空树，则结点个数为0，递归结束
}else
{
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
//否则结点个数为左子树结点个数+右子树结点个数+1
}
}（6）先序遍历的顺序建立二叉链表
算法步骤：
- 扫描字符序列，读入数字ch
- 如果ch是一个#字符，则表明该二叉树为空树，即T为NULL;否则执行以下操作：
（1）申请一个结点空间T
（2）将ch赋给T->data
（3）递归创建T的左子树
（4）递归创建T的右子树
void CreateBiTree(BiTree &T){
cin>>ch;
if(ch == '#') T=NULL;
else {
T = new BiTNode;
T->data = ch;
CreateBiTree(T->Lchild);
CreateBiTree(T->Rchild);
}（7） 复制二叉树
void copy(BiTree T,BiTree &NewT){
if(T==NULL){
NewT = NULL; //如果是空树，递归结束
return;
}else
{
NewT = new BiTNode;
NewT->data = T->data; //复制根结点
copy(T->lchild,NewT->lchild); //递归复制左子树
copy(T->rchild,NewT->rchild); //递归复制右子树
}
}3.4、非递归方式实现遍历算法
（1）先序遍历非递归算法
由此可以写出以下代码：
（2）中序遍历非递归算法
遍历序列为3，2，5，1，4
由以上步骤看出，中序非递归遍历过程如下：
4、线索二叉树
4.1、线索二叉树的原理
4.2、中序线索二叉树的构造
记ptr指向二叉链表中的一个结点，以下是建立线索的规则：
显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，结点结构如下所示。
对应的线索二叉树存储结构定义如下：
typedef struct BiThrNode{
char data;
int ltag,rtag;//线索标记
struct BiThrNode *lchild;
struct BiThrNode *rchild;
}BiThrNode,*BiThrTree;线索二叉树可以分为前序线索二叉树、中序线索二叉树和后序线索二叉树。对一棵二叉树中所有结点的空指针域按照某种遍历方式加线索的过程叫做线索化，被线索化了的二叉树称为线索二叉树。下图为中序线索二叉树及其二叉链表表示。
5、树和森林
5.1、树的存储结构
树的存储结构分为顺序存储结构与链式存储结构，其中又可分为三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。
双亲表示法
孩子表示法
与双亲表示法相反，孩子表示法便于对孩子的操作。可以把双亲表示法与孩子表示法结合起来，如下图：
孩子兄弟表示法
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;
6、树和森林与二叉树的转换
6.1、树转换为二叉树
6.2、森林转换为二叉树
6.3、二叉树转换为树
6.4、二叉树转换为森林
7、树和森林的遍历
7.1、树的遍历
- 先根遍历:若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树。
- 后根遍历:若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点。
先根遍历的结果为ABEFCGDHIJ
后根遍历的结果为EFBGCHIJDA
7.2、森林的遍历
三、 赫夫曼树及其应用
1、与赫夫曼树相关的一些概念
2、赫夫曼树的构造方法
3、赫夫曼编码
在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：
（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；
（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。
3.1、等长编码
这种编码方式的特点是每个字符的编码长度相同。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。
3.2、不等长编码
在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。
因此，为了设计长短不等的编码，以便减少电文的总长，还必须考虑编码的唯一性，即在建立不等长编码时必须使任何一个字符的编码都不是另一个字符的前缀，这种编码称为前缀编码（prefix code）
3.3、前缀编码和哈夫曼编码
（1）前缀编码
(2)哈夫曼编码
- 目标：使电文总长最短。
- 以字符出现的次数为权，构造一棵赫夫曼树；将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列，这样得到的编码称为哈夫码编码。
- 哈夫曼编码为前缀编码。
- 以这组编码传送电文可使电文总长最短(对所有其它前缀编码而言)。
例题：假设一个文本文件TFile中只包含7个字符{A，B，C，D，E，F，G}，这7个字符在文本中出现的次数为{5，24，7，17，34，5，13}利用哈夫曼树可以为文件TFile构造出符合前缀编码要求的不等长编码