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

数据结构:线索二叉树

目录

        1.线索二叉树是什么?

        2.包含头文件

        3.结点设计

        4.接口函数定义

        5.接口函数实现


线索二叉树是什么?

        线索二叉树(Threaded Binary Tree)是一种对普通二叉树的扩展,它通过在树的某些空指针上添加线索来实现更高效的遍历操作。线索二叉树的目的是减少查找特定节点(如前驱或后继节点)所需的时间,从而提高树的搜索效率。以下是线索二叉树的特点:

        1.普通二叉树的扩展:线索二叉树是基于普通二叉树的,它保留了二叉树的所有性质。

        2.线索:在二叉树的空指针(左子树或右子树的指针)上添加线索,这些线索可以指导我们找到节点的前驱或后继。

        3.前驱和后继:每个节点的前驱是其在中序遍历中直接前的一个节点,后继是直接后的节点。线索二叉树允许我们通过线索快速找到这些节点。


包含头文件

#include<stdio.h>
#include<stdlib.h>

结点设计

#define Initsize 100
typedef char Elemtype;typedef struct ThreadTree {Elemtype data;					//定义Elemtype类型的变量存储结点值struct ThreadTree* lchild;		//定义ThreadTree类型的指针变量lchild存储左子树的地址struct ThreadTree* rchild;		//定义ThreadTree类型的指针变量rchild存储右子树的地址int Lvalue, Rvalue;				//定义int类型的变量Lvalue和Rvalue分别标识线索
}ThreadTree,* ThTree;ThTree Pre = NULL;					//定义ThTree类型的全局变量Pre指向此次结点的前驱结点

接口函数定义

void InitThTree(ThTree& A);				//用于初始化线索二叉树
void InsertTree(ThTree& A);				//用于输入数据建立二叉树
void InOrder(ThTree A);					//用于在二叉树中执行中序遍历
void InOrderVisit(ThTree& A);			//用于在结点中进行中序线索化
void InOrderThread(ThTree& A);			//用于中序遍历线索化二叉树
void PreOrder(ThTree A);				//用于在二叉树中执行先序遍历
void PreOrderVisit(ThTree& A);			//用于先序遍历线索化二叉树
void PreOrderThread(ThTree& A);			//用于先序遍历线索化二叉树
void PostOrder(ThTree A);				//用于执行后序遍历
void PostOrderVisit(ThTree& A);			//用于后序遍历线索化二叉树
void PostOrderThread(ThTree& A);		//用于后序遍历线索化二叉树

接口函数实现


