（三）
树常用的基本方法：
①构建一个空树；
②销毁一个树；
③按给的树的定义，来构造一个树（不懂，不太明白这个如何给）；
④若树存在，将树清为一个空树；
⑤若t为空树，返回true，否则返回false；
⑥返回树的深度；
⑦返回树的根节点；
⑧某结点cur_e是树t的一个结点，返回此结点的值（应该说的是结点的数据部分的值）；
⑨给树t的结点cur_e赋值为value（这个value是我们给的）；
⑩若cur_e是树t的非根结点，则返回它的父结点，否则返回空；（原文是双亲，但是树只有一个父结点，不会有2个）；
（11）若cur_e是树t的非叶结点，则返回它的最左孩子，否则返回空；
（12）若cur_e有右兄弟，则返回它的右兄弟，否则返回空（但若有多个怎么办？）；
（13）指针p指向树t的某个结点，i为所指向的结点的度+1，非空树c与t不相交，操作结果：将树c插入树t，位置是，指针p指向的结点的第i棵子树的位置（即假如有结点有二棵子树，那么c就是结点的第三棵子树）；
（14）p指向树t的某个结点，i为所指结点p的度，操作结果：删除树t中p所指的第i棵子树。
树的存储结构：
需要考虑两部分：
①树的整体结构如何表示；
因为实际中，树的整体结构，最终往往是以数组／链表的形式来存储（不可能像树的图形图那样存储）。因此，需要有一个结构，用于表示树的整体结构。
②树的某一个结点如何表示；
需要有一个结构，用于表示这个结点在该树的数组／链表中的位置。
由于之前没有学过树的存储结构，因此特别说明：
树的存储结构分为两部分：①数据域；②指针域；
所谓的数据域，就是这个数组的数据内容部分。如之前学过的链表结构一样，
1. struct node //node是节点的意思
2.
{
3. item item;
4.
node* next; //struct node表示struct node的指针，貌似只用node*next也可以
5. };
item是数据部分，用于储存数据（也许是int，也许是char*）
而node*是指针域，其用于表示这个结点和其他结点之间的关系。注意，指针域不一定非要用指针类型，也许是非指针类型。
（1）双亲表示法：
如果树的整体结构以数组来存储的话。
则是
structnode
{
string mm;
intparent;
};
其中，mm是数据域，parent是其父结点下标的int值。由于根节点没有父结点，因此可以规定根结点的parent值为-1（数组下标最小为0）
由于每一个结点都保存了其父结点的值，因此，当我们有一个子结点时，可以轻易找到其父结点。而父结点又能继续找到他的父结点，直到parent值为-1时，找到了根节点。
具体过程可以自己画一个树形图，很简单。
时间复杂度为o（1）。
关于时间复杂度：
这里的执行函数次数，指的是最差情况下的次数。
①当固定若干次（执行函数的次数），则为常数；
②当数据的数量越多，次数成正比上升（可能会乘以一个固定值），那么是线性阶，比如数组；
③数据越多，需要的次数是乘方级的，则是平方阶；
④数据越多，但需要的次数比线性慢，例如二分查找法，数量翻一倍，次数增加一次，这种是对数阶；
⑤数据越多，需要的时间是三次方上升，是立方阶（还有4次方5次方等）；
⑥数据越多，需要的时间指数级别上升，是指数阶；
一般情况下，需要时间从少到多的顺序是：常数——》对数阶——》线性阶——》nlongn阶——》平方阶——》立方阶——》阶乘——》指数
后面几种比较少见，因为其效率太低，一般不考虑。
缺点：如果要找一个结点的子节点的话，会很麻烦，需要遍历整个树。
改进办法：再设置一个int类型变量：intlchild; 用于描述其最左子结点。
之所以是最左，是因为他可能有多个子结点，也可能没有子结点。没有子结点很简单，值为-1即可。如果有多个子结点，必然只能指向其中的一个，因此设置为最左子结点（当然，最右也可以）。
这样的话，如果树只有0个结点或者1个结点，那么找起来是很简单的。
但显然，树不可能只有0个结点或者1个结点，如果有2个结点，甚至多个结点呢？书上说，有2个子结点的话，在知道左子结点的时候，很容易找到右子结点，但我觉得不现实啊？你怎么知道有2个子结点，怎么知道右子结点是哪个？
改进办法2nd：设置一个int类型变量：intlbrother; 其效果是指向该结点右边的兄弟结点。这样的话，即使有多个子结点，也很容易找到某个子结点。
（2）孩子表示法
数组太麻烦了，不如上链表吧。
链表的特点是指针，他可以指向某个结点。父节点有若干个指针，分别指向自己的各个子节点。
指针的表示方法有三种：
①找树中最大的度，最大的度为指针的数量；
②一个指针，指向一个指针数组，指针数组的成员数量，是这个结点的子节点数量；
③每一条路径都是一个链表，其中链表的第一个指针，存储在一个二维数组之中，然后调用指针即可。
（3）兄弟表示法
每个结点，有两个指针。
第一个指针，指向它的最左边的孩子；
第二个指针，指向他右边的兄弟；
假如没有孩子，则为空；
假如右边的兄弟已经没有更右边的兄弟了，则为空；
二叉树的遍历：
所谓二叉树的遍历，就是指访问二叉树每一个结点。
用途有例如：①查找指定数据；②输出每一个遍历的结点的内容；
遍历方式分为前序、中序、后续。
以输出结点内容为例：
假如是查找，则需要修改遍历的逻辑，并且函数也应该加入条件判断。
例如，
以上是我自己写的，也许还有更好的。
当然，假如二叉树是有序的（即左子树的值必然比根小，右子树的值必然比根大），那么必然存在一个更好的查找算法。
二叉树的建立和插入：
书上列的仅仅是按自己预想设计那样建立一个二叉树。如下面代码：
以上这个树是无序的。
也可以通过创建一个空树：
然后插入一个子结点：
这个插入是有序的（依次判断，比当前结点小，则移动到当前结点的左子，否则右子，直到遇见空结点，然后放入空结点）。
二叉树的查找方法之一：
清空一个树：
赫夫曼树：
特点是：
①是一个二叉树；
②所有字符都在其二叉树的某个叶之中；
③根据出现频率，来规定字符的位置；
④出现频率越高的，其出现字符的位置越高；
⑤是一种压缩算法；
其原理是，根据字符出现的频率，将其置于二叉树的不同深度的叶上，在遍历的时候，以位的形式来尝试命中某个叶结点，当命中时，即为要找的字符，然后从下一位开始寻找下一个字符。
例如，二叉树是这样的：
abc分别在某个叶结点上。
当我们正常表示abc三个子节点时，至少要用2位来表示，例如：a00，b01，c10
而在遍历赫夫曼树时，找左子树记为0，找右子树记为1。其表示为：a0，b10，c11。
在最优情况：aaaa，正常表示法需要8位（00 00 00 00），但赫夫曼树表示法只需要4位（0 0 0 0）即可。
即使最差情况：表示bcbc，正常和赫夫曼树都需要8位。
注：赫夫曼树需要位数并非就一定比正常表示法小，只是大部分都比正常表示法要小。
因此，便起到了压缩占用空间的好处。
并且，由于必然命中，假如有某些字符无法命中，那么便可能是文件损坏了。