树，二叉树，森林，哈夫曼树

树，二叉树，森林，哈夫曼树

写在前面

我很懵逼啊，树这一章理论很多，但是给出的代码确是少之又少，难道这就是这一章的特色？

主要内容

1.树
2.二叉树
3.森林与树
4.哈夫曼树

OPEN

树
什么是树？

对，这是树，但不是数据结构里面说的树。
数据结构中的树是这样的

仔细一看，这两颗树还是有点神似的。
回到正题
讲一下有关一些树的性质
上图的每个圈称为树结点
结点之间又有相互的关系
比如A结点为B结点与C节点的父结点，相同的，BC结点为A结点的子结点
每个结点还有相应的度，度就是结点所含子树数量
比如A的度为2，E的度为1；
树的度便为整个树的各结度的最大值

那么应该如何表示一个树呢？
这里讲三种方法
双亲表示
双亲表示的便是在每个树的结点增加一个存储其父节点的数据，保存每一个结点的父结点。

typedef struct Ptree{int date;int parent;
}Ptree; 

比如这样一个树

他用双亲表示便是

孩子表示法
孩子表示法指把每个孩子结点排列起来，把单链表作为储存结构，则n个结点便有n个孩子链表如果是叶节点则此单链表为空，然后n个头指针又组成一个线性表采用顺序储存结构储存进一个一维数组中

孩子兄弟表示法

通过我们对树的观察我们可以发现，树的每个结点如果它的左孩子存在那就是唯一的它的右兄弟存在也就是唯一的，那么我们就可以换一种存储的方法。

typedef struct CStree{int date;strcut CStree *leftson,*rightbrother;
}CStree; 

二叉树

二叉树顾名思义有两个叉的树专业的来说就是n个结点的有限集合，该集合或为空集或为有一个根节点和两个互不相交的，分别称为左子树和右子树的二叉树组成。
专业的说法理解起来比较复杂，以我的理解，二叉树就是用每个父结点最多只含有两个子结点的树。
像这样

紧接着，二叉树也也需要注意一些二叉树的特殊性质
当某个结点只有一个子树时也要分析他是右子树还是左子树，二叉树就像左右手一样，虽然都是五个手指头，但是就是不一样。
一些特殊的二叉树
1.满二叉树
顾名思义，满二叉树便是 “饱满的二叉树” ，当所有的分支结点都有左子树和右子树并且所有的叶节点 都在同一层，那么这个二叉树便称为满二叉树
就像这样

一看就很饱满。
2.完全二叉树
完全二叉树也是在满二叉树的基础上而来，如果编号为i的结点与同样深度满二叉树的结点的编号相同，那么这个二叉树就可以称为完全二叉树。

像这样便是一个完全二叉树，所以我们就不难得出，满二叉树一定是完全二叉树，完全二叉树却不一定是满二叉树
我们也可以总结出完全二叉树的一些特点

1. 叶节点只能出现在地下两层中
2. 最下层叶子结点一定从左边分开始
3. 如果倒数第二层含有叶节点那么一定从右边开始
4. 如果结点的度为1那么结点含有的绝对是左子树而不是右子树

二叉树的性质
由于二叉树的特点，那么二叉树也有一些特性

1. 在二叉树的第I层上最多有2的（i-1）次方个结点
2. 深度为K的二叉树最多有2的k次方减一个结点
3. 对于任何一颗二叉树T，如果其终端结点数为n0度为2的结点数为n1，那么n0=n2+1；

二叉树的储存
由于二叉树严谨的顺序储存，那么我们就可以用线性结构来
就用数组储存其内容，下标即为结点。


但是这样储存确时有时有一种极端情况，当所有的左子树全部不存在时，那么却是很浪费储存空间

数组不太好的画话我们可以用链表链表好啊只需要定义一个数据域和指针域
就像这样

typedef struct BiTree{int date;struct BiTree *lchild,*rchild;
}BiTree;

