树模型的拓展
树的等价问题
在离散数学中，对等价关系和对价类的定义是： 如果集合S中的关系R是自反的，对称的和传递的，则称它为一个等价关系。 设R是集合S的等价关系。对任何x∈S，由[x]R={y|y∈S∩xRy}给出的集合[x]R⊆S称为由x∈S生成的一个R等价类。 若R是集合S的等价关系。则由这个等价关系可产生这个集合的唯一划分。即可以按R将S划分为若干不相交的子集S1，S2，...，它们的并即为S，则这些子集Si便称为S的R等价类。 应该如何划分等价类呢？假设集合S有n个元素，m个形如（x,y）（x，y∈S）的等价偶对确定了等价关系R，需求S的划分。 确定等价类的算法可如下进行：
- 令S中每个元素各自形成一个单个成员的子集，记做S1，S2，...，Sn。
- 重复读入m个偶对，对每个读入的偶对（x，y），判读x和y所属子集。不失一般性，假设x∈Si，y∈Sj，若Si！=Sj，则将Si并入Sj，并置Si为空（或将Sj并入Si并置Sj为空）。则当m个偶对都被处理之后，S1，S2，...，Sn中所有非空子集即为S的R等价类。
因此，可见划分等价类需对集合进行的操作有3个：其一是构造只含单个成员的集合；其二是判定某个单元素所在子集；其三是归并两个互不相交的集合为一个集合。 以集合为基础的抽象数据类型可用多种实现方法，如用位向量表示集合或用有序表表示集合。 如何高效的实现以集合为基础操作的抽象数据类型，则取决于该集合打大小以及对此集合所进行的操作。 数据结构中引入一个叫MFSet 的ADT，其实他就是并查集（见CSDN博客当时的并查集总结）的完善版 结构存储父结点，当两个结点的祖宗结点相同时便可以认为这是属于同一个集合的结点。 找祖宗操作：
int find_mfset(MFSet S, int i) {
// 找集合S中i所在子集的根
int j;
if (i<0 || i>S.n) return -1; // i不是S中任一子集的成员
if (i==0)
printf("t%d(%d%3d)n",i,S.nodes[0].data,S.nodes[0].parent);
for (j=i; S.nodes[j].parent>=0; j=S.nodes[j].parent)
printf("t%d(%d%3d)n",j,S.nodes[j].data,S.nodes[j].parent);
return 1;
}// find_mfset
两个结点判断是否一个集合：
Status merge_mfset(MFSet &S, int i, int j) {
// S.nodes[i]和S.nodes[j]分别为S中两个互不相交的子集Si和Sj的根结点。
// 求并集Si∪Sj。
if (i<0 || i>S.n || j<0 || j>S.n) return ERROR;
S.nodes[i].parent = j;
return OK;
} // merge_mfset
在使用并查集的时候有个需要注意的地方，就是整个算法的时间复杂度是和树的深度有关的。 如果建的树除了叶子外只有出度为1的结点，这种极端的例子时间复杂度高达O(n^2)。 那么解决个弊端有两个方式，一是选择结点较少的一枝添加结点，顶一个是就是“路径压缩” 路径压缩是在学并查集就学的东西，在集训的时候就已经没有问题，但书中提出了选择建树是一个我没有想到过的优化方式，
Status mix_mfset(MFSet &S, int i, int j) {
// S.nodes[i]和S.nodes[j]分别为S中两个互不相交的子集Si和Sj的根结点
// 求并集Si∪Sj。
if (i<0 || i>S.n || j<0 || j>S.n) return ERROR;
if (S.nodes[i].parent>S.nodes[j].parent) { // Si所含成员数比Sj少
S.nodes[j].parent+=S.nodes[i].parent;
S.nodes[i].parent=j;
} else { // Sj的元素比Si少
S.nodes[i].parent+=S.nodes[j].parent;
S.nodes[j].parent=i;
}
return OK;
} // mix_mfset
这种方式使建的树深度不会超过[log2n]+1。 但是我还是更喜欢路径压缩，一是简单，压缩在查询的过程中完成了，而是压缩完，路经长度不会大于4 只需要修改find查找函数即可以实现：
int fix_mfset(MFSet &S, int i) {
// 确定i所在子集，并将从i至根路径上所有结点都变成根的孩子结点。
int j,k,t;
if (i<1 || i>S.n) return -1; // i 不是S中任一子集的成员
for (j=i; S.nodes[j].parent>=0; j=S.nodes[j].parent)
printf("t%d(%d%3d)n", j, S.nodes[j].data, S.nodes[j].parent);
for (k=i; k!=j; k=t) {
t=S.nodes[k].parent; S.nodes[k].parent=j;
}
return 1;
} // fix_mfset
树的计数
树的计数放在了最后一节，其实到现在证明我也没有看明白，先把结论总结下来吧。
这一节主要讨论的是具有n个结点的不同形态树有多少棵。
二叉树相似是指：二者都为空树或二者均不为空树而且他们的左右子树分别相似
二叉树等价是指：二者不仅相似，而且所有对应结点上的数据元素均相同。
二叉树的计数问题就是讨论二叉具有n个结点、互不相似的二叉树的数目bn。
在n很小的时候，可直观的得到b0=1为空树；b1=1是只有一个根结点树，b2=2，b3=5。
一般情况下，一棵具有n（n>1）个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树和一棵具有n-i-1个结点的左右子树组成，其中0<=i<=n-1由此可得地推公式
b0=1
bn=Σ(n-1,i=0)bi bn-i-1 （n>=1）
最后，前序或后序加上中序遍历就可以确定一棵唯一的树，这也是判断两个树是否相同最好的方式。
树和森林
树的存储
树的各种操作还是离不开树的存储的，其实树的存储才是最好玩的东西。
双亲表示法
假设以一组连续的空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置
#define MAX_TREE_SIZE 100
typedef struct //节点结构
{
TElemType data;
int parent; //双亲位置域
}PTNode;
typedef struct //树结构
{
PTNode node[MAX_TREE_SIZE];
int count; //根的位置和节点个数
}PTree;
这种存储结构利用了每个结点（除了根结点以外）只有唯一的双亲的性质，在查找双亲的操作中可以在O(1)内实现，对于查找根结点也不过多次找双亲，实现和时间复杂度都可以接受。 但是，如果要找孩子结点，要遍历整棵树！！！因此，数据结构和算法是相互服务的，看需求选择。
孩子表示法
由于每个结点可能有多个子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵树的根结点。 其实和二叉链表很像，但是不一定是几个叉，也就是说对于孩子指针域，个数不确定，那么我们也要重新考虑这个问题，设定几个指针，既然个数不确定，那用动态存储就比较好，那么，指针域用链表存储，那么实现存储一棵树就应该是这个样子：
实现虽然麻烦，但是这应该是最直观最好理解的存储方式，不作细总结了。
孩子兄弟表示法
孩子兄弟表示法又称二叉树表示法，或二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分表指向该结点的第一个孩子结点和下一个兄弟结点。是不是很炫酷。。。
typedef struct CSNode
{
TElemType data;
CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
其实就是左支保存孩子，右支保存兄弟，当想遍历所有孩子的时候，只需要先遍历左子树一次，然后遍历左子树的右子树到空就可以了。 如果只看孩子兄弟表示法不形象的话，参照孩子孩子表示法便可以知道存储的是什么样子的：
也就是有这样的存储结构，所以树和森林转换起来非常的方便。
森林和二叉树的转换
由于二叉树和树都可以用二叉链表作为存储结构，则以二叉链表作为媒介可导出树和二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到一颗二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。
对于右面那棵树，即可以认为他是左面那可树的存储结构表示，也可以认为他本来就是一棵二叉树。 如果按照孩子兄弟表示法，我们可知，根结点的右支必为空（根没有兄弟），那么若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。 这个一一对应的关系导致森林或树与二叉树可以相互转换：
森林转换为二叉树
如果F={T1,T2,...,Tm}是森林，则可按如下规则转换成一棵二叉树B=(root,LB,RB)。
- 若F为空，即m=0，则B为空树
- 若F非空，即m！=0，则B的根root即为森林中第一棵树的根ROOT（T1）；B的左子树LB是从T1中根结点的子树森林F1={T11，T12，....，T1m1}转换而成的二叉树，其右子树RB是从森林F'={T2,T3,...,Tm}转换而成的二叉树
二叉树转换为森林
如果B=(root,LB,RB)是一棵二叉树，则可按如下规则转换成森林F={T1,T2,...,Tm}。
- 若B为空，则F为空
- 若B非空，则F中第一棵树T1的根ROOT（T1）即为二叉树B的根root；T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外其余树组成F'={T2,T3,...,Tm}是由B的右子树RB转换而成的森林。
明显，上述算法为递归算法。
树和森林的遍历
已知二叉树有三种遍历方式，因为树和森林都可以用二叉链表，因此树和森林的遍历的实现也算是依靠着树的遍历实现的。 由树结构的定义可引出两种次序遍历树的方法，一种是先根遍历树，即：先访问树的根结点，然后依次访问先根遍历根的每一棵树；另一种是后根遍历，即：先依次后根遍历每一棵树，然后访问根结点。 按照森林和树的相互递归关系，我们可以推出森林的两种遍历方法：
先序遍历森林
若森林非空，则可按照下述规则遍历之：
- 访问森林第一棵树的根结点
- 先序遍历第一棵树中根结点的子树森林
- 先序遍历除去第一棵树之后剩余的树构成的森林
中序遍历森林
若森林非空，则可按照下述规则遍历之：
- 中序遍历森林中的第一棵树的根结点的子树森林
- 访问第一棵树的根结点
- 中序遍历除去第一棵树之后剩余的树构成的森林
其实说白了，森林的先序和中序遍历分别对应了二叉树的先序和中序遍历（当用孩子兄弟表示法的时候）。
线索二叉树实现
遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。这实际上是对一个非线性结构进行线性化操作，使得每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。
当以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。
那么，如果有一个需要大量查询前驱后继的程序，对于每次都遍历，时间成本过大，我们便需要能快速查找前驱后继的办法。最简单的方法，每个结点加两个存储前驱后继的变量，但是这样却浪费大量的空间。
另一种方法，对于n个结点的二叉链表中必定存在n+1个空链域，由此，可以利用这些空链域来存放结点的前驱和后继的信息。
规定如下：若结点有左子树，则其lchild域指示其左孩子。否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。（为了避免混淆，尚需改变结点结构，增加两个标志域，用来区分其左右孩子指针到底指向的是子树还是前驱后继）。
更改为这种结构的二叉链表作为二叉树的存储结构叫做线索链表，其中指向结点前驱和后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。
在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直至其后继为空时为止。
在后序线索树中招结点后继较为复杂些，可分为3种情况：
- 若结点x是二叉树的根，则其后继为空
- 若结点x使其双亲的右孩子或左孩子且其双亲没有右子树，则其后继即为双亲结点
- 若结点x是其双亲的最孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点
为方便起见，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，病令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；反之，灵感二叉树中序序列中的第一个结点的l迟来的域指针和最后一个结点rchild域的指针均指向头结点。
这好比为二叉树建立了一个双向线索链表，既可从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。
以双向线索链表为存储结构是对二叉树进行遍历的算法：
Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType)) {
// T指向头结点，头结点的左链lchild指向根结点，头结点的右链lchild指向
// 中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树T，
// 对每个数据元素调用函数Visit。
BiThrTree p;
p = T->lchild; // p指向根结点
while (p != T) { // 空树或遍历结束时，p==T
while (p->LTag==Link) p = p->lchild;
if (!Visit(p->data)) return ERROR; // 访问其左子树为空的结点
while (p->RTag==Thread && p->rchild!=T) {
p = p->rchild; Visit(p->data); // 访问后继结点
}
p = p->rchild; // p进至其右子树根
}
return OK;
} // InOrderTraverse_Thr
线索化
由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继是信息是只有在遍历的时候才能得到，因此，线索化的过程即为在遍历的过程中修改空指针的过程。
为记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前访问的结点，则per指向他的前驱。由此，可得中序遍历建立中序线索化链表的算法：
Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { // 算法6.6
// 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。
if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
Thrt->LTag = Link; Thrt->RTag =Thread; // 建头结点
Thrt->rchild = Thrt; // 右指针回指
if (!T) Thrt->lchild = Thrt; // 若二叉树空，则左指针回指
else {
Thrt->lchild = T; pre = Thrt;
InThreading(T); // 算法6.7：中序遍历进行中序线索化
pre->rchild = Thrt; pre->RTag = Thread; // 最后一个结点线索化
Thrt->rchild = pre;
}
return OK;
} // InOrderThreading
更多基础介绍：线索二叉树概要
Copyright © 2020 Powered by MWeb, Theme used GitHub CSS.