（三）
树常用的基本方法：
①构建一个空树；
②销毁一个树；
③按给的树的定义，来构造一个树（不懂，不太明白这个如何给）；
④若树存在，将树清为一个空树；
⑤若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）兄弟表示法
每个结点，有两个指针。
第一个指针，指向它的最左边的孩子；
第二个指针，指向他右边的兄弟；
假如没有孩子，则为空；
假如右边的兄弟已经没有更右边的兄弟了，则为空；
二叉树的遍历：
所谓二叉树的遍历，就是指访问二叉树每一个结点。
用途有例如：①查找指定数据；②输出每一个遍历的结点的内容；
遍历方式分为前序、中序、后续。
以输出结点内容为例：
①二叉树的数据结构：
struct Tree
{
data m;
Tree* Lchild = NULL, *Rchild = NULL;
};
②前序遍历函数：
void PreOrderTraverse(Tree*T) //前序遍历
{
if (T == NULL) //如果指向的是空结点，则返回
return;
std::cout << T->m << std::endl;
PreOrderTraverse(T->Lchild); //继续遍历左子结点
PreOrderTraverse(T->Rchild); //最后遍历右子结点
}
③中序遍历函数：
void MidOrderTraverse(Tree*T) //中序遍历
{
if (T == nullptr)
return;
MidOrderTraverse(T->Lchild);
std::cout << T->m << std::endl;
MidOrderTraverse(T->Rchild);
}
④后序遍历函数：
void LastOrderTraverse(Tree*T) //后序遍历
{
if (T == nullptr)
return;
LastOrderTraverse(T->Lchild);
LastOrderTraverse(T->Rchild);
std::cout << T->m << std::endl;
}
假如是查找，则需要修改遍历的逻辑，并且函数也应该加入条件判断。
例如，
void PreOrderTraverse(Tree*T,data &p,Tree* q) //前序遍历查找，p是需要查找的数据，q是指向该结点的指针
{
if (T == NULL) //如果指向的
return;
if (p == T->m)
q = T;
PreOrderTraverse(T->Lchild, p, q);
PreOrderTraverse(T->Rchild, p, q);
}
以上是我自己写的，也许还有更好的。
当然，假如二叉树是有序的（即左子树的值必然比根小，右子树的值必然比根大），那么必然存在一个更好的查找算法。
二叉树的建立和插入：
书上列的仅仅是按自己预想设计那样建立一个二叉树。如下面代码：
void CreateTree(Tree**T,int p)
{
data temp;
if (p == 0)return;
std::cout << "输入一项内容：";
std::cin >> temp;
if (temp == 0) //这里假设遇见0时，认为是空结点（即所有结点的内容必然是非0的）
{
*T = NULL; //让指向当前指针的是空指针
return;
}
else //采用前序遍历方法创建一个新树
{
Tree *q = new Tree;
*T = q;
(*T)->m = temp;
CreateTree(&(*T)->Lchild,p-1); //因为要传递指向该指针的地址，因此要在实际地址（(*T)->Lchild)之前加地址运算符&
CreateTree(&(*T)->Rchild,p-1);
}
}
以上这个树是无序的。
也可以通过创建一个空树：
void CreateTree(Tree* T)
{
T->Lchild = T->Rchild = NULL;
}
然后插入一个子结点：
void InsertTree(Tree**T,Tree**m) //在树T内，插入树m
{
if (*T == nullptr)
*T = *m;
else
{
if ((*m)->m < (*T)->m)
InsertTree(&(*T)->Lchild, m);
else
InsertTree(&(*T)->Rchild, m);
}
}
这个插入是有序的（依次判断，比当前结点小，则移动到当前结点的左子，否则右子，直到遇见空结点，然后放入空结点）。
二叉树的查找方法之一：
Tree* FindTree(Tree*T, data value) //查找某个值，返回其遍历查到的一个结点（设置此方法为前序遍历，具体可以修改）
{
if (T->m == value)
return T;
Tree*temp;
temp=FindTree(T->Lchild, value);
if (temp == NULL)
{
temp=FindTree(T->Rchild, value);
if (temp == NULL)
return NULL;
else return temp;
}
else return temp;
}
清空一个树：
void DeleteTree(Tree*T)
{
if (T == NULL) //如果是空指针，则返回（停止递归）
return;
Tree *templeft = T->Lchild; //临时指针，用于指向左右子节点
Tree *tempright = T->Rchild;
delete T;
DeleteTree(templeft);
DeleteTree(tempright);
}
赫夫曼树：
特点是：
①是一个二叉树；
②所有字符都在其二叉树的某个叶之中；
③根据出现频率，来规定字符的位置；
④出现频率越高的，其出现字符的位置越高；
⑤是一种压缩算法；
其原理是，根据字符出现的频率，将其置于二叉树的不同深度的叶上，在遍历的时候，以位的形式来尝试命中某个叶结点，当命中时，即为要找的字符，然后从下一位开始寻找下一个字符。
例如，二叉树是这样的：
ABC分别在某个叶结点上。
当我们正常表示ABC三个子节点时，至少要用2位来表示，例如：A00，B01，C10
而在遍历赫夫曼树时，找左子树记为0，找右子树记为1。其表示为：A0，B10，C11。
在最优情况：AAAA，正常表示法需要8位（00 00 00 00），但赫夫曼树表示法只需要4位（0 0 0 0）即可。
即使最差情况：表示BCBC，正常和赫夫曼树都需要8位。
注：赫夫曼树需要位数并非就一定比正常表示法小，只是大部分都比正常表示法要小。
因此，便起到了压缩占用空间的好处。
并且，由于必然命中，假如有某些字符无法命中，那么便可能是文件损坏了。