考研二战_数据结构_day11_线索二叉树_先序前驱怎么找

目录

前言

一、线索树

1 基本概念

2 中序线索化

3 先序线索化

4 后序线索化

二、找前驱、后继

1 中序找后继

2 中序找前驱

3 先序找后继

4 先序找前驱

5 后序找后继

6 后序找前驱

7 小结

 后记

---

前言

        线索树的代码属于想起来很复杂，但是实现起来就非常简单的东西。主要是在实现过程中需要注意不要转圈、以及是否需要处理最后一个结点。

---

一、线索树

1 基本概念

        有N个结点的二叉树中，会有N+1个空链域（推理出来的），可以把这些空的链域用来存储前驱与后继。

2 中序线索化

        线索化就是在对结点进行visit操作时，顺便完成的操作。线索化过程中，最重要的就是找到当前结点的前驱线索，以及前一个结点的后继线索。

        换句话说，线索化分为两部分操作，一个处理当前结点，一个处理上一个访问的结点。因此可以定义一个指针pre，用于表示上一个访问的结点，初始置为NULL；除此以外，为了将结点的线索指针与孩子指针相区别，还可以定义一个Ltag与Rtag，用0表示孩子结点，用1表示线索结点。

        如上图所示，这是中序线索化后的结果，黄色线表示前驱线索，紫色表示后继线索。在线索化过程中记当前结点名为root：

        1、若root->LNode == NULL，则将其线索化，将root的左孩子指针指向pre；

        2、若pre->RNode == NULL，则将其线索化，将pre的右孩子指针指向root；

        3、将pre指向root。

typedef int ElemType;
 
typedef struct TreeNode {
	ElemType data;
	struct TreeNode *LNode, *RNode;
	int Ltag, Rtag;
} BiNode, *BiTree;
 
BiNode *pre = NULL;  //定义全局变量pre
 
void Thread(BiNode* root) {
	root->Ltag = 0;
	root->Rtag = 0;
	if(root->LNode == NULL) {
		root->LNode = pre;
		root->Ltag = 1;
	}
	if(pre != NULL && pre->RNode == NULL) {
		pre->RNode = root;
		pre->Rtag = 1;
	}
	pre = root;
}
 
bool MidThread(BiNode* root) {
	if(root) {
		MidThread(root->LNode);
        Thread(root);
		MidThread(root->RNode);
	}
	return true;
}
 
int main() {
	//定义一棵空树
	BiTree root = NULL;
 
    /*中间省略构建过程*/
 
	MidThread(root);
	if(pre->RNode == NULL) {  //处理最后一个结点
		pre->Rtag = 1;
	}
 
	return 0;
}

        如代码所示，线索化过程与遍历过程可以说一模一样，只是需要注意处理最后一个结点。

3 先序线索化

         与先序遍历方式一样，但是若是不经过修改，出现如下情况时会出现转圈现象。

出现转圈的主要原因是：当访问结点B的左孩子结点时，由于已经对结点B进行了线索化，导致左孩子指针已经是线索指针了，因此只有当左孩子指针不为线索指针时，才能使用递归，访问其左孩子结点。

bool PreThread(BiNode* root) {
	if(root) {
		Thread(root);
		if(root->Ltag == 0) {
			PreThread(root->LNode);
		}
		PreThread(root->RNode);
	}
}
 
int main() {
    PreThread(root);
	if(pre->RNode == NULL) {  //处理最后一个结点
		pre->Rtag = 1;
	}
    return 0;
}

4 后序线索化

        根据先序线索化，是因为在访问结点的左孩子结点时，其指针已经是线索指针，才会导致转圈的问题，这种情况是先序特有。考虑访问右孩子结点时，由于并不会对当前结点的右孩子指针进行线索化，而是对上一个结点的右孩子指针进行线索化，所以不需要考虑当前结点已经线索化。

        因此后序遍历怎么遍历，后序线索化就怎么线索化，注意最后一个结点的处理即可。

bool PreThread(BiNode* root) {
	if(root) {
		Thread(root);
		if(root->Ltag == 0) {
			PreThread(root->LNode);
		}
		PreThread(root->RNode);
	}
}
 
int main() {
    PostThread(root);
	if(pre->RNode == NULL) {  //处理最后一个结点
		pre->Rtag = 1;
	}
    return 0;
}

---

二、找前驱、后继

        在二叉树已经线索化的基础上，如何快速找到一个结点的前驱、后继？如何进行遍历？

1 中序找后继

        在使用中序线索化后，若需要找到一个结点 p 的后继会有两种情况：

        1、p->Rtag == 1，线索指针，其后继一定是右孩子指针指向结点（也可能是NULL）；

        2、p->Rtag == 0，未线索化，说明其右子树，则需要找到右子树最左边的结点即可。

//找到root为根结点的树中序遍历的第一个结果
BiNode* FirstNode(BiNode* root) {
	while(root->Ltag == 0) root = root->LNode;
	return root;
}
 
