树--搜索二叉树

现有一棵结点数目为n的二叉树,采用二叉链表的形式存储。对于每个结点均有指向左右孩子的两个指针域,而结点为n的二叉树一共有n-1条有效分支路径。那么,则二叉链表中存在2n-(n-1)=n+1个空指针域。那么,这些空指针造成了空间浪费。

例如:图2.1所示一棵二叉树一共有10个结点,空指针^有11个。

此外,当对二叉树进行中序遍历时可以得到二叉树的中序序列。例如:图2.1所示二叉树的中序遍历结果为HDIBJEAFCG,可以得知A的前驱结点为E,后继结点为F。但是,这种关系的获得是建立在完成遍历后得到的,那么可不可以在建立二叉树时就记录下前驱后继的关系呢,那么在后续寻找前驱结点和后继结点时将大大提升效率。

线索化

现将某结点的空指针域指向该结点的前驱后继,定义规则如下:

若结点的左子树为空,则该结点的左孩子指针指向其前驱结点。

若结点的右子树为空,则该结点的右孩子指针指向其后继结点。

这种指向前驱和后继的指针称为线索。将一棵普通二叉树以某种次序遍历,并添加线索的过程称为线索化。

按照规则将图2.1所示二叉树线索化后如图所示:

图中黑色点画线为指向后继的线索,紫色虚线为指向前驱的线索。

可以看出通过线索化,既解决了空间浪费问题,又解决了前驱后继的记录问题。

线索化带来新问题

可以将一棵二叉树线索化为一棵线索二叉树,那么新的问题产生了。我们如何区分一个结点的lchild指针是指向左孩子还是前驱结点呢?例如:对于图所示的结点E,如何区分其lchild的指向的结点J是其左孩子还是前驱结点呢?

为了解决这一问题,现需要添加标志位ltag,rtag。并定义规则如下:

ltag为0时,指向左孩子,为1时指向前驱

rtag为0时,指向右孩子,为1时指向后继

添加ltag和rtag属性后的结点结构如下:

上图所示线索二叉树转变为图所示的二叉树。

答案:b

线索二叉树结点数据结构

//#define Link 0//指针标志  
//#define Thread 1//线索标志  
typedef char TElemType;   
//中序线索二叉树  
typedef enum PointerTag {Link, Thread};//结点的child域类型,link表示是指针,指向孩子结点,thread表示是线索,指示前驱或后继结点  
//定义结点数据结构
typedef struct ThrBiNode{  TElemType data;  ThrBiNode *lchild, *rchild;//左右孩子指针  PointerTag lTag, rTag;//左右标志  
}ThrBiNode, *ThrBiTree;  

中序遍历建立线索二叉树

中序遍历的方法已经在第一篇二叉基础树中讲解过,那么实现线索化的过程就是在中序遍历同时修改结点空指针的指向。

采用中序遍历的访问顺序实现一棵二叉树的线索化过程代码如下:

//中序遍历进行中序线索化
void inThreading(ThrBiTree T, ThrBiTree &pre){  if(T){  inThreading(T->lchild, pre);//左子树线索化  if(!T->lchild){//当前结点的左孩子为空  T->lTag = Thread;  T->lchild = pre;  }else{  T->lTag = Link;  }  if(!pre->rchild){//前驱结点的右孩子为空  pre->rTag = Thread;  pre->rchild = T;  }else{  pre->rTag = Link;  }  pre = T;          inThreading(T->rchild, pre);//右子树线索化  }  
}  

加上头结点,遍历线索二叉树

加上线索的二叉树结构是一个双向链表结构,为了便于遍历线索二叉树,我们为其添加一个头结点,头结点左孩子指向原二叉树的根结点,右孩子指针指向中序遍历的最后一个结点。同时,将第一个结点左孩子指针指向头结点,最后一个结点的右孩子指针指向头结点。

上图所示线索二叉树添加头结点后如图所示:

带有头结点的线索二叉树遍历代码如下:

//T指向头结点,头结点的lchild链域指针指向二叉树的根结点  
//中序遍历打印二叉线索树T(非递归算法)  
void inOrderTraversePrint(ThrBiTree T){  ThrBiNode *p = T->lchild;//p指向根结点  while(p != T){//空树或遍历结束时,p == T  while(p->lTag == Link){  p = p->lchild;  }  //此时p指向中序遍历序列的第一个结点(最左下的结点)  printf("%c ", p->data);//打印(访问)其左子树为空的结点  while(p->rTag == Thread && p->rchild != T){  p = p->rchild;  printf("%c ", p->data);//访问后继结点  }  //当p所指结点的rchild指向的是孩子结点而不是线索时,p的后继应该是其右子树的最左下的结点,即遍历其右子树时访问的第一个节点  p = p->rchild;  }  printf("\n");  
}  

结语

线索二叉树充分利用了指针空间,同时又便于寻找结点的前驱结点和后继结点。线索二叉树适用于经常需要遍历寻找结点前驱或者后继结点的二叉树。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

通过vlan实现同一网段下的网络隔离

现有两个电脑通过交换机直接连接在一起 pc1&#xff1a; pc2&#xff1a; 正常状态下是可以ping成功的 现在先进入交换机命令行界面&#xff0c;创建两个vlan <Huawei>system-view Enter system view, return user view with CtrlZ. [Huawei]vlan 10 [Huawei-vlan10…

python基础知识总结(第一节)

一、python简介&#xff1a; Python是一种解释型&#xff0c;面向对象的高级语言。 Pyhton的语法和动态类型&#xff0c;以及解释性语言的本质&#xff0c;使它一跃成为多数平台上写脚本和快速开发应用的编程语言。 python语言百度百科介绍 二、Python基础语法&#xff1a;…

交换机的三层交换技术

现有pc1与pc2不在同一个网段之下&#xff0c;通过交换机相连接。 进人交换机1&#xff0c;创建两个vlan 10和vlan 20 &#xff0c;进入串口2设置串口模式为access&#xff0c;并且设置默认vlan为10.进入串口3设置串口模式为access&#xff0c;并且设置默认vlan为20. 进入串口1…

操作系统真象还原:完善MBR

第3章-完善MBR 这是一个网站有所有小节的代码实现&#xff0c;同时也包含了Bochs等文件 编译器给程序中各符号&#xff08;变量名或函数名等&#xff09;分配的地址&#xff0c;就是各符号相对于文件开头的偏移量 。 section 称为节&#xff0c;在有的编译器中&#xff0c;同…

做视频号小店和达人对接的好,爆单少不了!

大家好&#xff0c;我是喷火龙。 目前&#xff0c;视频号是没有什么自然流量的&#xff0c;所以&#xff0c;想要出单、爆单的话&#xff0c;靠达人带货的方式才是最可靠的&#xff0c;靠达人带货是肯定要对接达人&#xff0c;并和达人沟通带货的。 下面给大家讲一讲应该怎么…

【Python】解决Python报错:TypeError: unsupported operand type(s) for ...

&#x1f9d1; 博主简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟&#xff0c;欢迎关注。提供嵌入式方向…

Kafka原生API使用Java代码-生产者-分区策略-默认分区策略轮询分区策略

文章目录 1、代码演示1.1、pom.xml1.2、KafkaProducerPartitioningStrategy.java1.2.1、ProducerConfig.LINGER_MS_CONFIG取 0 值得情况&#xff0c;不轮询1.2.2、ProducerConfig.LINGER_MS_CONFIG取 0 值得情况&#xff0c;轮询1.2.3、ProducerConfig.LINGER_MS_CONFIG取 1000…

前端应用开发实验:表单控件绑定

目录 实验目的相关知识点实验内容代码实现效果 实验目的 &#xff08;1&#xff09;熟练掌握应用v-model指令实现双向数据绑定的方法&#xff0c;学会使用 v-model指令绑定文本框、复选框、单选按钮、下拉菜单&#xff1b; &#xff08;2&#xff09;学会值绑定&#xff08;将…

Java枚举

引入&#xff1a; 当有一些类&#xff0c;希望它的成员的值是具体的有限的值&#xff0c;且只读不需要修改&#xff0c;不希望用户去自定义其他的值。 比如季节类&#xff0c;它的成员只能是春夏秋冬&#xff0c;不希望用户构造其他的值。 枚举enum&#xff1a; 枚举是一组的特…

SQL数据库多层嵌套 json转sql建表语句,SQL数据库里数组里对象数据怎么创建

1. uniapp sqlite 一个数组包含对象嵌套对象通过主外键方式插入数据库&#xff1a; // 假设有一个对象数组&#xff0c;对象中包含嵌套对象 const objectsArray [{parentObject: {id: 1,name: Parent 1,// 其他父对象属性},childObject: {id: 11,parentId: 1,name: Child 1 o…

字符串操作:写一个方法,实现字符串的反转,如:输入abc,输出cba

import java.util.Scanner; public class Test_A15 {public static void main(String[] args){String strA"";System.out.println("请输入一串字符串:");Scanner scannernew Scanner(System.in);strAscanner.next();Test_A15 T15new Test_A15();String re…

使用 LangFuse 意外被挂马!我是怎么恢复系统稳定的?

在使用 LangFuse 过程中,被意外挂马!通过一番折腾服务恢复正常~ 本文将详细介绍应对恶意脚本和进程的完整方案,包括识别、清理、恢复和预防步骤。 阿里云扫到的信息 被执行的 Base64 SUlaQnRTCmV4ZWMgJj4vZGV2L251bGwKSUhDa0hQbmQ9Li8uJChkYXRlfG1kNXN1bXxoZWFkIC1jMjApCl…

AI Agent智能体概述及原理

AI Agent概述 AI Agent旨在理解、分析和响应人类输入&#xff0c;像人类一样执行任务、做出决策并与环境互动。它们可以是遵循预定义规则的简单系统&#xff0c;也可以是根据经验学习和适应的复杂、自主的实体&#xff1b;可以是基于软件的实体&#xff0c;也可以是物理实体。…

行为型设计模式之模板模式

文章目录 概述原理结构图实现 小结 概述 模板方法模式(template method pattern)原始定义是&#xff1a;在操作中定义算法的框架&#xff0c;将一些步骤推迟到子类中。模板方法让子类在不改变算法结构的情况下重新定义算法的某些步骤。 模板方法中的算法可以理解为广义上的业…

【YOLOv5/v7改进系列】引入AKConv——即插即用的卷积块

一、导言 介绍了一种名为AKConv&#xff08;Alterable Kernel Convolution&#xff09;的新型卷积操作&#xff0c;旨在解决标准卷积操作存在的两个根本性问题。首先&#xff0c;标准卷积操作受限于局部窗口&#xff0c;无法捕获来自其他位置的信息&#xff0c;且其采样形状固…

Facebook隐私保护:数据安全的前沿挑战

在数字化时代&#xff0c;随着社交媒体的普及和应用&#xff0c;个人数据的隐私保护问题日益受到关注。作为全球最大的社交平台之一&#xff0c;Facebook承载了数十亿用户的社交活动和信息交流&#xff0c;但与此同时&#xff0c;也面临着来自内外部的数据安全挑战。本文将深入…

玄机平台应急响应—Linux入侵排查

1、前言 这篇文章主要说一下linux的入侵排查&#xff0c;也就是说当你的服务器已经被入侵的时候&#xff0c;该如何去排查使其恢复正常。下面是排查的步骤&#xff0c;但是实际情况往往更为复杂&#xff0c;需要进一步来分析&#xff0c;而不是无脑的按照步骤来敲就完事了。 …

【FPGA】Verilog语言从零到精通

接触fpga一段时间&#xff0c;也能写点跑点吧……试试系统地康康呢~这个需要耐心但是回报巨大的工作。正原子&&小梅哥 15_语法篇&#xff1a;Verilog高级知识点_哔哩哔哩_bilibili 1Verilog基础 Verilog程序框架&#xff1a;模块的结构 类比&#xff1a;c语言的基础…

07 FreeRTOS 事件组(event group)

1、事件组概念 1.1 基本概念 使用事件组可以等待某个事件、若干事件中的任意一个事件、若干事件中的所有事件&#xff0c;但是不能指定若干事件中的某些事件。 事件组可以简单地认为就是一个整数&#xff1a;这个整数的每一位表示一个事件&#xff1b;每一位事件的含义由程序员…

常用的优化器汇总及keras实现

1.SGD&#xff08;Stochastic Gradient Descent&#xff09; 2.RMSprop&#xff08;Root Mean Square Propagation&#xff09; 3.Adadelta 4.Adam&#xff08;Adaptive Moment Estimation&#xff09; 5.Nadam 6.代码实现 from sklearn.compose import make_column_transforme…