当前位置: 首页 > news >正文

第五章 树与二叉树 四、线索树(手算与代码实现)

一、定义

1.线索树是一种二叉树,它在每个节点上增加了两个指针,分别指向其前驱和后继。

2.这些指针称为“线索”,因此线索树也叫做“线索化二叉树”。

3.在线索树中,所有的叶子节点都被线索化,使得遍历树的过程可以更加高效地进行。

4.同时,线索树可以在O(1)的时间复杂度内找到任意节点的前驱和后继,而不需要遍历整个树。

二、存储结构(链式存储)

typedef struct BiNode{int data;struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;typedef struct ThreadNode{int data;struct ThreadNode *lchild,*rchild;int ltag,rtag;//左右线索标志
}ThreadNode,*ThreadTree;

ltag==1时,表示lchild指向前驱;

ltag==0时,表示lchild指向左孩子;

rtag==1时,表示rchild指向后继;

rtag==0时,表示rchild指向右孩子;

三、三种线索二叉树

1、手算线索二叉树

(1)中序线索二叉树

1.首先使用中序遍历为每个结点标上序号

2.我们跟着序号来画线索,首先判断D结点,它的没有前驱结点,所以它的前驱线索指向NULL,后继指针指向G

3.接着判断序号为2的结点G,它的前驱是D,后继是B

4.结点B的前驱是G,后继是E,但是在步骤三3中已经找到了它的前驱,而且结点B的指针已经有指向的结点了,所以不能再分配线索指针。

5.依此类推得到中序线索二叉树

(2)先序线索二叉树

1.步骤和中序相同,最重要的就是给结点打上序号,而且要把每个结点的左右孩子指针用完

(3)后序线索二叉树

1.直接上答案,同时要记住一个原则,左孩子指针指向该节点的前驱,右孩子指针指向后继。

(左前驱,右后继)

2、代码实现线索二叉树

(1)中序线索二叉树

#include "stdio.h"
#include "stdlib.h"typedef struct ThreadNode {char data;struct ThreadNode *lchild, *rchild;int ltag, rtag; // 左右线索标志
} ThreadNode, *ThreadTree;ThreadTree pre = NULL; // 使用单一指针void visit(ThreadNode *q) {if (q->lchild == NULL) {q->lchild = pre;q->ltag = 1;}if (pre != NULL && pre->rchild == NULL) {pre->rchild = q;pre->rtag = 1;}pre = q; // 直接赋值给 pre,不需要解引用
}// 中序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T) {if (T != NULL) {InThread(T->lchild); // 中序遍历左子树visit(T); // 访问根节点InThread(T->rchild); // 中序遍历右子树}
}void CreateInThread(ThreadTree T) {pre = NULL;if (T != NULL) {InThread(T);if (pre->rchild == NULL) {pre->rtag = 1;}}
}

(2)先序线索二叉树

#include "stdio.h"
#include "stdlib.h"typedef struct ThreadNode {char data;struct ThreadNode *lchild, *rchild;int ltag, rtag; // 左右线索标志
} ThreadNode, *ThreadTree;ThreadTree pre = NULL; // 使用单一指针void visit(ThreadNode *q) {if (q->lchild == NULL) {q->lchild = pre;q->ltag = 1;}if (pre != NULL && pre->rchild == NULL) {pre->rchild = q;pre->rtag = 1;}pre = q; // 直接赋值给 pre,不需要解引用
}// 先序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T) {if (T != NULL) {visit(T); // 访问根节点if(T->ltag == 0)                                    //判断是否为前驱线索InThread(T->lchild); // 中序遍历左子树InThread(T->rchild); // 中序遍历右子树}
}void CreateInThread(ThreadTree T) {pre = NULL;if (T != NULL) {InThread(T);if (pre->rchild == NULL) {pre->rtag = 1;}}
}

(3)后序线索二叉树