二叉树的遍历
根据遍历的顺序不同，二叉树的遍历可以分为前序遍历，中序遍历，后续遍历，层序遍历。

前序遍历(有点像DFS)

void Order(BiTree* T){if(T==NULL){return;}Order(T->lchild);Order(T->rchild);
}

中序遍历

void Order(BiTree* T){if(T==NULL){return;}Order(T->lchild);printf("%d",t->date);Order(T->rchild);
}

后续遍历

void Order(BiTree* T){if(T==NULL){return;}Order(T->lchild);	Order(T->rchild);printf("%d",t->date);
}

层序遍历（有点像BFS）

二叉树的遍历
在建立二叉树时我们看有做出一个约定当遇到#时我们就定义此结点为NULL

void CreatBiTree(BiTree *T){char ch;scanf("%c",&c);if(c==NULL){T=NULL;}else{T=(BiTree*)malloc(sizeof(BiTree));T->date=c;CreatBitree(T->lchild);CreatBitree(T->rchild);}
}

森林，树与二叉树的转换

森林
什么是森林？一堆树在一起不就是森林了嘛

这就是一个森林啦。

你看，上面讲了二叉树，它的性质那么多，也好操作，那么有没有一种方法能把森林啦树啦转换为二叉树呢想屁呢你别说还真有

树转二叉树

1. 加线 在所有兄弟结点之间加上连线
2. 去钱。对树中每个结点，只保留它与第一个孩子结点的连线，删除色与其他孩
   子结点之间的连线。
3. 层次调整。以树的根结点为轴心，将整棵树顺时针旋转 定的角度，使之结构
   层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结
   点的右孩子。

森林转二叉树

1. 先把森林中的每个树转换为二叉树
2. 从第二颗二叉树开始把树的根结点作为前一棵树的右儿子，依次连接，这样就能得到一棵由原来的森林转化的二叉树。

赫夫曼树/哈夫曼树

说哈夫曼树之前先举一个例子，我们经常根据成绩来给学生分级60-69是D，70-79是C，80-89是B，90-100是A
一般写一个程序

if(grade>=90){A;}else if(grade>=80){B;}else if(grade>=70){C;}else if(grade>=60){D;}else{E;}

这样的话总会只能一个一个判断,但是实际上大部分学生的成绩处于70-80，那么怎样才能让我们判断的次少而合理呢
现在假设我们有这样一个前提

这里可以看出，70-79的同学是最多的，我们做出这样的一个判断二叉树

那这个二叉树是怎么来的呢？又是为什么这样做呢？
当然这个树不是凭空来的，这是一个聪明的前人———哈夫曼前辈是吧，他为了解决一些问题提出来的。
哈夫曼树主要是为了解决一些带权的树的问题

我们先引入另一个概念，树的路径长度——树根到每一个结点的路径之和。
左树的路径即为1+1+2+2+3+3+4+4=20
右树的长度为1+1+2+2+2+2+3+3=16
然后我们将两个结点之间的数字称为两个结点之间的权，那么有了权之后，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积
哈夫曼树便是带权路径长度 WPL 最小的二叉树
左树的WPL=5* 1+15* 2+40* 3+30 * 4+10*4=315
右树的WPL=5 * 3+15 * 3+40 * 2+30 * 2+10 * 2=220
回到刚才的问题，右树又是怎么构成的呢？
我们先把所有的结点和他所带的权值从小到大排个序
A5,E10,B15,D30,C40
然后我们便将最小的两个结点构成一个二叉树权值小的为左孩子大的为右孩子
那么现在的序列就变成了
AE15,B15,D30,C40
接下来便是不断执行这个操作
AEB30,D30,C40
AEBD60,C40

这就是最后构成的哈夫曼树。
那么哈夫曼树有什么好处呢？
如果我们现在有 10000 个学生 百分制成绩需计算五级分制成绩，用左树二叉树的判断方法，需要做 31500 次比较，而右二叉树的判断方法，只需要 22000 次比较 差不多少三分之一量，是不是很快啊。