树(四)——线索二叉树

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

目录

一、线索二叉树基本概念

1、概念 

2、线索二叉树的结构

3、名词解释

二、线索二叉树的线索化

1、原理

1.1如何实现空指针域中结点的前驱或后继

1.2 图解便于理解

2、算法实现

三、线索二叉树的遍历

1、中序线索二叉树中寻找遍历的首结点 

2、寻找结点的直接后继

3、遍历线索二叉树

四、线索二叉树遍历的应用

算法实现:

运行结果:


一、线索二叉树基本概念

1、概念 

     二叉链表的存储结构,只能找到该结点的左右孩子,不能得到该结点在遍历过程中的遍历前驱和直接后继结点。二叉链表存储二叉树时,有2n个指针域,其中n+1个都为空指针域。

利用空指针域存储结点遍历过程中的前驱和后继结点,使结点之间组成联系,在遍历的过程中可以不用通过栈或递归。

线索 二叉树的作用:

将树转换成线性链表,二叉树在首次遍历中线索化,在需要时可以直接获得结点的前驱和后继,不需要像栈一样频繁的压栈出栈。

2、线索二叉树的结构

线索二叉树与二叉链表的区别是,增加了左标志域Ltag,和右标志域Rtag,,是两个布尔值的数据域。线索二叉树的结构为:

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

1、若结点的左孩子不为空,LChild指针域仍指向其左孩子,否则,LChild指针域指向遍历过程序列的前驱结点。

2、若结点的右孩子不为空,RChild指针域仍指向其右孩子,否则,RChild指针域指向遍历过程序列的后继结点。

3、对于Ltag和Rtag的标志域的定义:

   Ltag = 0时,LChild域指向结点的左孩子。

   Ltag=1时, LChild域指向结点的遍历前驱。

   Rtag=0时,RChild域指向结点的右孩子。

   Rtag=1时,RChild域指向结点的遍历后继。

typedef struct Node
{
   TypeData data;
   int Ltag,Rtag;
   struct Node*LChild;
   Struct Node*RChild;
}BiTree,*BiThrTree;

3、名词解释

线索:指向前驱和后继结点的指针

线索化:对二叉树以先序次序(中序,后序)遍历的过程中将结点的空指针域改为线索的过程,叫做‘线索化’。

线索二叉树:经过线索化的二叉树。

线索链表:以线索二叉树的结点结构存储的含有线索的二叉链表

二、线索二叉树的线索化

1、原理

线索化的过程就是在遍历的过程中将二叉树中空的指针域填上结点的直接前驱或直接后继的过程。

