树和二叉树
树形结构是一种重要的非线性数据结构，只管来看树是以分支关系定义的层次结构，本文主要介绍二叉树存储结构及其各种操作。
树的定义和基本术语
树（Tree）是n个结点的有限集，在任意一颗非空树中有且仅有一个特定的节点称为根（Root）。当n>1时其他节点可以分为m个互不相交的有限集，其每个集合都是一颗树称为根的子树。树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（Degree），度为零的结点称为叶子（leaf）也称为终端结点。结点的子树的根称为该结点的孩子，相应的结点被称为孩子的双亲，同一个双亲的孩子之间互相称为兄弟。结点的层次从根开始定义，根为第一层，根的孩子称为第二层，树中结点的最大层次称为树的深度（Depth）。森林（Forest）是m棵互不相交的树的集合。对树的集合。对书的每个结点而言其子树的集合即为森林。
二叉树
二叉树是个好i另一种树形结构，它的特点是每个结点之多只有两颗子树（即二叉树中的不存在度大与二的结点），并且二叉树的子树有左右之分，其次序不能相互颠倒。 因为二叉树的结构特性二叉树具有以下特征：
1.在二叉树的第i层上至多a^{i-1}次方个节点。 2.在深度为k的二叉树之多有2的k次方-1个结点。 3.对任何一颗二叉树T，若其终端节点数为n0，度为2的结点数为n2，则n0 = n2 + 1。 4.具有n个节点的完全二叉树深度为[log^{n}{2}] + 1 5.如果一棵树有n个节点的完全二叉树其深度为[log^{n}{2}]+1，的结点按层序号从一层到[log^{n}_{2}]+1层（每层从左到右），则对任一节点有： （1）如果i=1，则结点i是二叉树的根，无双亲，如果i>1，则双亲是结点[i/2]。 （2）如果2i>n，则结点i无左孩子，否则左孩子是结点2i。 （3）如果2i+1>n，则结点i无右孩子，否则有孩子结点是2i+1。
二叉树的存储结构
存储结构类似单链表相似，但后继不唯一，有左右孩子结点，用链式结构存储，下面是存储结构：
typedef int ElemType; //数据类型
//定义二叉树结构，与单链表相似，多了一个右孩子结点
typedef struct BiTNode{
ElemType data; //数据域
struct BiTNode *lChild, *rChlid; //左右子树域
}BiTNode, *BiTree;
遍历二叉树
在二叉树的的一个重要应用，常常要求在树中查找具有某种特征的结点，或者对树中全部节点逐一进行某种处理。这就提出了遍历二叉树，及如何按照某条搜索路径访问树中的每个节点遍历线性结构是一种，非线性结构，因而需要寻找一种规律。
先序遍历：访问根结点，先序遍历左子树，先序遍历右子树。 下面说明先序遍历：
//先序遍历二叉树
void TraverseBiTree(BiTree T)
{
if (T == NULL)
return ;
printf("%d ", T->data);
TraverseBiTree(T->lChild);
TraverseBiTree(T->rChlid);
}
中序遍历：先遍历左子树，访问根结点，遍历右子树
下面说明中序遍历：
//中序遍历二叉树
void InOrderBiTree(BiTree T)
{
if (T == NULL)
return ;
InOrderBiTree(T->lChild);
printf("%d ", T->data);
InOrderBiTree(T->rChlid);
}
后序遍历：先遍历左子树，再遍历右子树，再访问根结点。
//后序遍历二叉树 void PostOrderBiTree(BiTree T) { if (T == NULL) return ; PostOrderBiTree(T->lChild); PostOrderBiTree(T->rChlid); printf("%d ", T->data); }以上就是遍历树的三种方式。在每次遍历是都是采用递归的方式，并不是简单的按照顺序访问。
先序创建链表
创建链表也是个困难的问题，同样是采用遍历的方式进行创建二叉树，首先接受一个数据，为二叉树的root结点分配内存，把数据存放到root结点的数据域，采用先序的方式（其他顺序也可以）递归创建左子节点和右子节点，完成创建，下面说明先序创建链表的：
//先序创建二叉树
void CreateBiTree(BiTree *T)
{
ElemType ch;
scanf("%d", &ch);
if (ch == -1)
*T = NULL;
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
if (!(*T))
exit(-1);
(*T)->data = ch;
printf("输入%d的左子节点：", ch);
CreateBiTree(&(*T)->lChild);
printf("输入%d的右子节点：", ch);
CreateBiTree(&(*T)->rChlid);
}
}
求二叉树的深度
上文说过二叉树的深度就是树中结点的最大层次称为树的深度，因此采用递归的方式分别判断左右子树的深度，进行比较返回较大值，通过递归+1，最终求得二叉树的深度，下面说明二叉树的深度：
int TreeDeep(BiTree T)
{
int deep = 0;
if(T)
{
int leftdeep = TreeDeep(T->lChild);
int rightdeep = TreeDeep(T->rChlid);
deep = leftdeep>=rightdeep?leftdeep+1:rightdeep+1;
}
return deep;
}
求二叉树叶子结点个数
通过定义可知，叶子就是没有左右子树的结点，通过，通过遍历整个二叉树，寻找没有左右子树的结点，球的二叉树叶子结点的个数，下面说明求二叉树叶子结点的个数：
int Leafcount(BiTree T,int num)
{
if(T){
if(T->lChild ==NULL &&T->rChlid==NULL)
num++;
Leafcount(T->lChild,num);
Leafcount(T->rChlid,num);
}
return num;
}
下面放上整个代码： 二叉树
线索二叉树
遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，这实质上是对一个非线性结构进行了线性化操作，使每个结点（除了第一个和最后一个）在线性序列中只有一个前驱和一个后继。当我们在以二叉链表树作为存储结构的时候，对于每一个节点只能找到左右孩子的信息，不能得到节点在任一序列中的前驱和后继信息，这个信息只能通过便利得到，但我们在每个节点上增加两个指针域饭别表示节点的前驱和后继，但这样会浪费很多的内存空间，因此用叶子结点空的左子树存放前驱，空的右子树节点存放后继。
线索二叉树结点结构
在最基本的链表二叉树结构上增加左右两个标志，每个标志设置两种状态,有孩子结点，和无孩子结点。因此我们还需设置一个枚举类型存储标志的状态。我来简单介绍一下枚举类型：
在C中定义了一种特殊的数据类型：枚举。有点类似于结构体，但每个元素都是整形，枚举的好处在于它可以使一些数字符号化，然后增强程序的可读性。当然使用宏定义也是可以哒。 enum 枚举类型的名字{a,b,c}这就是枚举的格式，注意枚举中的那些a之类的符号并不是真正意义上的符号，而是整形。若果没有初始化，按照顺序自动0-n，输出和输入枚举类型的时候都需要按照整形来处理。
这里我们用0和1的枚举类型表示有孩子节点，和无孩子节点，下面说明二叉树结点的结构：
//线索存储标志位
//link(0)： 指向左右孩子 | 表示当前结点的左指针(*lchild)或右指针(*rchild) 指向对应的左或右孩子
//Thread(1): 指向前驱后继线索 | 表示当前结点的左指针(*lchild)或右指针(*rchild) 指向对应的前驱或后继元素
typedef enum
{
Link, //link=0,
Thread //Thread=1
}PointerTag;
//BinaryThreadTree Node 线索二叉树结点结构
typedef struct BiThrNode
{
ElemType data;
struct BiThrNode *lchild, *rchild;
PointerTag ltag;
PointerTag rtag;
}BiThrNode, *BiThrTree; //*BiThrTree: 指向结点的指针为树
创建二叉树
创建二叉树时并不能实现线索化，所以创建二叉树和以前一样，只是在初始化的时候标志位赋初值，默认所有结点有左右孩子。下面说明创建二叉树：
//创建一颗二叉树，约定用户遵照前序遍历方式输入数据
void CreateBiThrTree(BiThrTree *T) //BiThrTree *T: T为指向树的指针 | 二级指针
{
ElemType c;
scanf("%c", &c);
if (' ' == c)
{
*T = NULL;
}
else
{
*T = (BiThrNode*)malloc(sizeof(BiThrNode));
(*T)->data = c;
(*T)->ltag = Link; //标志位赋初值，默认所有结点有左右孩子
(*T)->rtag = Link;
CreateBiThrTree(&(*T)->lchild); //递归法为左右子节点赋值
CreateBiThrTree(&(*T)->rchild);
}
}
中续遍历线索化
中序遍历线索化二叉树需要一个二叉树结点指针，指向访问过的结点，这样就可以方便操作链接前驱和后继。 建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一颗二叉树。在遍历过程中，访问结点的场所是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。
//全局变量 始终指向刚刚访问过的结点
BiThrTree pre; //前一个结点/头结点指针
不同的顺序遍历二叉树,自然会生成不同的线索二叉树，这里用中续来实现线索化二叉树，下面说明线索化二叉树：
//中序遍历线索化 | 改变无左或右孩子结点的tag标志位，使其指向前驱或后继(形成首尾相连的双向链表)
void InThreading(BiThrTree T)
{
if (T) //若不为空树
{
InThreading(T->lchild); //递归左孩子线索化
if (!T->lchild) //若该结点没有左孩子，设置Tag为Thread
{
T->ltag = Thread;
T->lchild = pre;
}
if (!pre->rchild) //若该结点没有右孩子，设置Tag为Thread
{
pre->rtag = Thread;
pre->rchild = T;
}
pre = T;
InThreading(T->rchild); //递归右孩子线索化
}
}
//初始化二叉树T 开始时的头指针pre + 中序遍历线索化 + 收尾:头尾相连
//参数 *p： 指向树的头指针
//参数 T : 要操作的二叉树
void InOrderThreading(BiThrTree *p, BiThrTree T)
{
*p = (BiThrNode *)malloc(sizeof(BiThrTree)); //头指针分配内存
(*p)->ltag = Link; //结点指针操作结点：赋值
(*p)->rtag = Thread;
(*p)->rchild = *p; //头指针右侧初始化指向自己
if (!T)
{
(*p)->lchild = *p; //空二叉树，指向自己
}
else
{
(*p)->lchild = T; //头指针左侧 指向要操作的对象
pre = *p; //初始化头指针pre
InThreading(T); //中序遍历线索化 后pre 变成最后一个结点T
pre->rchild = *p; //最后一个结点 指向 头指针
pre->rtag = Thread;
(*p)->rchild = pre; //头指针 指向 最后一个结点
}
}
中序线索化二叉树需要两个函数进行操作，首先传入两个参数分别为指向树的头指针，和一个要操作的二叉树。首先为头指针分配内存空间，头指针的左标志先设置为有孩子节点，右标志设置为没有孩子节点，并让右孩子指针指向自己，意味着初始化指针后继为自己。若为空树则把前驱指针指向自己，否则指针的左孩子指向要操作的树，当前指针指向头指针，调用线索化操作函数，收尾工作使当前指针的右孩子结点指向头节点（最后一个节点指向头节点），当前节点的后继设置为空，头指针指向最后一个节点完成线索化。再说说中序遍历线索化，首先判断当前的树是否为空树，中续递归，首先递归左孩子，对于每个节点，若该节点没有左孩子，设置当前结点的左标志为没有孩子，把左孩子指针设置为当前结点，判断当前结点是否有右孩子指针，若没有设置当前结点的右标志为没有孩子节点，并设置后继结点为当前的树节点。操作完成后，把当前结点设置为当前的树节点，在递归右孩子线索化，这部分比较难理解，找张纸画图看着代码来就比较轻松的理解。
下面放上这个代码线索二叉树
哈夫曼树（最优二叉树）
首先明白一个概念，从树中的一个节点到另一个节点之间的分支结构构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度就是从树根到每一个节点的路径长度之和。由此推广考虑带权的的节点，结点的带全路径长度为从该节点到树根之间的路径长度与结点权值的乘积，若一棵树的带权路径最小的二叉树称为最优二叉树，或者哈夫曼树（Huffman）。
哈夫曼书结构
哈夫曼树，相比于二叉树，每个节点都有他自己的权值，和一指向双亲的叶子结点，下面是哈夫曼树的结构：
typedef struct{
unsigned int weight; // 叶子节点权值
unsigned int parent; // 指向双亲的叶子节点
unsigned int lchild;
unsigned int rchild;
}Node,*HuffmanTree;
//动态分配数组，储存哈夫曼编码
typedef char *HuffmanCode;
创建赫夫曼树
计算哈夫曼树的节点数，设置两个哨兵s1，s2，用来存放较小权值的节点，创建一个哈夫曼树的头节点并为其分配内存，根据叶子节点数初始化叶子结点，只需要设置，叶子结点的双亲和孩子都为0（意味着没有），保存叶子节点的权值。再初始化非叶子结点，创建非叶子结点，建立哈夫曼树，在haffmantree【1】~huffmantree【i-1】的范围内选择两个parent为0且weight最小的结点，其序号分别为s1，s2，选出的两个权值最小的叶子结点，组成一个新的二叉树，根为i结点，然后计算新节点的权值等于两个最小权值节点的权值之和。通过for循环，全部建立一次。 再说如何找出最小权值的两个节点，设置标记i，和最小权值min， 遍历全部节点，找出单节点，然后再次遍历找到权值最小的结点赋值给s1，重复上述操作，找到最小节点但不是s1指向的节点，赋值给s2。 下面说明创建哈夫曼树：
//选择两个parent为0，且weight最小的结点s1和s2的方法实现
//n 为叶子节点总数，s1和s2两个指针参数指向要选取出来的两个权值最小的结点
void selecte(HuffmanTree *huffmanTree,int n,int *s1,int *s2){
//标记i
int i = 0;
//记录最小权值
int min;
//遍历全部节点，找出单节点
for(i = 1;i <= n;i++){
//如果此结点的父亲没有，那麽把结点好赋值给min，跳出循环
if((*huffmanTree)[i].parent == 0){
min = i;
break;
}
}
//继续遍历全部节点，找出权值最小节点
for(i = 1; i <= n;i++){
if((*huffmanTree)[i].parent == 0){
if((*huffmanTree)[i].weight < (*huffmanTree)[min].weight){
min = i;
}
}
}
//找到了最小权值的结点，s1指向
*s1 = min;
//遍历全部结点
for(i = 1;i <= n;i++){
//找出下一个节点，且没有被s1指向，那麽赋值i给min，跳出循环
if((*huffmanTree)[i].parent == 0 && i!= (*s1)){
min = i;
break;
}
}
//继续遍历全部结点，找到权值最小的那一个
for(i = 1; i <= n;i++){
if((*huffmanTree)[i].parent == 0 && i!= (*s1)){
if((*huffmanTree)[i].weight < (*huffmanTree)[min].weight){
min = i;
}
}
}
//s2指针指向第二个权值最小的叶子结点
*s2 = min;
}
//创建哈夫曼树并求哈夫曼树的编码，w数组存放已知的n个权值
void createHuffmanTree(HuffmanTree *huffmanTree,int w[],int n){
//m为哈夫曼树总共的节点数，n为叶子结点数
int m = 2 * n - 1;
//s1和s2为当前结点里，要选取的最小权值结点
int s1;
int s2;
//标记
int i;
//创建哈夫曼树的结点所需要的空间，m + 1,代表其中包含一个头结点
*huffmanTree = (HuffmanTree)malloc((m + 1) * sizeof(Node));
//1--n号放叶子节点，初始化叶子结点，初始的时候看做一个个单个结点的二叉树
for(i = 1;i <= n;i++){
//其中叶子结点的权值是w【n】数组来保存
(*huffmanTree)[i].weight = w[i];
//初始化叶子结点（单个二叉树）的孩子和双亲，单个节点，也就是没有孩子和双亲，==0
(*huffmanTree)[i].lchild = 0;
(*huffmanTree)[i].parent = 0;
(*huffmanTree)[i].rchild = 0;
}
//非叶子结点的初始化
for(int i = n + 1;i <= m;i++){
(*huffmanTree)[i].weight = 0;
(*huffmanTree)[i].lchild = 0;
(*huffmanTree)[i].parent = 0;
(*huffmanTree)[i].rchild = 0;
}
printf("\nHuffmanTree\n");
//创建非叶子结点，建哈夫曼树
for(i = n + 1;i <= m; i++){
//在haffmantree【1】~huffmantree【i - 1】的范围内选择两个parent为0
//且weight最小的结点，其序号分别为s1，s2
selecte(huffmanTree,i - 1,&s1,&s2);
//选出的两个权值最小的叶子结点，组成一个新的二叉树，根为i结点
(*huffmanTree)[s1].parent = 1;
(*huffmanTree)[s2].parent = 1;
(*huffmanTree)[i].lchild = s1;
(*huffmanTree)[i].rchild = s2;
//新结点i的权值
(*huffmanTree)[i].weight = (*huffmanTree)[s1].weight + (*huffmanTree)[s2].weight;
printf("%d (%d,%d)\n",(*huffmanTree)[i].weight,(*huffmanTree)[s1].weight,(*huffmanTree)[s2].weight);
}
printf("\n");
}
还有一个逆向求每个叶子节点对应的哈夫曼编码就不介绍了，放在代码里了，有兴趣的自己看看，完整代码如下Huffman。