#include "stdio.h"
#include "stdlib.h"typedef struct ThreadNode {char data;struct ThreadNode *lchild, *rchild;int ltag, rtag; // 左右线索标志
} ThreadNode, *ThreadTree;ThreadTree pre = NULL; // 使用单一指针void visit(ThreadNode *q) {if (q->lchild == NULL) {q->lchild = pre;q->ltag = 1;}if (pre != NULL && pre->rchild == NULL) {pre->rchild = q;pre->rtag = 1;}pre = q; // 直接赋值给 pre,不需要解引用
}// 后序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T) {if (T != NULL) {InThread(T->lchild); // 中序遍历左子树InThread(T->rchild); // 中序遍历右子树visit(T); // 访问根节点}
}void CreateInThread(ThreadTree T) {pre = NULL;if (T != NULL) {InThread(T);if (pre->rchild == NULL) {pre->rtag = 1;}}
}

相关文章:

第五章 树与二叉树 四、线索树(手算与代码实现)

一、定义 1.线索树是一种二叉树,它在每个节点上增加了两个指针,分别指向其前驱和后继。 2.这些指针称为“线索”,因此线索树也叫做“线索化二叉树”。 3.在线索树中,所有的叶子节点都被线索化,使得遍历树的过程可以…...

服务器前后端学习理解

个人兴趣,突然想起来记录一下 1. 背景 想做一个最简单的网页,点击按钮后,访问服务器的redis数据库,读取一个为hello的值并显示 首先用js写了一个脚本,使用redis包,读取到了数据,并使用consol.l…...

python-数据分析-numpy、pandas、matplotlib的常用方法

一、numpy import numpy as np1.numpy 数组 和 list 的区别 输出方式不同 里面包含的元素类型 2.构造并访问二维数组 使用 索引/切片 访问ndarray元素 切片 左闭右开 np.array(list) 3.快捷构造高维数组 np.arange() np.random.randn() - - - 服从标准正态分布- - - …...

ChatGPT⼊门到精通(5):ChatGPT 和Claude区别

⼀、Claude介绍 Claude是Anthropic开发的⼀款⼈⼯智能助⼿。 官⽅⽹站: ⼆、Claude能做什么 它可以通过⾃然语⾔与您进⾏交互,理解您的问题并作出回复。Claude的主要功能包括: 1、问答功能 Claude可以解答⼴泛的常识问题与知识问题。⽆论是历史上的某个事件,理科…...

ChatGPT 总结数据分析的所有知识点

ChatGPT功能非常多,特别是对某个行业,某个方向,某个技术进行总结那是相当专业的。 如下图。 直接用一个指令便总结出来数据分析当中的所有知识点内容。 AIGC ChatGPT ,BI商业智能, 可视化Tableau, PowerBI, FineReport, 数据库Mysql Oracle, Office, Python ,ETL Ex…...

hadoop-HDFS

1.HDFS简介 2.1 Hadoop分布式文件系统-HDFS架构 2.2 HDFS组成角色及其功能 (1)Client:客户端 (2)NameNode (NN):元数据节点 管理文件系统的Namespace元数据 一个HDFS集群只有一个Active的NN &#xff…...

0202hdfs的shell操作-hadoop-大数据学习

文章目录 1 进程启停管理2 文件系统操作命令2.1 HDFS文件系统基本信息2.2 介绍2.3 创建文件夹2.4 查看指定文件夹下的内容2.5 上传文件到HDFS2.6 查看HDFS文件内容2.7 下载HDFS文件2.8 HDFS数据删除操作 3 HDFS客户端-jetbrians产品插件3.1 Big Data Tools 安装3.2 配置windows…...

生活小记-挂号信

"挂号信"通常指的是在邮寄过程中通过挂号邮寄服务寄送的信件,相对于普通信件有一些特殊的特点和服务。以下是挂号信与其他信件(例如普通信件)之间的区别: 跟踪和确认: 挂号信:通过挂号邮寄服务寄…...

3D点云处理:基于PCA的计算点云位姿(占位待整理)

文章目录 文章目录:3D视觉个人学习目录微信:dhlddxB站: Non-Stop_...

