程序员经验分享-hwhale

系统掌握数据结构8 树与二叉树 第二节

2023-11-13

1. 线索二叉树的逻辑结构

线索二叉树要解决什么问题？我们之前学习了先序、中序、后序、层次遍历，可是当给出一个节点时，我们如何知道概节点的下一个是哪个？上一个是哪个？其实就是将树结构线性化，我们不知道前驱和后继，必须遍历才能知道，下次寻找还要再遍历一次，正好之前我们提到完全二叉树的空指针域是n+1个，正好可以被利用记录遍历的前驱后继，以后就不用在遍历了。

线索二叉树的定义：
1）若节点有左子树，则lchild指向左孩子；否则lchild指向其前驱。

2）若节点有右子树，则rchild指向有孩子；否则rchild指向其后继。

为了避免混淆，需要添加两个标志标记是否有左子树、是否有右子树。所以节点变为如下形式。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YZega1fT-1649823769042)(树与二叉树 2节.assets/p19.png)]

规定，

若ltag=0，表示lchild指向左子树，若ltag=1，表示lchild指向前驱；

若rtag=0，表示rchild指向右子树，若rtag=1，表示rchild指向后继；

2. 线索二叉树的物理结构

#define ElemType char
#define OK 1
#define ERROR 0
#define Status int

typedef struct ThreadNode {
	ElemType data;
	ThreadNode* lchild;
	ThreadNode* rchild;
	int ltag;
	int rtag;
}ThreadNode, * ThreadTree;

3. 中序线索二叉树

3.1 逻辑结构

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-apw36HS0-1649823769043)(树与二叉树 2节.assets/p20.png)]

如图就是一棵中序遍历线索二叉树，注意thrt是为了方便设置的头节点，我们暂时不考虑，只有叶子节点的左右链域是指向前驱和后继的，那如何再这棵树的节点上找到前驱和后继呢？

以图中的+节点举例找后继：+节点的rtag为0，所以有右子树，根据中序遍历的规则，其右子树中序遍历的第一个节点即是+节点的后继，所以我们顺着左指针找下去即可找到一个节点没有左孩子，即ltag=1，这就是+号节点的后继，b节点。

以图中的根节点-号节点举例找前驱，（根节点不是头节点），根节点的ltag=0,所以存在左子树，根据中序遍历的规则，其左子树遍历的最后一个节点即是根节点的前驱，我们通过遍历左子树找到其前驱。

头节点：我们令头节点的lchild指向根节点，rchild指向中序遍历的最后一个节点，令中序遍历的第一个节点的lchild指向头节点，中序遍历的最后一个节点的rchild指向根节点，这样我们就可以根据头节点实现正序、反序遍历这棵线索二叉树了。

3.2 代码实现

我们首先写一个中序创建普通二叉树的代码，然后对它进行线索化，第一节我们学习过创建二叉树的代码，只要稍微修改即可,把参数的BiTree换位ThreadTree：

// - + a # # * b # # - c # # d # # / e # # f # #
//是先序创建上面那棵树的输入，但是前两个/是注释别输入进去了
Status CreateTreeByPreOrder(ThreadTree& T) {
	ElemType e;
	cin >> e;
	if (e == '#') {
		T = NULL;
	}
	else {
		T = (ThreadNode*)malloc(sizeof(ThreadNode));
		if (!T) {
			cout << "申请内存错误！" << endl;
			exit(1);
		}
		T->data = e;
		CreateTreeByPreOrder(T->lchild);
		CreateTreeByPreOrder(T->rchild);
	}
	return OK;
}

然后我们将一棵树中序线索化：设置一个pre为p的前驱，pre初始化为头节点时pre不需要建立后继，只需要p建立前驱为pre，其他情况pre若没右孩子则建立后继为p，p若无左孩子则建立前驱为pre。

Status InThread(ThreadTree &p, ThreadTree &pre,ThreadTree thrt) {

	if (p != NULL) {
		InThread(p->lchild, pre, thrt);
		if (p->lchild) {
			p->ltag = 0;
		}
		else {
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != thrt) {
			if (pre->rchild) {
				pre->rtag = 0;
			}
			else {
				pre->rchild = p;
				pre->rtag = 1;
			}
		}
		pre = p;
		InThread(p->rchild, pre, thrt);
	}
	return OK;
}
ThreadTree CreateInThread(ThreadTree T) {
	ThreadTree pre = NULL,thrt=NULL;
	thrt = (ThreadNode*)malloc(sizeof(ThreadNode));//头节点
	if (!thrt) {
		cout << "申请内存错误" << endl;
		exit(1);
	}
	thrt->lchild = T;					//头节点左链指向根节点
	thrt->ltag = 0;
	thrt->data = '#';					//方便识别头节点

	pre = thrt;							//设为头节点使得第一个节点的前驱是头节点
	InThread(T, pre, thrt);
	pre->rchild = thrt;					//最后一个节点后继为头节点
	pre->rtag = 1;

	thrt->rchild = pre;					//头节点右链指向最后一个节点
	thrt->rtag = 1;
	return thrt;
}

