从零开始_学_数据结构（三）——树的初步应用

（三）

树常用的基本方法：

①构建一个空树；

②销毁一个树；

③按给的树的定义，来构造一个树（不懂，不太明白这个如何给）；

④若树存在，将树清为一个空树；

⑤若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棵子树。

树的存储结构：

需要考虑两部分：

①树的整体结构如何表示；

       因为实际中，树的整体结构，最终往往是以数组／链表的形式来存储（不可能像树的图形图那样存储）。因此，需要有一个结构，用于表示树的整体结构。

②树的某一个结点如何表示；

       需要有一个结构，用于表示这个结点在该树的数组／链表中的位置。

由于之前没有学过树的存储结构，因此特别说明：

树的存储结构分为两部分：①数据域；②指针域；

所谓的数据域，就是这个数组的数据内容部分。如之前学过的链表结构一样，

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位。

注：赫夫曼树需要位数并非就一定比正常表示法小，只是大部分都比正常表示法要小。

因此，便起到了压缩占用空间的好处。

并且，由于必然命中，假如有某些字符无法命中，那么便可能是文件损坏了。