【数据结构】线索二叉树(适用场景+图文推导过程+C语言代码实现)

这篇具有很好参考价值的文章主要介绍了【数据结构】线索二叉树(适用场景+图文推导过程+C语言代码实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

导读:

普通二叉树(如下图):

  • 空间浪费:存在大量“∧”,该空间未利用。
  • 时间效率:查找一次结点的前驱、后继就需要遍历一次,时间效率低。

线索二叉树,数据结构与算法,数据结构,c语言,c++,算法,线索二叉树、

        在实际问题中,如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表的存储结构就是非常不错的选择。

一、线索二叉树

1.定义

        线索二叉树:指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树就称为线索二叉树(Threaded Binary Tree)。

2.图文推导

        如下图,把这棵二叉树进行中序遍历后,将所有的空指针域中的rchild,改为指向它的后继结点。于是我们就可以通过指针知道H的后继是D(图I的后继是B(图中②),J的后继是E(图中③),E的后继是A(图中④),F的后继是 C(图中⑤),G的后继因为不存在而指向NULL(图中⑥)。此时共有6个空指针域被利用。

线索二叉树,数据结构与算法,数据结构,c语言,c++,算法,线索二叉树、

        再如,我们将这棵二叉树的所有空指针域中的lchild,改为指向当前结点的前驱。因此H的前驱是NULL(图中①),I的前驱是D(图中②),J的前驱是B(图中 ③),F的前驱是A(图中④),G的前驱是C(图中⑤)。一共5个空指针域被利用, 正好和上面的后继加起来是11个。

线索二叉树,数据结构与算法,数据结构,c语言,c++,算法,线索二叉树、

        通过下图(空心箭头实线为前驱,虚线黑箭头为后继),可以看出,其实线索二叉树,等于是把一棵二叉树转变成了一个双向链表,这样对我们的插入删除结点、查找某个结点都带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。

线索二叉树,数据结构与算法,数据结构,c语言,c++,算法,线索二叉树、

改进:        

        我们不知道某一结点的lchild是指向它的左孩子还是指向前驱?rchild是指向右孩子还是指向后继?在决定lchild是指向左孩子还是前驱,rchild是指向右孩子还是后继上是需要一个区分标志。

        每个结点再增设两个标志域ltag和rtag,注意ltag和rtag只是存放0或1数字的布尔型变量,其占用的内存空间要小于像lchild和rchild的指针变量。结点结构如表所示。

线索二叉树,数据结构与算法,数据结构,c语言,c++,算法,线索二叉树、

其中:

        ltag为0时指向该结点的左孩子,为1时指向该结点的前驱。

        rtag为0时指向该结点的右孩子,为1时指向该结点的后继。 

线索二叉树,数据结构与算法,数据结构,c语言,c++,算法,线索二叉树、

二、代码段

1.结构定义代码

/* 二叉树的二叉线索存储结构定义 */
/* Link==0表示指向左右孩子指针 */
/* Thread==1表示指向前驱或后继的线索 */
typedef enum { Link, Thread } PointerTag;
/* 二叉线索存储结点结构 */
typedef struct BiThrNode
{
	/* 结点数据 */
	TElemType data;
	/* 左右孩子指针 */
	struct BiThrNode* lchild, * rchild;
	PointerTag LTag;
	/* 左右标志 */
	PointerTag RTag;
} BiThrNode, * BiThrTree;

 2.中序遍历线索化的递归函数代码如下:

BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{
	if (p)
	{
		/* 递归左子树线索化 */
		InThreading(p->lchild);
		/* 没有左孩子 */
		if (!p->lchild)
		{
			/* 前驱线索 */
			p->LTag = Thread;
			/* 左孩子指针指向前驱 */
			p->lchild = pre;
		}
		/* 前驱没有右孩子 */
		if (!pre->rchild)
		{
			/* 后继线索 */
			pre->RTag = Thread;
			/* 前驱右孩子指针指向后继(当前结点p) */
			pre->rchild = p;
		}
		/* 保持pre指向p的前驱 */
		pre = p;
		/* 递归右子树线索化 */
		InThreading(p->rchild);
	}
}

3.一般遍历

        在二叉树线索链表上添加一个头结点(和双向链表结构一样),其lchild域的指针指向二叉树的根结点(图中的①),其rchild域的指针指向中序遍历时访问的最后一个结点(图中的②)。反之,令二叉树的中序序列中的第一个结点中,lchild域指针和最后一个结点的rchild域指针均指向头结点(图中的③和④)。

        这样定义的好处就是我们既可以从第一个结点起顺后继进行遍历,也可以从最后一个结点起顺前驱进行遍历。

线索二叉树,数据结构与算法,数据结构,c语言,c++,算法,线索二叉树、

 遍历的代码如下:

/* T指向头结点,头结点左链lchild指向根结点,
头结点右链rchild指向中序遍历的 */
/* 最后一个结点。中序遍历二叉线索链表表示的二
叉树T */
Status InOrderTraverse_Thr(BiThrTree T)
{
	BiThrTree p;
	/* p指向根结点 */
	p = T->lchild;
	/* 空树或遍历结束时,p==T */
	while (p != T)
	{
		/* 当LTag==0时循环到中序序列第一个结点 */
		while (p->LTag == Link)
			p = p->lchild;
		/* 显示结点数据,可以更改为其他对结点操作 */
		printf("%c", p->data);
		while (p->RTag == Thread && p->rchild != T)
		{
			p = p->rchild;
			printf("%c", p->data);
		}
		/* p进至其右子树根 */
		p = p->rchild;
	}
	return OK;
}

 三、完整测试代码

  线索二叉树完整测试代码如下:文章来源地址https://www.toymoban.com/news/detail-763094.html

#include "string.h"
#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag;	/* Link=0表示指向左右孩子指针, */
										/* Thread=1表示指向前驱或后继的线索 */
typedef  struct BiThrNode	/* 二叉线索存储结点结构 */
{
	TElemType data;	/* 结点数据 */
	struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */
	PointerTag LTag;
	PointerTag RTag;		/* 左右标志 */
} BiThrNode, *BiThrTree;

TElemType Nil='#'; /* 字符型以空格符为空 */

Status visit(TElemType e)
{
	printf("%c ",e);
	return OK;
}

/* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
/* 0(整型)/空格(字符型)表示空结点 */
Status CreateBiThrTree(BiThrTree *T)
{ 
	TElemType h;
	scanf("%c",&h);

	if(h==Nil)
		*T=NULL;
	else
	{
		*T=(BiThrTree)malloc(sizeof(BiThrNode));
		if(!*T)
			exit(OVERFLOW);
		(*T)->data=h; /* 生成根结点(前序) */
		CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
		if((*T)->lchild) /* 有左孩子 */
			(*T)->LTag=Link;
		CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
		if((*T)->rchild) /* 有右孩子 */
			(*T)->RTag=Link;
	}
	return OK;
}

BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{ 
	if(p)
	{
		InThreading(p->lchild); /* 递归左子树线索化 */
		if(!p->lchild) /* 没有左孩子 */
		{
			p->LTag=Thread; /* 前驱线索 */
			p->lchild=pre; /* 左孩子指针指向前驱 */
		}
		if(!pre->rchild) /* 前驱没有右孩子 */
		{
			pre->RTag=Thread; /* 后继线索 */
			pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
		}
		pre=p; /* 保持pre指向p的前驱 */
		InThreading(p->rchild); /* 递归右子树线索化 */
	}
}

/* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ 
	*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
	if(!*Thrt)
		exit(OVERFLOW);
	(*Thrt)->LTag=Link; /* 建头结点 */
	(*Thrt)->RTag=Thread;
	(*Thrt)->rchild=(*Thrt); /* 右指针回指 */
	if(!T) /* 若二叉树空,则左指针回指 */
		(*Thrt)->lchild=*Thrt;
	else
	{
		(*Thrt)->lchild=T;
		pre=(*Thrt);
		InThreading(T); /* 中序遍历进行中序线索化 */
		pre->rchild=*Thrt;
		pre->RTag=Thread; /* 最后一个结点线索化 */
		(*Thrt)->rchild=pre;
	}
	return OK;
}

/* 中序遍历二叉线索树T(头结点)的非递归算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{ 
	BiThrTree p;
	p=T->lchild; /* p指向根结点 */
	while(p!=T)
	{ /* 空树或遍历结束时,p==T */
		while(p->LTag==Link)
			p=p->lchild;
		if(!visit(p->data)) /* 访问其左子树为空的结点 */
			return ERROR;
		while(p->RTag==Thread&&p->rchild!=T)
		{
			p=p->rchild;
			visit(p->data); /* 访问后继结点 */
		}
		p=p->rchild;
	}
	return OK;
}