然后我们写一个遍历线索二叉树的方法：
首先要写一个找一棵树最左子树的方法方便找后继

ThreadTree InOrderFirstNode(ThreadTree p) {
	while (p->lchild) p = p->lchild;
	return p;
}

然后我们实现找一个节点后继的方法：

ThreadTree InOrdernextNode(ThreadTree p) {//返回p的后继节点
	if (p->rtag == 0) {
		return FirstNode(p->rchild);
	}
	else {
		return p->rchild;
	}
}

然后我们就可以遍历线索二叉树了：

Status InOrderThread(ThreadTree thrt) {
	ThreadTree p = InOrderFirstNode(thrt->lchild);//从第一个节点开始
	while (p != thrt) {
		visit(p);
		p = InOrdernextNode(p);
	}
	return OK;
}

我们实现一个找前驱的方法甚至可以倒着遍历：

/*寻找子树中序最后一个节点*/
ThreadTree InOrderLastNode(ThreadTree p, ThreadTree root) {
	ThreadTree pre = NULL;
	while (p != root) {
		pre = p;
		p = InOrdernextNode(p);
	}
	return pre;
}
/*寻找节点的前驱*/
ThreadTree InOrderPreNode(ThreadTree p) {
	if (p->ltag == 0) {
		return InOrderLastNode(p->lchild, p);
	}
	else {
		return p->lchild;
	}
}
/*逆向中序遍历*/
Status reverseInOrderThread(ThreadTree thrt) {
	ThreadTree p = thrt->rchild;
	while (p != thrt) {
		visit(p);
		p = InOrderPreNode(p);
	}
	return OK;
}

4. 先序线索二叉树

我们考虑如何在先序线索二叉树中找后继？
如果节点有左孩子，左孩子必然是后继，如果节点没有做孩子有右孩子，那右孩子是后继，若都没有则右链域指向的是后继。

那如何找前驱？

若有左孩子则：如果节点是双亲节点的左孩子，双亲节点必然是前驱；

​ 如果是双亲节点的右孩子则前驱是双亲结点的左子树先序遍历的最后一个节点是前驱；

​ 如果是根节点则无前驱；

若无左孩子则：左链指向前驱。

由此我们必须知道节点的双亲，采用三叉链表存储结构的二叉树可以方便的找到双亲。我们将在后面实现先序线索二叉树。

5. 后序线索二叉树

如何在后序线索二叉树中找后继？
若节点没有右孩子：右链域指向后继。

若节点有右孩子：该节点若是二叉树的根，则无后继；

​ 该节点若是双亲节点的右孩子，或者是双亲节点的左孩子且双亲没有右孩子，则双亲节点是后继；

​ 该节点若是双亲结点的左孩子且双亲节点有右孩子，则右子树后序遍历的第一个节点是后继；

如何在后序线索二叉树中找前驱？

若节点没有左孩子：左链域指向前驱；

若节点有左孩子且没有右孩子：后序遍历左子树的最后一个节点是前驱；

若节点有左孩子且有右孩子：后序遍历右子树的最后一个节点是前驱；

由此我们知道，后序线索二叉树也必须用三叉链表来存储。

6. 三叉链表的物理结构

#define Status int
#define OK 1
#define ERROR 0
#define ElemType char

typedef struct BiPNode {
	ElemType data;
	BiPNode* parent = NULL;
	BiPNode* lchild;
	BiPNode* rchild;
}BiPNode,*BiPTree;

但是我们需要对三叉链表斤建立线索，所以线索二叉树的三叉链表物理结构如下：

#define Status int
#define OK 1
#define ERROR 0
#define ElemType char

typedef struct BiPNode {
	ElemType data;
	BiPNode* parent = NULL;
	BiPNode* lchild;
	BiPNode* rchild;
	int ltag;
	int rtag;
}BiPNode,*BiPTree;

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PGpCgwbf-1649823769044)(树与二叉树 2节.assets/p21.png)]

7. 先序线索二叉树的三叉链表存储实现

