线索二叉树实现
遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。这实际上是对一个非线性结构进行线性化操作，使得每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。
当以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。
那么，如果有一个需要大量查询前驱后继的程序，对于每次都遍历，时间成本过大，我们便需要能快速查找前驱后继的办法。最简单的方法，每个结点加两个存储前驱后继的变量，但是这样却浪费大量的空间。
另一种方法，对于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
更多基础介绍：线索二叉树概要
树的遍历
遍历二叉树
在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就提出了一个遍历二叉树的问题。即如何按某条搜索路径巡防树中每个结点，使得每个节点均被访问一次，而且仅被访问一次。 因为二叉树是由3个基本单元组成：根结点，左子树和右子树。因此，若能依次遍历这三个部分，便是遍历了整个二叉树。根据对这三个部分遍历顺序不同，那么我们就有了先序遍历，中序遍历，后序遍历。 先序遍历： 若二叉树为空则空操作（递归边界），否者： 1.访问根节点 2.先序遍历左子树 3.先序遍历右子树 中序遍历： 若二叉树为空则空操作，否者： 1.中序遍历左子树 2.访问根节点 3.中序遍历右子树 后序遍历： 若二叉树为空则空操作，否者： 1.后序遍历左子树 2.后序遍历右子树 3.访问根节点 这个过程明显是个递归的过程，《数据结构》给出了先序遍历的伪代码：
Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) {
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数，
// 先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
// 最简单的Visit函数是：
// Status PrintElement( ElemType e ) { // 输出元素e的值
// printf( e ); // 实用时，加上格式串
// return OK;
// }
// 调用实例：PreOrderTraverse(T, PrintElement);
if (T) {
if (Visit(T->data))
if (PreOrderTraverse(T->lchild, Visit))
if (PreOrderTraverse(T->rchild, Visit)) return OK;
return ERROR;
} else return OK;
} // PreOrderTraverse
对于上图的树（忽略他的线索线），如果我们采用不同的遍历方式，可以得到不同的结果： 先序遍历：-+ab-cd/ef 中序遍历：a+bc-d-e/f 后序遍历：abcd-*+ef/- 其实这就是前缀表达式（波兰式），中缀表达式，后缀表达式（逆波兰式）。 其实用树便可以实现前缀、中缀、后缀表达式相互转换，但是，一般我们采用栈的方式实现，至少不用建树。 仿照递归算法执行过程中递归工作栈的状态变化状态可直接写出相应的非递归算法。例如，从中序遍历递归算法执行过程中递归工作栈的状态可见： 1.工作记录中包含两项其一是递归调用的语句编号,其二是指向左子树根的指针进栈 2.若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回，则应访问当前层即栈顶记录中指针所指的根结点 3.若是从右子树返回，则表明当前层的遍历结束，应继续退栈。从另一角度，这意味着遍历右子树时不再需要保存当前层指针，直接修改栈顶记录中的指针就好。 非递归算法执行效率要比递归算法高些，有时候可以考虑。
Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType)) {
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
// 中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
stack S;
BiTree p;
InitStack(S); Push(S, T); // 根指针进栈
while (!StackEmpty(S)) {
while (GetTop(S, p) && p) Push(S, p->lchild); // 向左走到尽头
Pop(S, p); // 空指针退栈
if (!StackEmpty(S)) { // 访问结点，向右一步
Pop(S, p);
if (!Visit(p->data)) return ERROR;
Push(S, p->rchild);
}
}
return OK;
} // InOrderTraverse
Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType)) {
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
// 中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
stack S;
BiTree p;
InitStack(S); p = T;
while (p || !StackEmpty(S)) {
if (p) { Push(S, p); p = p->lchild; } // 非空指针进栈，继续左进
else { // 上层指针退栈，访问其所指结点，再向右进
Pop(S, p);
if (!Visit(p->data)) return ERROR;
p = p->rchild;
}
}
return OK;
} // InOrderTraverse
建立二叉树
遍历是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如：对一颗已知树可求结点的双亲，求结点的孩子结点，判断结点所在的层次等。 反之，也可以在遍历过程中生成结点，建立二叉树的存储结构。
BiTree CreateBiTree(BiTree &T) {
// 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
T->data = ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return T;
} // CreateBiTree
对二叉树的遍历的搜索路径除了已经说的先序中序后序遍历，还可以从上到下（DFS），从左到右（BFS）按层次遍历。 但是遍历二叉树的算法中的基本操作时访问结点，则无论安那一种次序进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)，所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n则空间复杂度也为O(n)。
回溯法与树的遍历
在程序设计中有一类求一组解或求全部解或求最优解的问题，比如八皇后问题，骑士周游问题，不是根据某种确定的计算法则，而是利用试探和回溯的搜索技术求解。 回溯法的实质是一个先序遍历一棵“状态树”的过程，只是这棵树不是遍历前预先建立的，而是隐含在遍历过程中的（边建立便遍历，随之释放）。 八皇后问题以后讨论，在数据结构中有一个很好玩的例题。
求含n个元素的集合的幂集 集合A的幂集是由集合A的所有子集所组合的集合。如：A={1，2，3}，则A的幂集， p(A)={{1,2,3},{1,2},{1,3},{2,3},{1},{2},{3},∅}
但是这个答案肿么解出来，树中给出了一个树的思想，因为对每个元素只有舍或者留两种情况，那么，我们可以用二叉树，左支是留，右支是舍：
没有比代码更直观的了：
void GetPowerSet(int i, List A, List &B) {
// 线性表A表示集合A，线性表B表示幂集ρ(A)的一个元素。
// 局部量k为进入函数时表B的当前长度。
// 第一次调用本函数时，B为空表，i＝1。
ElemType x;
int k;
if (i > ListLength(A)) Output(B); // 输出当前B值，即ρ(A)的一个元素
else {
GetElem(A, i, x); k = ListLength(B);
ListInsert(B, k+1, x); GetPowerSet(i+1, A, B);
ListDelete(B, k+1, x); GetPowerSet(i+1, A, B);
}
} // GetPowerSet
其实还有优化，比如加上状态压缩什么的。当然，这只是在竞赛中的小伎俩罢了。
Copyright © 2020 Powered by MWeb, Theme used GitHub CSS.