1.1如何实现空指针域中结点的前驱或后继

     结点空指针域前驱的填入,需要知道刚刚访问的结点,后继的填入,需要知道下一个访问的结点,所以可以用一个 pre 指针专门用于记录刚刚访问的结点(也就是现在访问的结点的上一个结点。

     对于 pre 指针,因为开始遍历的第一个结点没有前驱,所以 pre 需要初始化为NULL

对于空指针域结点的前驱的填入思路:

     如果当前访问的结点的左子树为空,此时指向左子树的指针域为空,让其指向刚刚访问过的结点pre,root->LChild=pre 同时将左标志域 Ltag 置为 1 ,即完成了前驱线索。

对于后继的填入思路:

      结点的右子树为空,指向其右子树的指针域为空,让其指向下一个结点,就需要知道下一个结点的存在才能进行连接。所以需要在遍历到下一个结点时,让刚访问过的结点 pre 进行回填指向右孩子的指针域。

      pre是刚访问过的结点,判断pre的右孩子是否为空,为空时:root是当前访问的结点,对pre的右孩子指针域进行回填,让pre->RChild=root,且将右标志域Rtag 置为1。

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

1.2 图解便于理解

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

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

2、算法实现

二叉树的中序线索化算法

//中序线索化算法
void Inthread(BiTree root)
{
  if(root!=NULL)
    {
       Inthread(root->LChild);   //通过递归线索化左子树
       if(root->LChild==NULL)    //当前结点的左子树为空
         {
            root->LChild=pre;    //  第一步   置前驱线索
            root->Ltag=1;        //左标志域为1
         }
        if(pre!=NULL&&pre->RChild==NULL)  //刚刚访问的结点不为空且右子树为空
          {
             pre->RChild=root;        //  第二步 置后驱线索
             pre->Rtag=1;        //右标志域为1
          }
        pre=root;               //  第三步  pre指向当前访问的结点
        Inthread(root->RChild);  //递归线索化右子树
     }
}

三、线索二叉树的遍历

线索二叉树的遍历过程分为两步:

1、第一步找到遍历过程中的第一个被访问的结点。

2、第二步是不断在遍历的过程中寻找刚访问结点的后继结点,并访问。

1、中序线索二叉树中寻找遍历的首结点 

中序次序是先访问左子树,根结点、右子树。所以中序遍历的首结点是左子树的最左下端的结点。

BiThrTree InFirst(BiThrTree bt)
{
      BiThrTree p=bt;
      if(p==NULL)
        return NULL;
      while(p->Ltag==0)
           p=p->LChild;
      return p;
}

2、寻找结点的直接后继

要找 p 结点的后继,需要进入其右子树,p结点的后继结点是右子树中遍历的第一个结点也就是左子树中的最左下端。

BiThrTree InNext(BiThrTree p)
{ 
    if(p->Rtag==1)        //如果p的右子树为空,直接利用线索找到其后继结点。
      next=p->RChild;
    else                 //在p的右子树中找左子树的第一个结点
     { 
          next=p->RChild;
          while(next->Ltag==0)    //结点的左子树指向下一个结点时,继续找最左下端的左子树
          next=next->LChild;
     }
    return next;
}

3、遍历线索二叉树

按照线索二叉树遍历的两步走

void TinOrder(BiThrTree root)
{
    BiThrTree p;
    p=InFirst(root);
    while(p!=NULL)
    {
       Visit(p->data);
       p=InNext(p);
     }
}

四、线索二叉树遍历的应用

算法实现:

#include<stdio.h>
#include<stdlib.h>
//定义结点结构
typedef struct Node
{
	char data;
	int Ltag, Rtag;
	struct Node* LChild;
	struct Node* RChild;
}BiTreeNode,*BiThrTree;
//建立二叉链表
void Establish(BiThrTree* root)  
{
	char demo;
	demo = getchar();
	if (demo == '^')
		*root = NULL;
	else
	{
		*root = (BiThrTree)malloc(sizeof(BiTreeNode));
		if (*root == NULL)
			return;
		(*root)->data = demo;
		(*root)->Ltag = 0;
		(*root)->Rtag = 0;
		Establish(&((*root)->LChild));
		Establish(&((*root)->RChild));
	}
}
//线索化,建立线索链表
void Inthread(BiThrTree*root)
{
	static BiThrTree pre = NULL;       //在递归调用中,初始化pre,且保存每次pre的信息,用static静态局部变量解决
	if ((*root) != NULL)
	{
		Inthread(&((*root)->LChild));
		if ((*root)->LChild == NULL)
		{
			(*root)->LChild = pre;
			(*root)->Ltag = 1;
		}
		if (pre != NULL && pre->RChild == NULL)
		{
			pre->RChild = (*root);
			pre->Rtag = 1;
		}
		pre = (*root);
		Inthread(&((*root)->RChild));
	}
}
//查找遍历的首结点
BiThrTree InFirst(BiThrTree root)
{
	BiThrTree p=root;
	if (p == NULL)
		return NULL;
	while(p->Ltag == 0)
		 p = p->LChild;
	return p;
}
//查找遍历过程中结点的直接后继
BiThrTree InNext(BiThrTree p)
{
    BiThrTree next=NULL;
	if (p->Rtag == 1)
		next = p->RChild;
	else
	{
		next= p->RChild;
		while (next!=NULL&&next->Ltag == 0)   //next!=NULL,解决局部变量next为空指针时,不能访问data等数据
			next = next->LChild;
	}
	return next;
}
//遍历线索二叉树
void TinOrder(BiThrTree root)
{
	BiThrTree p;
	if (root == NULL)
		return;
	p = InFirst(root);
	while (p != NULL)
	{
		printf("%c ", p->data);
		p = InNext(p);
	}
}
main()
{
	BiThrTree root;
	printf("------根据二叉链表的格式输入结点数据------\n");
	printf("\n");
	Establish(&root);
	Inthread(&root);
	printf("-------遍历打印线索二叉树-------\n");
	printf("\n");
	TinOrder(root);
}

运行结果:

线索二叉树,# 树,数据结构与算法,算法,数据结构,c语言                      线索二叉树,# 树,数据结构与算法,算法,数据结构,c语言文章来源地址https://www.toymoban.com/news/detail-696436.html

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

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

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

相关文章

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

    利用中序遍历可以解决二叉树中空出来的内存,以及前驱后继的问题。 lchild ltag data rtag rchild ——ltag为0时指向该结点的左孩子,为1时指向该结点的前驱。 ——rtag为0时指向该结点的有孩子,为1时指向该结点的后继。

    2024年02月11日
    浏览(36)
  • 数据结构——二叉树线索化遍历(前中后序遍历)

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

    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)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

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

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

    目录 一、树 1、初识树 2、树的一些概念 3、树的表示形式 二、二叉树 1、初识二叉树 2、两种特殊的二叉树 3、二叉树的性质  4、二叉树的遍历 5、实现一棵二叉树  6、二叉树题目(没代码的后面会给补上) (1)根节点没有前驱。 (2)子树的根节点只有一个前驱,可以有

    2024年04月09日
    浏览(48)
  • 数据结构与算法-二叉树

            在计算机科学中,数据结构是组织和存储数据的基础框架,而算法则是处理这些数据的核心逻辑。在这众多的数据结构中,二叉树因其独特的层级结构、高效的搜索和插入操作,成为广泛应用的一种非线性数据结构。本文将深入探讨二叉树的定义、种类、操作方法

    2024年03月10日
    浏览(59)
  • 数据结构---二叉树(C语言)

    空树 非空:根节点,根节点的左子树、根节点的右子树组成的。 从二叉树的定义来看,二叉树是递归定义的,因此我们可以用递归的形式来遍历二叉树。 1.1.1二叉树前中后序遍历(递归版) 访问根结点的顺序不同。 1.1.2 层序遍历 层序遍历是按照二叉树的高度,一层一层遍

    2024年02月06日
    浏览(47)
  • 二叉树(上)——“数据结构与算法”

    各位CSDN的uu们好呀,好久没有更新我的数据结构与算法专栏啦,今天,小雅兰继续来更新二叉树的内容,下面,让我们进入链式二叉树的世界吧!!! 二叉树链式结构的实现  二叉树链式结构的实现 普通的二叉树的增删查改是没有价值的!!! 只有搜索二叉树的增删查改才

    2024年02月15日
    浏览(45)
  • 【数据结构】二叉树---C语言版

    树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树,是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个特殊的结点,称为根结点, 根节点没有前驱结点 除根节点外,其余结点被分成M(M0)个互不相交

    2024年02月05日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包