数据结构--树4.2.3(线索二叉树)

这篇具有很好参考价值的文章主要介绍了数据结构--树4.2.3(线索二叉树)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

利用中序遍历可以解决二叉树中空出来的内存,以及前驱后继的问题。

lchild ltag data rtag rchild

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

——rtag为0时指向该结点的有孩子,为1时指向该结点的后继。文章来源地址https://www.toymoban.com/news/detail-679504.html

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

typedef char ElemType;
//线索存储标志
//Link(0):表示指向左右孩子的指针
//thread(1):表示指向前驱后继的线索 

typedef enum{Link,Thread} Pointertag;

typedef struct  Bithrnode
{
	char data;
	struct Bithrnode * lchild ,* rchild;
	Pointertag ltag;
	Pointertag rtag;
}Bithrnode,*Bithrtree;
//创建一棵二叉树,约定用户遵照前序遍历的方式输入数据
Bithrtree pre;

CreateBithree(Bithrtree *t)
{
	char c;
	scanf("%c",&c);
	if(' '== c)
	{
		*t =  NULL;
	}
	else
	{
		*t = (Bithrnode*)malloc(sizeof(Bithrnode));
		(*t)->data=c;
		(*t)->ltag = Link;
		(*t)->rtag = Link;
		CreateBithree(&(*t)->lchild);
		CreateBithree(&(*t)->rchild);
	}
 } 
 
 //中序遍历
 Inthreading(Bithrtree t)
 {
 	if(t)
 	{
 		Inthreading(t->lchild);//递归左孩子线索化 
 		if(!t->lchild)
 		{
 			t->ltag = Thread;
 			t->lchild = pre;
		 }
		if(!pre->rchild)
		{
			pre->rtag = Thread;
			pre->rchild = t;
		}
		pre = t;
		Inthreading(t->rchild);//递归右孩子线索化 
	 }
  } 

//中序遍历二叉树,非递归
Inordertraverse(Bithrtree t)
{
	Bithrtree p;
	p = t->lchild;
	while(p!= t)
	{
		while(p->ltag == Link)
		{
			p=p->lchild;
		}
		visit(p->data);
		while(p->rtag == Thread && p->rchild != t)
		{
			p=p->rchild;
			visit(p->data);
		}
		p=p->rchild;
	}
 } 
int main()
{
	Bithrtree p,t =NULL;
	CreateBithree(&t);
	Inthreading(t);
	printf("中序遍历输出结果为:");
	Inordertraverse(p);
	printf("\n");
	return 0;
}

到了这里,关于数据结构--树4.2.3(线索二叉树)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构——二叉树线索化遍历(前中后序遍历)

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

    2024年02月09日
    浏览(39)
  • 【数据结构】线索二叉树(适用场景+图文推导过程+C语言代码实现)

    普通二叉树(如下图): 空间浪费 :存在大量“∧”,该空间未利用。 时间效率 :查找一次结点的前驱、后继就需要遍历一次,时间效率低。         在实际问题中,如果所用的 二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表

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

    ❤️作者主页:微凉秋意 ✅作者简介:后端领域优质创作者🏆,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)
  • 数据结构 | 二叉树的应用

    目录 一、解析树 二、树的遍历 我们可以用解析树来表示现实世界中像句子或数学表达式这样的构造。 我们可以将((7+3)*(5-2))这样的数学表达式表示成解析树。这是完全括号表达式,乘法的优先级高于加法和减法,但因为有括号,所以在做乘法前必须先做括号内的加法和减法

    2024年02月14日
    浏览(41)
  • 数据结构——二叉树的遍历与应用

    目录 一.前言 二. 二叉树链式结构的实现 2.1 前置说明 2.2 二叉树的遍历 2.2.1 前序、中序以及后序遍历 前序遍历: 中序遍历递归图: 后序遍历: 2.3节点个数 2.4叶子节点个数 2.5第K层的节点个数 2.6 二叉树查找值为x的节点 2.7 二叉树的销毁 三.结语   大家好久不见,放寒假了咱

    2024年01月19日
    浏览(47)
  • [数据结构] 树、森林及二叉树的应用

    双亲表示法 双亲表示法的存储结构 【注】 区别树的顺序存储结构与二叉树的顺序存储结构。在树的顺序存储结构中,数组下标代表节点的编号,下标中所存的内容指示了节点之间的关系。而在二叉树的顺序存储结构中, 数组下标既表达了节点的编号,又指示了二叉树中节点

    2024年03月09日
    浏览(57)
  • 【数据结构和算法】---二叉树(2)--堆的实现和应用

    如果有一个数字集合,并把它的所有元素 按完全二叉树的顺序存储方式存储在一个一维数组中 ,且在逻辑结构(即二叉树)中,如果 每个父亲节点都大于它的孩子节点那么此堆可以称为大堆 ;那么如果 每个父亲节点都小于它的孩子节点那么此堆可以称为小堆 。 堆的 性质

    2024年02月03日
    浏览(47)
  • 头歌数据结构实训参考---二叉树及其应用

    第1关 实现二叉树的创建 第2关 计算二叉树的深度和节点个数 第3关 递归实现二叉树左右子树交换 第4关 非递归实现二叉树左右子树交换 第5关 层次遍历二叉树

    2024年02月05日
    浏览(43)
  • 【数据结构】堆的应用+TOP-K问题+二叉树遍历

    欢迎来到我的: 世界 希望作者的文章对你有所帮助,有不足的地方还请指正,大家一起学习交流 ! 该篇文章写到主要是:堆排序、 TOP-K问题、二叉树链式结构的实现、二叉树的遍历等等;如果有朋友还不太了解堆以及二叉树可以翻看我的上一篇博客:堆和二叉树的概念; 最

    2024年02月07日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包