本地私有仓库、harbor私有仓库部署与管理

本地私有仓库、harbor私有仓库部署与管理 一、本地私有仓库1.本地私有仓库简介2.搭建本地私有仓库3.容器重启策略介绍 二、harbor私有仓库部署与管理1.什么是harbor2.Harbor的特性3.Harbor的构成4.harbor部署及配置5.客户端测试 三、Harbor维护1.创建2.普通用户操作私有仓库3.日…...

尚硅谷SpringMVC (5-8)

五、域对象共享数据 1、使用ServletAPI向request域对象共享数据 首页&#xff1a; Controller public class TestController {RequestMapping("/")public String index(){return "index";} } <!DOCTYPE html> <html lang"en" xmln…...

jupyter notebook中查看python版本的解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...

动态字符串 String (完整源码)

C自学精简教程 目录(必读) C数据结构与算法实现&#xff08;目录&#xff09; 本文的实现基本上和 动态数组 vector 是一样的。 因为大部分接口都一样。 所以&#xff0c;本文就直接给出全部的源码和运行结果。 //------下面的代码是用来测试你的代码有没有问题的辅助代码…...

【深度学习】实验05 构造神经网络示例

文章目录 构造神经网络1. 导入相关库2. 定义一个层3. 构造数据集4. 定义基本模型5. 变量初始化6. 开始训练 构造神经网络 注明&#xff1a;该代码用来训练一个神经网络&#xff0c;网络拟合y x^2-0.5noise&#xff0c;该神经网络的结构是输入层为一个神经元&#xff0c;隐藏层…...

用了这么久SpringBoot却还不知道的一个小技巧

前言 你可能调第三方接口喜欢启动application&#xff0c;修改&#xff0c;再启动&#xff0c;再修改&#xff0c;顺便还有个不喜欢写JUnitTest的习惯。 你可能有一天想要在SpringBoot启动后&#xff0c;立马想要干一些事情&#xff0c;现在没有可能是你还没遇到。 那么SpringB…...

Websocket、SessionCookie、前端基础知识

目录 1.Websocket Websocket与HTTP的介绍 不同使用场景 Websocket链接过程 2.Session&Cookie Cookie的工作原理 Session的工作原理 区别 3.前端基础知识 1.Websocket Websocket与HTTP的介绍 HTTP&#xff1a; 1.HTTP是单向的&#xff0c;客户端发送请求&#xff0…...

【云原生进阶之PaaS中间件】第一章Redis-2.4缓存更新机制

1 缓存和数据库的数据一致性分析 1.1 Redis 中如何保证缓存和数据库双写时的数据一致性&#xff1f; 无论先操作db还是cache&#xff0c;都会有各自的问题&#xff0c;根本原因是cache和db的更新不是一个原子操作&#xff0c;因此总会有不一致的问题。想要彻底解决这种问题必须…...

Qt——事件处理详解

Qt事件处理 一、事件基础 事件是Qt应用程序中的基本构建块&#xff0c;它们代表了一些特定的行为或状态变化。事件可以是鼠标点击、键盘输入、窗口大小改变、定时器事件等。每个事件都是一个对象&#xff0c;继承自QEvent类。 二、事件常见类型 Qt中的事件分为多种类型&…...

基于位置管理的企业员工考勤打卡系统设计 微信小程序

员工考勤打卡系统设计app是针对员工必不可少的一个部分。在公司发展的整个过程中&#xff0c;员工考勤打卡系统设计app担负着最重要的角色。为满足如今日益复杂的管理需求&#xff0c;各类员工考勤打卡系统设计app程序也在不断改进。本课题所设计的 MVC基于HBuilder X的员工考勤…...

adb 查找应用包名,应用 Activity 等信息

列出设备上的包 不使用参数&#xff1a;adb shell pm list packages&#xff0c;打印设备/模拟器上的所有软件包 根据包名查看应用的activity 命令&#xff1a; dumpsys package 包名 adb shell dumpsys package 包名 petrel-cv96d:/data/app # dumpsys package com.instal…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...