7.1 先序遍历创建一棵二叉树

在创建节点后，由该节点去找孩子，让孩子认双亲。相比于二叉链表只多了两行代码。

Status CreatBiPTreePreOrder(BiPTree &T) {
	ElemType e;
	cin >> e;
	if (e == '#') T = NULL;
	else {
		T = (BiPNode*)malloc(sizeof(BiPNode));
		if (!T) {
			cout << "申请内存错误！" << endl;
			exit(1);
		}
		T->data = e;
		CreatBiPTreePreOrder(T->lchild);
		CreatBiPTreePreOrder(T->rchild);
		if (T->lchild) T->lchild->parent = T;
		if (T->rchild) T->rchild->parent = T;
	}
	return OK;
}
//- + a # # * b # # - c # # d # # / e # # f # #
//先序创建上面的例子树的输入，从-开始

然后我们写个例子实验一下：

/*先序遍历二叉树*/
Status PreOrderBiPTree(BiPTree T) {
	if (T) {
		cout << T->data;
		cout << "\t";

		PreOrderBiPTree(T->lchild);
		PreOrderBiPTree(T->rchild);
	}
	return OK;
}
/*找到元素e节点返回给p*/
Status check(ElemType e, BiPTree T,BiPTree &q) {
	if (T) {
		if (T->data == e) {
			q = T;
		}
		check(e, T->lchild, q);
		check(e, T->rchild, q);
	}
	return OK;
}


int main() {
	BiPTree T;
	cout << "先序创建二叉树：" << endl;
	CreatBiPTreePreOrder(T);
	PreOrderBiPTree(T);
	/*检查一下*节点的双亲是否是+ */
	cout << "" << endl;
	BiPTree p;
	check('*', T, p);//获得*节点
	cout << p->data;
	cout << "节点的双亲是："<< endl;
	cout << p->parent->data << endl;
	
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FI8N5TIt-1649823769044)(树与二叉树 2节.assets/p22.png)]

7.2 二叉树的先序线索化

中序先遍历p的左子树，然后修改p的前驱，pre的后继，再遍历p的右子树。

而先序先修改p的前驱和pre的后继，再遍历时可能出现访问的是前驱后继而不是左右子树的情况

Status createThredBiPNodePre(BiPTree& p, BiPTree& pre) {
	if (p) {
		if (p->lchild) {
			p->ltag = 0;
		}
		else {
			p->lchild = pre;//左链指向前驱
			p->ltag = 1;
		}
		if (pre->rchild) {
			pre->rtag = 0;
		}
		else {
			pre->rchild = p;	//即使pre是头节点也没关系，我们在执行后会在CreateThreadBIPTreePre修改的
			pre->rtag = 1;
		}
		pre = p;
		if (p->ltag == 0) createThredBiPNodePre(p->lchild, pre);
		//防止左链被修改为前驱 限制有左孩子才遍历左子树
		if(p->rtag == 0)createThredBiPNodePre(p->rchild, pre);
		//防止右链被修改为后继 限制有有孩子才遍历右子树
	}
	return OK;
}

BiPTree CreateThreadBIPTreePre(BiPTree T) {
	BiPTree pre, thrt;
	thrt = (BiPNode*)malloc(sizeof(BiPNode));
	if (!thrt) {
		cout << "申请内存错误！" << endl;
		exit(1);
	}

	thrt->lchild = T;//头节点左链指向根节点；
	thrt->ltag = 0;  //根节点作为头结点的左孩子
	thrt -> data = '#';
	pre = thrt;		//前驱节点赋值头节点，使得第一个节点的前驱指向头节点

	createThredBiPNodePre(T,pre);

	thrt->rchild = pre; //头节点右链指向最后一个节点
	thrt->rtag = 1;
	pre->rchild = thrt;	//最后一个节点后继为头节点
	pre->rtag = 1;
	return thrt;
}

7.3 遍历先序线索二叉树

首先实现一个找节点后继的方法：

/*先序后继*/
BiPTree nextBiPNode(BiPTree p) {
	if (p->ltag == 0) {//有左孩子，左孩子必然是后继
		return p->lchild;
	}
	else {				//无左孩子，有右孩子右孩子是后继没有右链指向后继
		return p->rchild;
	}
}

然后是遍历算法：

Status BiPTreePreOrder(BiPTree p,BiPTree thrt) {
	while (p != thrt) {
		cout << p->data;
		cout << "\t";

		p = nextBiPNode(p);
	}
	return OK;
}

小实验如下：