void PostOrderThread(ThTree& A) {	//用于后序遍历线索化二叉树Pre = NULL;if (A != NULL) {PostOrder(A);if (A->rchild == NULL){Pre->Rvalue = 1;}}
}			void PostOrderVisit(ThTree& A) {	//用于后序遍历线索化二叉树if (A->lchild == NULL) {		//若传入的结点的左子树为空,则将该结点的左子树线索化A->Lvalue = 1;A->lchild = Pre;}if (A->rchild == NULL && Pre != NULL) {//若传入的结点的空子树为空,且前驱结点不为空,则将该结点的左子树线索化Pre->rchild = A;Pre->Rvalue = 1;}Pre = A;
}				void PostOrder(ThTree A) {		//用于执行后序遍历if (A != NULL) {PostOrder(A->lchild);PostOrder(A->rchild);PostOrderVisit(A);}
}void PreOrderThread(ThTree& A) { //用于先序遍历线索化二叉树Pre = NULL;								if (A != NULL) {PreOrder(A);if (Pre->rchild == NULL) {Pre->Rvalue = 1;}}
}void PreOrderVisit(ThTree& A) {	 //用于先序遍历线索化二叉树if (A->lchild == NULL) {	 //若传入的结点的左子树为空,则将该结点的左子树线索化A->Lvalue = 1;A->lchild = Pre;}if (A->rchild == NULL && Pre != NULL) {//若传入的结点的空子树为空,且前驱结点不为空,则将该结点的左子树线索化Pre->Rvalue = 1;Pre->rchild = A;}Pre = A;
}void PreOrder(ThTree A)	{		  //用于在二叉树中执行先序遍历if (A != NULL) {PreOrderVisit(A);if (A->Lvalue==0) {PreOrder(A->lchild);}PreOrder(A->rchild);}
}void InOrderThread(ThTree& A) {	  //用于中序遍历线索化二叉树Pre = NULL;					  //遍历第一个结点时,第一个结点无前驱结点,故Pre为NULLif (A != NULL) {InOrder(A);							//进行中序遍历if (Pre->rchild == NULL) {			//将中序遍历的最后一个结点的右子树线索化Pre->Rvalue = 1;				//因为其结点无后继,故不更新指向}}
}void InOrderVisit(ThTree& A) {		//用于在结点中进行线索化if (A->lchild == NULL) {		//左子树若为空,则将其左子树线索化A->Lvalue = 1;A->lchild = Pre;}if (A->rchild == NULL && Pre != NULL) {//右子树若为空,则将其右子树线索化Pre->rchild = A;Pre->Rvalue = 1;}Pre = A;		//更新指向前驱结点的指针pre
}void InOrder(ThTree A) {			//用于在二叉树执行中序遍历if (A!= NULL) {					InOrder(A->lchild);InOrderVisit(A);InOrder(A->rchild);}
}void InsertTree(ThTree& A) {	//用于输入数据建立二叉树ThTree Q[Initsize],		//定义ThTree类型的指针数组存储根结点的地址W = NULL;		//定义Thtree类型的指针W指向新建的结点的地址int i=0,				//定义int类型的变量i作为左右孩子树的标识j=0,				//定义int类型的变量j作为字符串遍历的指针top=-1;				//定义int类型的变量top作为结点数组的指针char E,R[Initsize];printf("请以括号法输入数据,并以此建立二叉树:");scanf_s("%s", R, Initsize);E = R[i];while (E != '\0') {switch (E) {case '(':top++;			 //入栈操作Q[top] = W;i = 1;			//对新结点做标识,1为左子树的标识break;case ',':i = 2;			//对新结点做标识,2为右子树的标识break;case ')':top--;			//出栈操作break;default:W = (ThreadTree*)malloc(sizeof(ThreadTree));		//新建结点W->data = E;					//更新结点的数据域data的指向W->rchild = W->lchild = NULL;if (A == NULL) {				//当传入的结点为空时,则新建的结点为树的根结点A = W;}else {switch (i) {					//判断传入的结点为左子树还是右子树case 1:Q[top]->lchild = W;			//将栈内的根结点的lchild指向新建的地址break;case 2:Q[top]->rchild = W;			//将栈内的根结点的rchild指向新建的地址break;}}}j++;E = R[j];}printf("构建线索二叉树对应的二叉树成功\n");
}void InitThTree(ThTree& A) {	//用于初始化线索二叉树A = NULL;printf("初始化线索二叉树成功\n");
}
http://www.lryc.cn/news/366116.html

相关文章:

  • 宝塔Linux面板-Docker管理(2024详解)
  • 【Linux】进程(8):Linux真正是如何调度的
  • R语言探索与分析14-美国房价及其影响因素分析
  • golang websocket 数据处理和返回JSON数据示例
  • 【Mac】Downie 4 for Mac(视频download工具)兼容14系统软件介绍及安装教程
  • 【操作系统】进程与线程的区别及总结(非常非常重要,面试必考题,其它文章可以不看,但这篇文章最后的总结你必须要看,满满的全是干货......)
  • 自动驾驶仿真(高速道路)LaneKeeping
  • 数据挖掘实战-基于Catboost算法的艾滋病数据可视化与建模分析
  • 分水岭算法分割和霍夫变换识别图像中的硬币
  • 什么是AVIEXP提前发货通知?
  • Python 之SQLAlchemy使用详细说明
  • 就业班 第四阶段(docker) 2401--5.29 day3 Dockerfile+前后段项目若依ruoyi
  • 【运维项目经历|026】Redis智能集群构建与性能优化工程
  • Linux编程for、while循环if判断以及case语句用法
  • docker命令 docker ps -l (latest)命令在 Docker 中用于列出最近一次创建的容器
  • inflight 守恒和带宽资源守恒的有效性
  • 短视频直播教学课程小程序的作用是什么
  • Open AI又出王炸GPT-4,目测一大波人的饭碗要碎了...
  • 8086 汇编笔记(八):转移指令的原理
  • win 系统 cmd 命令从私库上传,下载jar包
  • dots_image 增强图像中的圆点特征
  • 代码随想录算法训练营第十五天| 110.平衡二叉树、 257. 二叉树的所有路径、404.左叶子之和
  • MSP430单片机控制流水灯,Proteus仿真
  • 出售iPhone前的必做步骤:完全擦除个人数据的方法
  • npm yarn 更换国内源以及node历史版本下载地址
  • 微信小程序手机号码授权登录
  • 【网络编程开发】1.网络结构 2.IP地址与端口号 3.字节序
  • 读取文件
  • Allure在jenkins中无法显示的问题
  • 建筑建筑一建考试试题及答案,分享几个实用搜题和学习工具 #其他#职场发展