int main()
{
	BiThrTree H,T;
	printf("请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')\n");
 	CreateBiThrTree(&T); /* 按前序产生二叉树 */
	InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
	printf("中序遍历(输出)二叉线索树:\n");
	InOrderTraverse_Thr(H); /* 中序遍历(输出)二叉线索树 */
	printf("\n");
	
	return 0;
}


到了这里,关于【数据结构】线索二叉树(适用场景+图文推导过程+C语言代码实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之线索二叉树详细解释

    1.1 线索二叉树的原理 我们现在倡导节约型社会,一切都应该以节约为本。但当我们创建二叉树时我们会发现其中一共有两个指针域,有的指针域指向的结构为空,这也就浪费了很多空间。所以为了不去浪费这些空间我们采取了一个措施。就是利用那些空地址,存放指向结点

    2023年04月20日
    浏览(40)
  • 数据结构——二叉树线索化遍历(前中后序遍历)

    为什么要转换为线索化         二叉树线索化是一种将普通二叉树转换为具有特殊线索(指向前驱和后继节点)的二叉树的过程。这种线索化的目的是为了提高对二叉树的遍历效率,特别是在不使用递归或栈的情况下进行遍历。         将二叉树线索化的主要目的是为了

    2024年02月09日
    浏览(39)
  • 数据结构三叉链表与线索二叉树的思路与实现详解

    ❤️作者主页:微凉秋意 ✅作者简介:后端领域优质创作者🏆,CSDN内容合伙人🏆,阿里云专家博主🏆 我们知道最常见的链式存储二叉树的结构体中有数据域、左孩子指针以及右孩子指针,通过递归来创建二叉树。显而易见的是,想找到二叉树中任意一个结点的 前驱 或 后

    2024年02月02日
    浏览(61)
  • 探索树形数据结构,通识树、森林与二叉树的基础知识(专有名词),进一步利用顺序表和链表表示、遍历和线索树形结构

      结点之间有分支,具有层次关系 树的定义 : 树 (tree)是n(n≥0)个有限集。 若n = 0,则称为空树; 若n 0,则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点; 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,.....,Tm,其中每一个集合本身又是一棵树,并称为根的

    2024年02月01日
    浏览(53)
  • 【数据结构-二叉树】二叉树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(48)
  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

    2024年01月23日
    浏览(58)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(63)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(47)
  • 【数据结构】二叉树——顺序结构

    由于每个节点都 只有一个父节点 ,所以我们可通过双亲来表示一棵树。具体方式通过 数组的形式 实现。 根节点的下标为0 按照层序从上到下排序 每层从左向右递增 表示形式: 二维数组 数据的列标为0 ,只需确定行标,即可锁定位置 根节点的父节点下标为 -1 列标为1存父节

    2024年02月02日
    浏览(56)
  • 数据结构-二叉树-二叉树左右孩子交换(递归)

     注:本文采用队列和递归的算法进行创建和层次遍历。同时不能采用BFS和DFS,因为需要把当前根节点的左孩、右孩勾链并输入才能递归下一个根节点; 队列用于存储此时应该递归的根节点; 格式:每一行尾不能有空格; Description 根据输入利用二叉链表创建二叉树,并将所

    2024年02月04日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包