int main() {
	BiPTree T,thrt;
	
	cout << "先序创建二叉树：" << endl;
	CreatBiPTreePreOrder(T);
	PreOrderBiPTree(T);
	cout << "" << endl;
	thrt = CreateThreadBIPTreePre(T);
	cout << "遍历线索二叉树" << endl;
	BiPTreePreOrder(thrt->lchild, thrt);

}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KvymemT7-1649823769045)(树与二叉树 2节.assets/p23.png)]

7.4 逆向遍历

三叉链表在先序遍历的用处就是找前驱了，先实现一个找前驱的方法：

/*返回root左子树先序遍历的最后一个节点*/
BiPTree preLastBiPNode(BiPTree root) {
	BiPTree p = root->lchild,pre=root;
	while (p != root->rchild) {
		pre = p;
		p = nextBiPNode(p);
	}
	return pre;
}
/*返回节点的前驱*/
BiPTree preBiPNode(BiPTree p) {
	if (p->ltag == 1) {
		return p->lchild;
	}
	else {
		if (p == p->parent->lchild) {
			return p->parent;
		}
		else {
			if (p == p->parent->rchild) {
				return preLastBiPNode(p->parent);
			}
		}
	}
}

然后我们实现遍历算法：

Status reverseBiPTreePreOrder(BiPTree p, BiPTree thrt) {
	while (p != thrt) {
		cout << p->data;
		cout << "\t";

		p = preBiPNode(p);
	}
	return OK;
}

小实验：

int main() {
	BiPTree T,thrt;
	
	cout << "先序创建二叉树：" << endl;
	CreatBiPTreePreOrder(T);
	PreOrderBiPTree(T);
	cout << "" << endl;
	thrt = CreateThreadBIPTreePre(T);
	cout << "正向遍历线索二叉树" << endl;
	BiPTreePreOrder(thrt->lchild, thrt);
	cout << "" << endl;
	cout << "正向遍历线索二叉树" << endl;
	reverseBiPTreePreOrder(thrt->rchild, thrt);

}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-R9XM5JZD-1649823769046)(../../图片/数据结构/树/p24.png)]

8. 后序线索二叉树的三叉链表存储实现

在先序中我们已经完整的实现了三叉链表存储二叉树，后序遍历也是一样的道理，只要熟记找前驱和后继的方法即可。代码稍微改动就好了。

（树与二叉树第三节：）

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

系统掌握数据结构8 树与二叉树 第二节 的相关文章

