数据结构:二叉树的遍历和线索二叉树

二叉树的遍历

二叉树的遍历是二叉树的一种重要的操作,指按照某种顺序访问树中的每个节点,并且每个节点仅被访问一次。常见的遍历方式有四种:前序遍历、中序遍历、后序遍历和层次遍历(或称为广度优先遍历)。

二叉树的定义类型:

typedef struct
{ElemType data;struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
  1. 前序遍历(Preorder Traversal)

首先访问根节点,然后递归地进行前序遍历左子树,最后递归地进行前序遍历右子树。

//pre
void preorder(BiTree T){if(T!=NULL){visit(T);preorder(T->lchild);preorder(T->rchild);}
}

非递归算法:

void preorder2(BiTree T){InitStack(S);BiTree p=t;if(p||isEmpty(S)){if (p){visit(p);push(S,p);p=p->lchild;}else{pop(S,p);p=p->rchild;}}
}
  1. 中序遍历(Inorder Traversal)

首先递归地进行中序遍历左子树,然后访问根节点,最后递归地进行中序遍历右子树。

void inorder(BiTree T){if(T!=NULL){inorder(T->lchild);visit(T);inorder(T->rchild)}
}

非递归算法:

void inprder2(BiTree T){InitStack(S);BiTree P=T;if(p||isEmpty(S)){if(P){push(S,P);P=P->lchild;}else{pop(S,P);visit(P);P=P->rchild;}}
}

 

  1. 后序遍历(Postorder Traversal)

首先递归地进行后序遍历左子树,然后递归地进行后序遍历右子树,最后访问根节点。

void postorder(BiTree T){if(T!=NULL){postorder(T->lchild);postorder(T->rchild);visit(T);}
}
  1. 层次遍历(Level-order Traversal)

从上到下、从左到右依次访问树的每个节点。这通常需要使用队列来实现。

void levelorder(BiTree T){InitQueue(Q);BiTree p;EnQueue(Q,T);while(isEmpty(Q)){DeQueue(Q,p);visit(p);if(p->lchild)EnQueue(Q,p->lchild);else if(p->rchild)EnQueue(p->rchild);}
}

线索二叉树(存储结构)

线索二叉树是二叉树的一种变种,主要用于解决二叉树在遍历过程中“指针空域”的浪费问题。在普通二叉树中,每个节点有两个指针域,分别指向左右子节点,但在很多情况下,这两个指针域可能为空,这些空指针域就称为“空域”。线索二叉树就是将这些空域利用起来,存储指向该节点在某种遍历次序下的前驱和后继节点的指针(或线索)。

线索二叉树的实现
  1. 线索化:将二叉树中的空指针域改为线索的过程称为线索化。根据遍历方式的不同,可以构造出前序线索二叉树、中序线索二叉树和后序线索二叉树。

//线索二叉树定义的类型
typedef struct{`ElemType data;struct TreadNode * lchild,*rchild;int ltag,rtag;
}ThreadNode,*ThreadTree;//中序遍历线索化二叉树
void inthread(ThreadTree &p,ThreadTree &pre){if(p!=NULL){inthread(p->lchild,pre);if(p->lchild==NULL){p->lchild=pre;p->ltag=1;}if(pre!=NULL&&pre->rchild==NULL){pre->rchild=p;pre->rtag=1;}pre=p;inthread(p->rchild,pre);}
}//中序遍历构造线索二叉树
void createinorder(ThreadTree T){ThreadTree pre=NULL;if(T!=NULL){inthread(T,pre);pre->rchild=NULL;pre->rtag=1;}}//求线索二叉树的第一个结点
ThreadNode *FirstNode(ThreadNode *T){while(T->ltag!=1){T=T->lchild;}return T;
}//求线索二叉树的结点的下一个结点
ThreadNode *NextNode(ThreadNode *T){if(T->rtag==0)return FirstNode(T->rchild);elsereturn T->rchild;
}//中序遍历线索二叉树
void inorder(ThreadNode *T){for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p)){visit(p);}
}
  1. 线索的表示

    • 引入两个布尔标志,ltag 和 rtag,分别表示左指针域和右指针域是否为线索。若 ltag=1,则 lchild 指向前驱;若 ltag=0,则 lchild 指向左子树。同理,若 rtag=1,则 rchild 指向后继;若 rtag=0,则 rchild 指向右子树。
  2. 遍历:在中序线索二叉树中,从根节点开始,若 ltag=1,则直接通过 lchild 访问前驱节点;否则,递归遍历左子树。遍历完左子树后,访问根节点,然后根据 rtag 决定是否直接通过 rchild 访问后继节点或递归遍历右子树。

线索二叉树的优点
  • 节省空间:不需要额外的空间来存储遍历的结果。
  • 简化遍历:通过线索,可以快速找到前驱和后继节点,无需回溯。
  • 引入线索二叉树的目的是加快查找结点前驱和后继的速度。
线索二叉树的缺点
  • 空间利用率:虽然节省了指针空域,但增加了 ltag 和 rtag 的存储开销。
  • 灵活性:线索二叉树只能适应一种遍历方式,如果需要其他遍历方式,需要重新线索化。

注意:

后续线索二叉树上找后继时需要知道双亲结点,即需采用带标志域的三叉链表作为存储结构。

线索二叉树是数据结构中一种高效利用空间并简化遍历操作的方法,特别适用于需要频繁遍历但不修改树结构的场景。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1548719.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

物联网系统中LCD屏主流驱动方案详解

01 物联网系统中为什么要使用LCD驱动芯片 在物联网系统中使用LCD驱动芯片的原因主要有以下几点: 节省资源 1、减少IO端口占用:在物联网设备中,单片机或其他主控芯片的IO资源通常非常有限。LCD驱动芯片可以通过简单的接口(如SP…

基于Hive和Hadoop的白酒分析系统

本项目是一个基于大数据技术的白酒分析系统,旨在为用户提供全面的白酒市场信息和深入的价格分析。系统采用 Hadoop 平台进行大规模数据存储和处理,利用 MapReduce 进行数据分析和处理,通过 Sqoop 实现数据的导入导出,以 Spark 为核…

jenkins项目发布基础

随着软件开发需求及复杂度的不断提高,团队开发成员之间如何更好地协同工作以确保软件开发的质量已经慢慢成为开发过程中不可回避的问题。Jenkins 自动化部署可以解决集成、测试、部署等重复性的工作,工具集成的效率明显高于人工操作;并且持续集成可以更早的获取代码变更的信息,…

从Linux系统的角度看待文件-基础IO

目录 从Linux系统的角度看待文件 系统文件I/O open write read 文件操作的本质 vim中批量注释的方法 从Linux系统的角度看待文件 关于文件的共识: 1.空文件也要占用磁盘空间 2.文件内容属性 3.文件操作包括文件内容/文件属性/文件内容属性 4.文件路径文…

【Qt】前后端交互---DataCenter类

设计目的 前后端交互系统中,创建并使用数据核心类的目的就是让该类作为客户端的数据中心,也就是说其负责管理客户端的所有数据与服务器的网络通信。 数据持久化 初始化数据文件 该函数设计的目的就是用于检查所需要的文件和目录是否存在,如…

短视频矩阵系统源码开发/矩阵系统OEM搭建--源代码开发经验分享

短视频矩阵系统开发策略 短视频矩阵系统源码的原生开发方法 一、基于原生技术的短视频矩阵系统开发途径 原生编程语言:采用各平台专有的编程语言及开发工具,如iOS平台的Swift或Objective-C,以及平台的Java或Kotlin,确保应用性能与…

[贪心+数学/数学+位运算] 两种方法O(1)解决 消减整数

标题:[贪心数学/数学位运算] 两种方法O(1)解决 消减整数 个人主页水墨不写bug 目录 一、题目:消减整数(Newcoder) 二、题目分析 1.理解题意: 2.解决问题 解法详解一:贪心数学 解法一参考代码: 解法详解二&#xf…

WiFi无线连接管理安卓设备工具:WiFiADB

介绍 WiFi ADB 使您能够通过 WiFi TCP/IP 连接直接在设备上轻松调试和测试 Android 应用,无需使用 USB 数据线。在启用 WiFi 上的 ADB 后,打开控制台将电脑连接到设备。 手机和电脑在同一个WiFi然后电脑上运行adb connect x.x.x.x:x命令即可 下载 谷…

MindSearch 部署到Github Codespace 和 Hugging Face Space

和原有的CPU版本相比区别是把internstudio换成了github codespace。 教程是https://github.com/InternLM/Tutorial/blob/camp3/docs/L2/MindSearch/readme_github.md 复现步骤: 根据教材安装环境和创建硅基流动 API 然后启动前后端 然后按照教材部署到 Huggi…

一站式家装服务管理系统

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本一站式家装服务管理系统就是在这样的大环境下诞生,其可以帮助管理者在短时间内处理完毕庞大的数…

基于Hive和Hadoop的病例分析系统

本项目是一个基于大数据技术的医疗病历分析系统,旨在为用户提供全面的病历信息和深入的医疗数据分析。系统采用 Hadoop 平台进行大规模数据存储和处理,利用 MapReduce 进行数据分析和处理,通过 Sqoop 实现数据的导入导出,以 Spark…

《征服数据结构》哈夫曼树(Huffman Tree)

摘要: 1,哈夫曼树的介绍 2,哈夫曼树的构造 3,哈夫曼树带权路径长度计算 4,哈夫曼树的编码 5,哈夫曼树的解码 1,哈夫曼树的介绍 哈夫曼树(Huffman Tree)也叫霍夫曼树,或者赫夫曼树&am…

学校周赛(1)

A - Short Sort 题目: 思路: 本条题目只允许改一处地方,只有三个字母,我们可以直接枚举所有移动过的结果,同时使用哈希去记录其值,对于每一个输入我们都寻找是否有这个值记录,有则输出YES否则…

微深节能 环形运动机械定位控制系统 格雷母线

微深节能的环形运动机械定位控制系统中的格雷母线,是一种高精度、无磨损的非接触式位置检测系统,特别适用于环形运动机械的定位控制。该系统主要由格雷母线、天线箱、电气柜等关键部件组成,其核心在于格雷母线这一特殊的编码线。 格雷母线概述…

JAVA一站式台球学习平台多端畅享助教教练系统小程序源码

​一站式台球学习平台 —— 多端畅享助教教练系统 🌟【开篇:解锁台球新境界】🌟 你是否厌倦了传统台球学习的枯燥与局限?想要随时随地,都能享受专业级的台球指导吗?今天,就让我为你揭秘一款颠覆…

JITWatch安装使用方法

JITWatch 版本1.4.2 JDK 版本 11以上 1.下载JITWatch: https://github.com/AdoptOpenJDK/jitwatch/releases/download/1.4.2/jitwatch-ui-1.4.2-shaded-win.jar 2.启动 bat脚本执行:通过启动jar包方式启动JITWatch echo off start cmd /c "ti…

SpringBoot+Activiti7工作流入门实例

目录 文章目录 目录准备Activiti建模工具1、BPMN-js在线设计器1.1 安装1.2 使用说明1.3运行截图 2、IDEA安装Activiti Designer插件2.1安装插件2.2 设置编码格式防止中文乱码2.3 截图 简单工作流入门实例1. 新建Spring Boot工程2. 引入Activiti相关依赖添加版本属性指定仓库添加…

探索分布式IO模块的介质冗余:赋能工业自动化的稳健之心

在日新月异的工业自动化领域,每一个细微环节的稳定性都直接关系到生产线的效率与安全。随着智能制造的深入发展,分布式IO(Input/Output)模块作为连接现场设备与控制系统的关键桥梁,其重要性日益凸显。我们自主研发的带…

RAG+llamaindex+DSW实操

本文纯干货,不做任何原理性讲解,适合于有一定基础的伙伴进行实践,本次文章将分为以下几个部分来介绍: 环境搭建LlamaIndex 使用本地知识库准备基本原理: 1. 环境搭建 1.1 配置基础环境 创建虚拟环境,环境名称可以自行取,我的是"llamaindex" conda create -n ll…

「iOS」——KVC

iOS学习 前言KVC模式KVC设值KVC取值KVC使用keyPathKVC处理异常处理不存在的key处理nil异常 KVC处理字典KVC高阶消息传递 总结 前言 对KVC模式的简单学习和总结。 KVC模式 KVC(Key-Value Coding,键值编码)是一种通过字符串来访问对象属性的机…