数据结构与算法——第6章-树-使用线索二叉树遍历(6.10.3)

发表于 2023-03-25 分类于开发， N-数据与算法，数据结构与算法阅读时长 ≈ 3 分钟

一概述

1.二叉树图示
2.线索二叉树情况分析
3.后续遍历3种情况
4.示例代码

二二叉树图示

1
2
3

图 3 中是一个按照中序遍历建立的线索二叉树。
其中，实线表示指针，指向的是左孩子或者右孩子。
虚线表示线索，指向的是该结点的直接前趋或者直接后继。

三线索二叉树情况分析

使用线索二叉树时，会经常遇到一个问题，
如图 3 中，结点 b 的直接后继直接通过指针域获得，为结点 * ；
而由于结点 * 的度为 2 ，无法利用指针域指向后继结点，整个链表断掉了。
当在遍历过程，遇到这种问题是解决的办法就是：寻找先序、中序、后序遍历的规律，找到下一个结点。

在先序遍历过程中，如果结点因为有右孩子导致无法找到其后继结点，如果结点有左孩子，则后继结点是其左孩子；
否则，就一定是右孩子。
拿图 3 举例，结点 + 的后继结点是其左孩子结点 a ，如果结点 a 不存在的话，就是结点 * 。

在中序遍历过程中，结点的后继是遍历其右子树时访问的第一个结点，也就是右子树中位于最左下的结点。
例如图 3 中结点 * ，后继结点为结点 c ，是其右子树中位于最左边的结点。
反之，结点的前趋是左子树最后访问的那个结点。

四后续遍历3种情况

后序遍历中找后继结点需要分为 3 种情况：
1. 如果该结点是二叉树的根，后继结点为空；
2. 如果该结点是父结点的右孩子（或者是左孩子，但是父结点没有右孩子），后继结点是父结点；
3. 如果该结点是父结点的左孩子，且父结点有右子树，后继结点为父结点的右子树在后序遍历列出的第一个结点。

使用后序遍历建立的线索二叉树，在真正使用过程中遇到链表的断点时，
需要访问父结点，所以在初步建立二叉树时，宜采用三叉链表做存储结构。

五示例代码

5.1 遍历线索二叉树非递归代码实现：

//中序遍历线索二叉树
void InOrderThraverse_Thr(BiThrTree p) {
	while(p) {
		//一直找左孩子，最后一个为中序序列中排第一的
		while(p->Ltag == Link) {
			p = p->lchild;
		}
		printf("%c ", p->data); //操作结点数据
		//当结点右标志位为 1 时，直接找到其后继结点
		while(p->Rtag == Thread && p->rchild !=NULL) {
			p = p->rchild;
			printf("%c ", p->data);
		}
		//否则，按照中序遍历的规律，找其右子树中最左下的结点，也就是继续循环遍历
		p = p->rchild;
	}
}

5.2 完整代码

#include <stdio.h>
#include <stdlib.h>
#define TElemType char//宏定义，结点中数据域的类型
//枚举，Link 为 0，Thread 为 1
typedef enum {
	Link,
	Thread
} PointerTag;
//结点结构构造
typedef struct BiThrNode {
	TElemType data;//数据域
	struct BiThrNode* lchild,*rchild;//左孩子，右孩子指针域
	PointerTag Ltag,Rtag;//标志域，枚举类型
} BiThrNode,*BiThrTree;
BiThrTree pre=NULL;
//采用前序初始化二叉树
//中序和后序只需改变赋值语句的位置即可
void CreateTree(BiThrTree * tree) {
	char data;
	scanf("%c",&data);
	if (data!='#') {
		if (!((*tree)=(BiThrNode*)malloc(sizeof(BiThrNode)))) {
			printf("申请结点空间失败");
			return;
		} else {
			(*tree)->data=data;//采用前序遍历方式初始化二叉树
			CreateTree(&((*tree)->lchild));//初始化左子树
			CreateTree(&((*tree)->rchild));//初始化右子树
		}
	} else {
		*tree=NULL;
	}
}
//中序对二叉树进行线索化
void InThreading(BiThrTree p) {
	//如果当前结点存在
	if (p) {
		InThreading(p->lchild);//递归当前结点的左子树，进行线索化
		//如果当前结点没有左孩子，左标志位设为 1，左指针域指向上一结点 pre
		if (!p->lchild) {
			p->Ltag=Thread;
			p->lchild=pre;
		}
		//如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。
		if (pre&&!pre->rchild) {
			pre->Rtag=Thread;
			pre->rchild=p;
		}
		pre=p;//pre 指向当前结点
		InThreading(p->rchild);//递归右子树进行线索化
	}
}
//中序遍历线索二叉树
void InOrderThraverse_Thr(BiThrTree p) {
	while(p) {
		//一直找左孩子，最后一个为中序序列中排第一的
		while(p->Ltag == Link) {
			p = p->lchild;
		}
		printf("%c ", p->data); //操作结点数据
		//当结点右标志位为 1 时，直接找到其后继结点
		while(p->Rtag == Thread && p->rchild !=NULL) {
			p = p->rchild;
			printf("%c ", p->data);
		}
		//否则，按照中序遍历的规律，找其右子树中最左下的结点，也就是继续循环遍历
		p = p->rchild;
	}
}
int main() {
	BiThrTree t;
	printf("输入前序二叉树:\n");
	CreateTree(&t);
	InThreading(t);
	printf("输出中序序列:\n");
	InOrderThraverse_Thr(t);
	return 0;
}

运行结果

输入前序二叉树:
124###35##6##
输出中序序列:
4 2 1 5 3 6

六参考

C语言中文网—线索二叉树

0%