随机推荐

  • 软件设计师笔记 2021年下半年

    软件设计师笔记 1 第一章 计算机知识 控制器包含 地址寄存器 S single M multiple I 指令流 Data 数据流 2 第二章

  • 【状态估计】基于UKF、AUKF的电力系统负荷存在突变时的三相状态估计研究（Matlab代码实现）

    欢迎来到本博客 博主优势 博客内容尽量做到思维缜密 逻辑清晰 为了方便读者 座右铭 行百里者 半于九十 本文目录如下 目录 1 概述 2 运行结果 3 参考文献 4 Matlab代码及数据 1 概述 基于UKF和AUKF的电力系统负荷存在突

  • ARM发布Cortex-X1，是为了向苹果自研A系列处理器发起冲击吗？

    对于Arm来说 2019年是伟大的一年 这一年ARM的Cortex内核依然是手机CPU领域的佼佼者 特别是Cortex A77 红极一时的高通骁龙865处理器采用的就是Cortex A77 据说采用骁龙865处理器的手机有70款之多 其中就

  • c语言文件处理中ab,C语言文件处理中wt是什么操作方式？

    匿名用户 1级 2013 04 25 回答 最常用的文件使用方式及其含义如下 1 r 为读而打开文本文件 不存在则出错 2 rb 为读而打开二进制文件 3 w 为写而打开文本文件 若不存在则新建 反之 则从文件起始位置写 原内容将被覆盖 4

  • 【中间件】Redis如何解决BigKey

    BigKey 的弊端 BigKey 需要解决 根源就在于 BigKey 会带来的问题 占用内存 因为 Redis 数据结构的底层数据结构 大 Key 会占用更多的内存空间 造成更大的内存消耗 单线程模型 因为 Redis 的通信依赖于 So

  • 一文看懂web服务器、应用服务器、web容器、反向代理服务器区别与联系

    我们知道 不同肤色的人外貌差别很大 而双胞胎的辨识很难 有意思的是Web服务器 Web容器 Web应用程序服务器 反向代理有点像四胞胎 在网络上经常一起出现 本文将带读者对这四个相似概念如何区分 Web服务器概念与基本原理 Web服务器的历

  • CSS基础之CSS文本属性

    文章目录 前言 1 color 2 text align 3 font size 4 text decoration 5 text indent 6 line height 7 文本属性总结 前言 CSS 文本属性可以设置文本的 外观 比如

  • 从同源政策到跨域解决方法

    一 同源政策 同源政策的目的 是为了保证用户信息的安全 防止恶意的网站窃取数据 所谓同源指的是协议 域名 端口相同 否则就会产生跨域问题 二 跨域 跨域问题主要分为三类 1 Cookie LocalStorage 和 IndexDB 无法读

  • 记一次jQuery EasyUI使用-Easyui combobox的使用方法

    开局附上最最最有用的官方文档 划重点 easyui使用手册 进入正题 现象 有这样一段代码 浏览器请求getSystemSignList方法有返回数据并且严格符合easyui的应答规范 一个json格式的list对象 tr td class

  • 大模型讲习班丨第四范式黄世宇：强化学习的发展历程与基于人类反馈的强化学习...

    人工智能研究与应用范式正经历一场剧变 越来越多的顶级团队和杰出人才纷纷加入这一变革浪潮 作为AI大模型科研先锋 智源研究院携手一批卓越的学者与工程师 致力于将尖端技术与经验传授给有潜力的学习者 通过高效的学习方式 让更多人能迅速融入这一重要

  • MobileNet网络结构详解

    下图展示了传统卷积与DW卷积的差异 在传统卷积中 每个卷积核的channel与输入特征矩阵的channel相等 每个卷积核都会与输入特征矩阵的每一个维度进行卷积运算 而在DW卷积中 每个卷积核的channel都是等于1的 每个卷积核只负责输

  • Python-安装库-图像处理库-cv2

    问题 在pycharm中搜索cv2库 发现没有版本 在网上查找资料 找到了类似官方文档的资料 提到了安装方法 https pypi org project opencv python description cv2介绍 CV2指的是Open

  • ERROR 1064 (42000): You have an error in your SQL syntax

    mysql使用load data infile导入数据 出现如下错误 root NoName 21 19 12 gt load data infile change csv into table change CHARACTER SET u

  • JAVA基础知识点大全之二

    1 泛型 1 1 泛型类 定义格式 修饰符 class 类名 lt 类型 gt 1 2 泛型方法 定义格式 修饰符 lt 类型 gt 返回值类型 方法名 类型 变量名 1 3 泛型接口 定义格式 修饰符 interface 接口名 lt 类

  • c/c++多线程编程（1）：线程的创建

    参考资料 多线程和线程同步 C C 运行环境 wsl2 Ubuntu 20 04 vscode clangd xmake gcc9 4 0 1 创建线程 1 1 线程函数 每个线程都有一个属于自己的线程id id的类型为phtread t

  • 解决centos 8命令ip add无效问题

    之前用Xshell连接虚拟机一直正常 突然一台节点总是连不上 查询众多资料后 终于找到了问题所在 出错情况 输入命令 root node01 service NetworkManager start root node01 nmcli ne

  • 图腾柱电路工作原理

    图腾柱就是上下各一个晶体管 上管为NPN c极接正电源 下管为PNP e极接负电源 注意 是负电源 是地 两个b极接到一起 接输入 上管的e和下管的c接到一起 接输出 用来匹配电压 或者提高IO口的驱动能力 有几种图腾柱电路的变种 一种是两

  • Log4j2安全 JNDI漏洞 CVE-2021-44228

    Apache Log4j2是基于Java的日志记录工具 工具重写了Log4j框架 并且引入了大量丰富特性 该日志框架被大量用于业务系统开发 用来记录日志信息 大多数情况下 开发者可能会将用户输入导致的错误信息写入日志中 因该组件使用极为广泛

  • linux内核态发送tcp包,Linux内核发送构造数据包的方式

    本文欢迎自由转载 但请标明出处 并保证本文的完整性 作者 Godbach 日期 2009 09 01 一 构造数据包简析 这里并不详细介绍如何在内核中构造数据包 下文如有需要会在适当的位置进行分析 这里简单的分析讲一下内核态基于Netfil

  • 系统掌握数据结构8 树与二叉树 第二节

    树与二叉树 2节 1 线索二叉树的逻辑结构 2 线索二叉树的物理结构 3 中序线索二叉树 3 1 逻辑结构 3 2 代码实现 4 先序线索二叉树 5 后序线索二叉树 6 三叉链表的物理结构 7 先序线索二叉树的三叉链表存储实现 8 后序线索

热门标签