//找到root的后继结点 
BiNode* NextNode(BiNode* root) {
	if(root->Rtag == 1) return root->RNode;
	else return FirstNode(root->RNode);
}
 
//使用中序线索化进行中序遍历 
void MidVisit(BiTree root) {
	for(BiNode* p = FirstNode(root); p != NULL; p = NextNode(p)) {
		visit(p);
	}
}

2 中序找前驱

        中序找前驱方法与中序找后继的方法一模一样。

//找到root为根结点的树中序遍历的最后一个结果
BiNode* LastNode(BiNode* root) {
	while(root->Rtag == 0) root = root->RNode;
	return root;
}
 
//找到root的前驱结点 
BiNode* PreNode(BiNode* root) {
	if(root->Ltag == 1) return root->LNode;
	else return LastNode(root->LNode);
}
 
//使用中序线索化进行中序遍历（倒置顺序）
void MidVisit2(BiTree root) {
	for(BiNode* p = LastNode(root); p != NULL; p = PreNode(p)) {
		visit(p);
	}
}

3 先序找后继

        依旧是两种情况：

        1、当root->Rtag == 1时，后继为其右孩子结点

        2、当root->Rtag == 0时，必有右孩子结点，此时分为两种小情况：

                （1）存在左孩子结点，后继即是左孩子结点

                （2）不存在左孩子结点，后继则是右孩子结点

        总结一下，就是若存在左孩子结点，则后继是左孩子结点；否则就是右指针指向结点。

BiNode* PreNextNode(BiNode* root) {
	if(root->Ltag == 0) return root->LNode;
	else return root->RNode;
}
 
void PreVisit(BiTree root){
	for(BiNode* p = root; p != NULL; p = PreNextNode(p)){
		visit(p);
	}
}

4 先序找前驱

        除非使用三叉树，即除了左右指针，还有一个指向父结点的指针，不然很难找到先序线索化的树中任一结点的前驱。

        还是分为两种情况：

        1、root->Ltag == 1，则当前结点的前驱为其左指针指向结点。

        2、root->Ltag == 0，则当前结点必有左孩子结点，但是先序遍历情况下，当前结点的所有子结点一定不可能是其前驱。故需要分为4种情况分析

                （1）当前结点是根结点，不存在前驱

                （2）当前结点有父结点，且当前结点是左孩子结点，则其前驱是父结点。

                （3）当前结点有父结点，且当前结点是右孩子结点，且无兄弟结点，则其前驱是父结点

                （4）当前节点不仅是父结点的右孩子结点，也存在兄弟节点，则其前驱为兄弟节点先序遍历的最后一个结点。

        虽然说是有4种情况来考虑，但是首先要找到当前结点的父结点，所以只能通过遍历，有点麻烦，所以我就只是看看原理，就不实现了。

5 后序找后继

        后序找后继与先序找前驱一个原理，也是极难找到。

        1、当root->Rtag == 1时，当前结点的后继即是其右指针指向结点。

        2、当root->Rtag == 0时，当前结点必有右孩子结点，但是在后序遍历的情况下，当前结点的所有子结点一定不可能是其后继。依旧分为四种情况：

                （1）当前结点是根结点，不存在后继

                （2）当前结点有父结点，且当前结点是右孩子结点，则其后继是父结点。

                （3）当前结点有父结点，且当前结点是左孩子结点，且无兄弟结点，则其后继是父结点

                （4）当前节点不仅是父结点的左孩子结点，也存在兄弟节点，则其前驱为兄弟节点后序遍历的第一个结点。

        虽然说是有4种情况来考虑，但是首先要找到当前结点的父结点，所以只能通过遍历，有点麻烦，所以我就只是看看原理，就不实现了。

6 后序找前驱

        分为两种情况考虑：

        1、当root->Ltag == 1时，当前结点的前驱结点就是其左指针指向结点。

        2、当root->Ltag == 0时，当前结点必有左孩子结点，依旧分为两种小情况：

                （1）存在右孩子结点，前驱即是右孩子结点

                （2）不存在右孩子结点，前驱则是左孩子结点

        总结一下，就是若存在右孩子结点，则后继是右孩子结点；否则就是左指针指向结点。

BiNode* PostPreNode(BiNode* root) {
	if(root->Rtag == 0) return root->RNode;
	else return root->LNode;
}
 
//后序遍历的倒置 
void PostVisit(BiTree root) {
	for(BiNode* p = root; p != NULL; p = PostPreNode(p)) {
		visit(p);
	}
}

7 小结

        根据线索二叉树寻找前驱、后继时，先序不能找前驱，后序不能找后继（除非使用三叉链表或者从头遍历）。虽然我并没有进行实现，但是先找前，后找后是如何找的，一定要会推理出来。

---

 后记

        线索化主要就先序线索化时要注意不要绕圈。

        先序线索化很难找前驱，后序线索化很难找后继，难在要找到当前结点的父结点；但是要会推理出如何寻找的4种情况。

        明天定个小目标，看到哈夫曼树。