精华内容
下载资源
问答
  • 数据结构-线索二叉树
    2019-08-13 16:30:31

    线索二叉树
    1.什么是线索二叉树
    遍历二叉树是按一定的规则将二叉树中所有结点排列为一个有序序列,这实质上是对一个非线性的数据结构进行线性化的操作。经过遍历的结点序列,除第一个结点和最后一个结点以外,其余每个结点都有且仅有一个直接前驱结点和一个直接后继结点。
    当以二叉链表作为存储结构时,只能找到结点的左、右孩子的信息,而不能直接得到结点任意一个序列中的直接前驱结点和直接后继结点是什么,这种信息只有在对二叉树遍历的动态过程中才能得到。若增加前驱指针和后继指针将使存储密度进一步降低。
    在用二叉链表存储的二叉树中,单个结点的二叉树有两个空指针域;两个结点的二叉树有三个空指针域。
    不难证明:n个结点的二叉树有n+1个空指针域。也就是说,一个具有n个结点的二叉树,若采用二叉链表存储结构,在其总共2n个指针域中只有n-1个指针域是用于存储结点子树的地址,而另外n+1个指针域存放的都是∧(空指针域)。因此,可以充分利用二叉链表存储结构中的那些空指针域,来保存结点在某种遍历序列中的直接前驱结点和直接后继结点的地址信息。
    指向直接前驱结点或指向直接后继结点的指针称为线索(thread),带有线索的二叉树称为线索二叉树。对于二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。
    2.线索二叉树的方法
    由于二叉树结点的序列可由不同的遍历方法得到,因此,线索二叉树也分为先序线索二叉树、中序线索二叉树和后序线索二叉树三种。在三种线索二叉树中一般以中序线索化用得最多,所以下面以图6-10所示的二叉树为例,说明中序线索二叉树的方法。中序线索二叉树的具体步骤如下。
    (1)先写出原二叉树的中序遍历序列:DGBAECHF。
    (2)若结点的左子树为空,则此线索指针将指向前一个遍历次序的结点。
    (3)若结点的右子树为空,则此线索指针将指向下一个遍历次序的结点。

    线索二叉树的结点结构定义如下。
    typedef struct threadbinode
    {
    datatype data; //二叉链表的结点
    bool ltag; //左孩子标志,当ltag为true时,表示左孩子存在(lchild所指为该结点左
    孩子);反之,则表示左孩子不存在(lchild所指为该结点直接后继结点)
    struct threadbinode lchild; //左孩子指针
    bool rtag; //其含义与ltag类似
    struct threadbinode rchild; //右孩子指针
    }ThreadBiNode; //二叉链表结点的类型
    二叉树进行中序线索化的递归函数代码如下。
    void InThreadBiTree(ThreadBiNode *T, ThreadBiNode *pre,ThreadBiNode *
    rear)
    { //pre指向整个二叉树T中序序列的直接前驱节点
    //rear指向整个二叉树T中序序列的直接后继节点
    if(trueT-> ltag)
    InThreadBiTree(T-> lchild,pre,T);
    //左子树的直接前驱结点就是整棵二叉树的直接前驱结点,左子树的直接后继结点就是整棵
    二叉树的根结点
    else
    T-> lchild=pre;
    if(true
    T-> rtag)
    InThreadBiTree(T-> rchild,T,rear);
    //右子树的直接前驱结点就是整棵二叉树的根结点,右子树的直接后继结点就是整棵二叉树
    的直接后继结点
    else
    T-> rchild=rear;
    }
    由于整棵二叉树中序序列的直接前驱结点和直接后继结点均可为空,因此对二叉树T进行中序线索化可采用语句InThreadBiTree(T,NULL,NULL)。
    另外,为了便于操作,在存储线索二叉树时需要增设一个结点,其结构与其他线索二叉树的结点结构一样。但是头结点的数据域不存放信息,它的左指针域指向二叉树的根结点,右指针域指向自己。而原二叉树在某种序列遍历下的第一个结点的前驱线索和最后一个结点的后继线索都指向头结点。
    3.线索二叉树的优点
    (1)利用线索二叉树进行中序遍历时,不必采用堆栈处理,速度比一般二叉树的遍历速度快,并且节约存储空间。
    (2)任意一个结点都能直接找到它相应遍历顺序的直接前驱结点和直接后继结点。
    4.线索二叉树的缺点
    (1)结点的插入和删除较麻烦,并且速度也比较慢。
    (2)线索子树不能共用。

    更多相关内容
  • C语言数据结构线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化。使得在这个访问序列中每一个节点...
  • 中序线索二叉树,反方向进行中序遍历(要求非递归,顺前驱进行)。 (1)建立二叉树; (2) 按先序、中序、后序输出二叉树; (3)复制二叉树; (4)在字符模式下画出无缺陷的二叉树
  • 线索二叉树应用实验 实验...线索二叉树是为了快速求解二叉树中结点在指定次序下的前驱和后继而将二叉链表中空的左右孩子指针分别改为指向其前驱和后继结点而得到的结构反映了运算对数据结构的设计的影响因此首先要了解
  • 中序线索化二叉树数据结构. 当用二叉链表作为二叉树的存储结构时因为每个结点中只有指向其左右孩子结点的 针所以从任一结点出发只能直接找到该结点的左右孩子在一般情况下靠它无法直接找 到该结点在某种遍历次序下的...
  • 数据结构-二叉线索

    2012-11-19 22:28:43
    数据结构作业的二叉线索树,实现 1.建立一个二叉树并且先序线索化二叉树并且先序遍历线索二叉树 2.建立一个二叉树并且先序线索化二叉树并且中序遍历线索二叉树 3.建立一个二叉树并且先序线索化二叉树并且后序遍历...
  • 本节主要讲述二叉树的线索链表存储结构和相关操作
  • 很好的课程设计,刚验收多的,源程序和设计报告都在哦
  • 某福建大三本的某三本学院的数据结构作业,题号对应清华殷人昆版。有一些可能参考借鉴了网上的代码,大体应该都能运行(尤其是大作业),仅供参考
  • (一)数据元素、数据结构、抽象数据类型等概念 (二)算法设计的基本要求 (三)语句的频度和估算时间复杂度 二、线性表 (一)线性表的定义和基本操作 (二)线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 三...
  • 数据结构动画演示

    2019-05-06 14:22:22
    该资源包含了几乎所有的数据结构的动画视频,帮助我们更好的理解数据结构与算法的编程思路。 目录如下: 'B树的删除.swf', 'B树的生长过程.swf', '三元组表的转置.swf', '中序线索化二叉树.swf', '串的顺序存储.swf'...
  • 基本操作4.1 先序建立线索二叉树4.2 初始化tag4.3 后序线索化二叉树4.3.1 访问并建立线索4.3.2 遍历4.3.3 后序线索化主过程4.4 寻找后序前驱4.5 逆向后序遍历4.5.1 打印结点4.5.2 利用后序前驱实现逆向后序遍历4.6 ...

    1.头文件及类型定义

    #include<stdio.h>
    #include<stdlib.h>
    #define ElemType char
    

    2.线索二叉树结点类型定义

    //线索二叉树结点类型定义
    typedef struct ThreadNode {
    	ElemType data;							//数据元素
    	struct ThreadNode* lchild, * rchild;	//左、右孩子指针
    	int ltag, rtag;							//左、右线索标志
    	//tag=0,表示指针指向孩子;tag=1,表示指针是“线索”,ltag指向前驱,rtag指向后继
    }ThreadNode, * ThreadTree;
    

    3.函数声明

    /*函数声明*/
    void CreateThTree(ThreadTree& T);			//1.先序建立线索二叉树
    void InitThread(ThreadTree& T);				//2.初始化tag
    void visit1(ThreadNode* q);					//3-1.访问并建立线索
    void PostThread(ThreadTree T);				//3-2.遍历
    void CreatePostThread(ThreadTree T);		//3-3.后序线索化主过程
    ThreadNode* PreNode(ThreadNode* p);			//4.找到p的前驱结点
    void visit2(ThreadNode* p);					//5-1.打印结点
    void RevPostOrder(ThreadNode* T);			//5-2.利用后序前驱实现逆向后序遍历
    

    4.基本操作

    4.1 先序建立线索二叉树

    /*1.先序建立线索二叉树*/
    void CreateThTree(ThreadTree& T) {
    	char c;
    	scanf("%c", &c);
    	if (c == '#')
    		T = NULL;
    	else {
    		T = (ThreadNode*)malloc(sizeof(ThreadNode));
    		T->data = c;
    		CreateThTree(T->lchild);
    		CreateThTree(T->rchild);
    	}
    }
    

    4.2 初始化tag

    /*2.初始化tag*/
    void InitThread(ThreadTree& T) {
    	if (T != NULL) {
    		T->ltag = 0;
    		T->rtag = 0;	//初始化当前树中的tag指针为0,表示还未线索化
    		InitThread(T->lchild);	//递归遍历左子树
    		InitThread(T->rchild);	//递归遍历右子树
    	}
    }
    

    4.3 后序线索化二叉树

    4.3.1 访问并建立线索

    ThreadNode* pre = NULL;		//pre指向当前访问结点的前驱
    //3-1.访问并建立线索
    void visit1(ThreadNode* q) {
    	if (q->lchild == NULL) {	//左子树为空,建立前驱线索
    		q->lchild = pre;
    		q->ltag = 1;
    	}
    	if (pre != NULL && pre->rchild == NULL) {	
    		pre->rchild = q;	//建立前驱结点的后继线索
    		pre->rtag = 1;
    	}
    	pre = q;			//标记当前结点为刚刚访问过的结点
    }
    

    4.3.2 遍历

    //3-2.遍历
    void PostThread(ThreadTree T) {
    	if (T != NULL) {
    		PostThread(T->lchild);	//后序遍历左子树
    		PostThread(T->rchild);	//后序遍历右子树
    		visit1(T);				//访问根节点
    	}
    }
    

    4.3.3 后序线索化主过程

    //3-3.主过程
    void CreatePostThread(ThreadTree T) {
    	pre = NULL;			//pre初始化为NULL
    	if (T != NULL) {	//非空二叉树才能线索化			
    		PostThread(T);	//后序线索化二叉树
    		if (pre->rchild == NULL)	
    			pre->rtag = 1;			//处理遍历的最后一个结点
    	}
    }
    

    4.4 寻找后序前驱

    //4.寻找后序前驱
    ThreadNode* PreNode(ThreadNode* p) {
    	if (p->ltag == 0) {		//若ltag=0,说明所找结点有左孩子
    		if (p->rtag == 0)		//若rtag=0
    			return p->rchild;		//说明所找结点有右孩子,根据后序遍历的特点(左-右-根),右孩子为前驱
    		else                    //若rtag=1
    			return	p->lchild;		//说明所找结点无右孩子,则前驱结点为其左孩子
    	}
    	else
    		return p->lchild;	//若ltag=1,说明所找结点无左孩子,则返回前驱线索
    }
    

    4.5 逆向后序遍历

    4.5.1 打印结点

    //5-1.打印结点
    void visit2(ThreadNode* p) {
    	printf("%c\t", p->data);
    }
    

    4.5.2 利用后序前驱实现逆向后序遍历

    //5-2.利用后序前驱实现逆向后序遍历:空间复杂度为O(1) 
    void RevPostOrder(ThreadNode* T) {
    	for (ThreadNode* p = T; p != NULL; p = PreNode(p))
    		visit2(p);
    }
    

    4.6 main函数

    int main() {
    	ThreadTree T;
    
    	/*1、创建二叉树*/
    	printf("先序创建二叉树:");
    	CreateThTree(T);
    
    	/*2、初始化tag为0*/
    	InitThread(T);
    
    	/*3、后序线索化*/
    	CreatePostThread(T);
    
    	/*4、寻找后序前驱(用根结点测试)*/
    	printf("根结点的后序前驱为:%c\n", PreNode(T)->data);
    
    	/*6、逆向后序遍历二叉树*/
    	printf("<————逆向后序遍历————>\n");
    	RevPostOrder(T);
    
    	return 0;
    }
    

    4.7 测试

    4.7.1 二叉树结构

    在这里插入图片描述

    4.7.2 测试结果

    在这里插入图片描述

    5.小结

    • 对于后序线索二叉树并不会出现“转圈"现象,原因是根结点是最后被访问的,不可能再回去访问其左右孩子指向的子树。
    • 另外,同先序线索二叉树一样,后序线索二叉树也存在类似的问题:即只能找到后序前驱。具体分析同先序线索二叉树类似,已在上一篇文章小结中介绍,此处不再展开。
    展开全文
  • 数据结构》—— 遍历线索二叉树

    千次阅读 2021-10-04 21:32:14
    中、先、后序线索二叉树的遍历查找,代码实现遍历中序线索二叉树

    在这里插入图片描述
    以上图为参考:

    • 中序遍历(左根右):DGBEAFC;
    • 先序遍历(根左右):ABDGECF;
    • 后序遍历(左右根):GDEBFCA;

    讨论如何在线索二叉树查找结点的前驱与后继?

    一、中序线索二叉树的遍历查找:DGBEAFC

    ① 查找p指针所指结点的前驱:

    • 若 p->Ltag==1,则p的左链指向其前驱;
    • 若 p->Ltag==0,说明有左子树,结点的前驱是遍历左子树时最后访问的一个结点(左子树中最右下结点)。

    例如:左根右 --> ((左根右)根右) --> (((左根右)根右)根右);
    我们对根结点A进行中序遍历,可以发现,它的左子树是B为根节点,按中序遍历结果是先返回 D-G-B-E-A 满足(左子树最后访问的一个结点)。

    ② 查找p指针所指结点的后继:

    • 若 p->Rtag==1,则p的左链指向其前驱;
    • 若 p->Rtag==0,说明有右子树,结点的后继是遍历右子树时第一个访问的结点(右子树中最左下结点)。

    例如:左根右 --> (左根(左根右));
    我们对根结点A进行中序遍历,可以发现,它的右子树是C为根节点,第一个访问是F结点,满足中序遍历结果。
    在这里插入图片描述


    二、先序线索二叉树的遍历查找:ABDGECF

    ① 查找p指针所指结点的前驱:

    • 若 p->Ltag==1,则p的左链指向其前驱;
    • 若 p->Ltag==0,说明有左子树,若 *p 结点为根结点,则找不到它的前驱,因为由于(根左右),推不出它的前驱;若 *p 结点为左孩子 || (右孩子&兄弟节点)为NULL,则 *p 结点的前驱是它的父节点; 否则若 *p 结点为右孩子,它的前驱是兄弟节点。

    在这里插入图片描述
    ② 查找p指针所指结点的后继:

    • 若 p->Rtag==1,则p的左链指向其前驱;
    • 若 p->Rtag==0,说明有右子树,由遍历规则知则先序后继为左孩子,若p没有左孩子,则先序后继为右孩子。

    在这里插入图片描述


    三、后序线索二叉树的遍历查找:GDEBFCA

    ① 查找p指针所指结点的前驱:

    • 若 p->Ltag==1,则p的左链指向其前驱;
    • 若 p->Ltag==0,若p有右孩子,则后序前驱为右孩子,若p没有右孩子,则后序前驱为左孩子。

    ② 查找p指针所指结点的后继:

    • 若 p为根节点,则没有后继;若p为左孩子,它的后继结点是它的兄弟结点或者是p的父节点;若p为右孩子,它的后继是父节点。

    在这里插入图片描述
    在这里插入图片描述

    四、算法:遍历中序线索二叉树

    #include<iostream>
    using namespace std;
    
    //二叉树的二叉线索类型存储表示
    typedef struct BiThrNode{
    	char data;
    	struct BiThrNode *lchild,*rchild;	//左右孩子指针
    	int LTag,RTag;
    }BiThrNode,*BiThrTree;
    
    BiThrNode *pre=new BiThrNode;  // 全局变量pre
    
    void CreateBiTree(BiThrTree &T){
    	//按先序次序输入二叉树中结点的值(一个字符),创建二叉链表表示的二叉树T
    	char ch;
    	cin >> ch;
    	if(ch=='#')  T=NULL;			//递归结束,建空树
    	else{
    		T=new BiThrNode;
    		T->data=ch;//生成根结点
    		CreateBiTree(T->lchild);	//递归创建左子树
    		CreateBiTree(T->rchild);	//递归创建右子树
    	}
    }
    
    // 结点P为根的子树中序线索化
    void InThreading(BiThrTree p){
    	//pre是全局变量,初始化时其右孩子指针为空,便于在树的最左点开始建线索
    	if(p){
    		InThreading(p->lchild);             			//左子树递归线索化
    		if(!p->lchild){    //p的左孩子为空
    			p->LTag=1;   	//给p加上左线索
    			p->lchild=pre; 			//p的左孩子指针指向pre(前驱)
    		}
    		else
    			p->LTag=0;
    		if(!pre->rchild){		//pre的右孩子为空
    			pre->RTag=1;    		//给pre加上右线索
    			pre->rchild=p;      	//pre的右孩子指针指向p(后继)
    		}
    		else
    			pre->RTag=0;
    		pre=p;        			//保持pre指向p的前驱
    		InThreading(p->rchild);	//右子树递归线索化
        }
    }
    
    // 带头结点的中序线索化
    void InOrderThreading (BiThrTree &Thrt,BiThrTree T){
    	//中序遍历二叉树T,并将其中序线索化,Thrt指向头结点
    	Thrt=new BiThrNode;           //建头结点
    	Thrt->LTag=0;  		   		 //头结点有左孩子,若树非空,则其左孩子为树根
    	Thrt->RTag=1;				//头结点的右孩子指针为右线索
    	Thrt->rchild=Thrt;            	//初始化时右指针指向自己
    	if(!T)  Thrt->lchild=Thrt;      //若树为空,则左指针也指向自己
    	else{
    	  Thrt->lchild=T;  pre=Thrt;   //头结点的左孩子指向根,pre初值指向头结点
    	  InThreading(T);             //调用算法,对以T为根的二叉树进行中序线索化
    	  pre->rchild=Thrt;          //算法,结束后,pre为最右结点,pre的右线索指向头结点
    	  pre->RTag=1;
    	  Thrt->rchild=pre;        //头结点的右线索指向pre
    	}
    }
    
    void InOrderTraverse_Thr(BiThrTree T){
        //T指向头结点,头结点的左链lchild指向根结点,可参见线索化算法5.8。
        //中序遍历二叉线索树T的非递归算法,对每个数据元素直接输出
    	BiThrTree p;
    	p=T->lchild;              //p指向根结点
        while(p!=T){			  //空树或遍历结束时,p==T
    		while(p->LTag==0)	  //沿左孩子向下
    			p=p->lchild;	 //访问其左子树为空的结点
    		cout<<p->data;
    		while(p->RTag==1&&p->rchild!=T){
    			p=p->rchild;	//沿右线索访问后继结点
    			cout<<p->data;
    		}
    		p=p->rchild;
        }
    }
    
    int main(){
    	pre->RTag=1;
    	pre->rchild=NULL;
    	BiThrTree tree,Thrt;
    
    	cout<<"请输入建立二叉链表的序列,例如(ABD#G##E##CF###):\n";
    	CreateBiTree(tree);
    	InOrderThreading(Thrt,tree);
    	cout<<"中序遍历线索二叉树的结果为:\n";
    	InOrderTraverse_Thr(Thrt);
    	cout<<endl;
    }
    

    在这里插入图片描述

    展开全文
  • 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏
  • 数据结构-线索链表

    千次阅读 2018-10-09 15:22:32
    若经常遍历或者要求取遍历时结点的前驱、后继信息则应修改二叉链表的结构以保存该遍历顺序链表,加上线索的二叉树称为线索二叉树。分先序、中序、后序线索二叉树。 这里介绍的是中序线索二叉树. 首先是辅助宏的...

    遍历二叉树时结点访问的先后顺序信息只有子啊遍历的动态过程中得到。若经常遍历或者要求取遍历时结点的前驱、后继信息则应修改二叉链表的结构以保存该遍历顺序链表,加上线索的二叉树称为线索二叉树。分先序、中序、后序线索二叉树。

    这里介绍的是中序线索二叉树.

    首先是辅助宏的定义:

    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define OVERFLOW -1
    #define UNDERFLOW -2
    #define NULL 0
    #define TREE_SIZE 1
    #define TREEINCREMENT 1
    typedef int Status;
    typedef char TElemType;
    typedef enum {LINK,THREAD} PointerTag; //指针标记类型
    /*LINK 0 代表指向孩子的指针
    THREAD 1 代表为指向前驱后继的线索*/

    线索链表的存储结构定义:

    //线索链表的存储结构定义
    typedef struct BiThrNode{
       TElemType data;
       struct BiThrNode *lchild,*rchild;//左右指针
       PointerTag LTag,RTag;//指针性质LINK或者THREAD
    }BiThrNode,*BiThrTree;

    输出e 输出二叉树 调用先序遍历函数 用函数传递给其参数visit即可.

    Status PrintTElem(TElemType e){
       //输出e 输出二叉树 调用先序遍历函数 用函数传递给其参数visit即可
       printf("%c",e);
       return OK;
    }

    先序创造线索链表各节点 注意输入时空指针不要丢 输入空格是空树,停止 否则创造根节点 递归创造左子树, 递归创造右子树.

    Status CreatBiTree(BiThrTree &T){
       /*先序创造线索链表各节点 注意输入时空指针不要丢
       输入空格是空树,停止 否则创造根节点 递归创造左子树
       递归创造右子树*/
       TElemType e;
       scanf("%c",&e);
       if(e==' ')
           T=NULL;
       else{
           T=(BiThrTree)malloc(sizeof(BiThrNode));
           if(!T)//存储分配失败
               exit(OVERFLOW);
           T->data=e;
           T->lchild=NULL;
           T->rchild=NULL;
           CreatBiTree(T->lchild);
           CreatBiTree(T->rchild);
       }
       return OK;
    }

    遍历以p为根的树并添加前驱和后继线索信息 pre指向遍历后第一个结点的前驱 函数返回时pre指向最后一个访问的结点 

    递归求解 空时无操作 否则先递归的向左子树添加线索信息 后处理与p相关的线索信息 再递归的向右子树添加线索信息 注意处理左右子树时pre的取值..

    void InTreading(BiThrTree p,BiThrTree &pre){
        /*遍历以p为根的树并添加前驱和后继线索信息 pre指向遍历后第一个结点的前驱
        函数返回时pre指向最后一个访问的结点
        递归求解 空时无操作 否则先递归的向左子树添加线索信息 后处理与p相关的线索信息
        再递归的向右子树添加线索信息 注意处理左右子树时pre的取值*/
       if(p){
           InTreading(p->lchild,pre);
           if(!p->lchild){
               p->LTag=THREAD;
    	   p->lchild=pre;
           }
           else
               p->LTag=LINK;
           if(!pre->rchild) { 
    	   pre->RTag=THREAD;
    	   pre->rchild=p;
           }
           else
    	   pre->RTag=LINK;
           pre=p; //修改pre
           InTreading(p->rchild,pre);
       }
    }

    T为原二叉树 T指向树的根结点 将T中序线索化为Thrt,开辟头结点并赋初值 遍历原二叉树 根据有无孩子修改标记并适时添加线索信息 最后结点单独处理.

    Status InOrderTheading(BiThrTree &Thrt,BiThrTree T){
       //T为原二叉树 T指向树的根结点 将T中序线索化为Thrt
       //开辟头结点并赋初值 遍历原二叉树 根据有无孩子修改标记并适时添加线索信息 最后结点单独处理
       Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
       if(!Thrt)
           exit(OVERFLOW);
       BiThrNode *pre;
       Thrt->lchild=Thrt;//假设T为空
       Thrt->LTag=LINK;
       Thrt->RTag=THREAD;
       Thrt->rchild=Thrt;
       if(T){
           Thrt->lchild=T;
           pre=Thrt;
           InTreading(T,pre);
           pre->RTag=THREAD;//处理最后一个结点
           pre->rchild=Thrt;
           Thrt->rchild=pre;
       }
       return OK;
    }

    中序遍历线性链表.  令p指向原树根 设法让p指向第一个应该访问的结点 只要左孩子不空就令他指向左孩子 即 第一个左标记不为LINK的结点 访问p 只要p->THREAD 就让p=p->rchild 并访问p 否则令p指向右子树的根  重复上面操作 直到p指向头结点 遍历完毕.

    复杂度也为O(n),但是没有递归,不需要栈。

    Status InOrderTraverse_Thr(BiThrTree T,Status (*visit)(TElemType)){
        /*中序遍历线性链表
        令p指向原树根 设法让p指向第一个应该访问的结点 只要左孩子不空就令他指向左孩子 即
        第一个左标记不为LINK的结点 访问p 只要p->THREAD 就让p=p->rchild 并访问p 否则令p指向右子树的根
        重复上面操作 直到p指向头结点 遍历完毕*/
        BiThrNode *p=T->lchild;//p访问根结点
        while(p!=T){//未遍历结束
            while(p->LTag==LINK) //p指向第一个待访问的结点
    	    p=p->lchild;
    	if(!visit(p->data))
    	    return ERROR;
    	while(p->RTag==THREAD&&p->rchild!=T){
    	//只要是线索就前进
    	    p=p->rchild; 
                if(!visit(p->data))
    		return ERROR;
    	}
    	p=p->rchild;//当前结点右子树非线索 p指向右子树根
        }
        return OK;
    }//T(n)=O(n)

     

    展开全文
  • 线索二叉树 思考:在有n个节点的二叉链表中必定有n+1个空链域(下面会说为什么),遍历运算是最重要也是最常用的运算,之前的无论递归与非递归算法实现遍历效率都不算高。能不能利用这未使用的n+1空指针域,设计出...
  • 自己做的线索二叉树,数据结构课设的时候可以参考哦!编译过的cpp文件。欢迎下载!
  • 数据结构 线索二叉树

    2014-04-27 15:06:01
    当以二叉链表作为储存结构时,只能找到结点的左右孩子的信息,而不能直接找到结点的前驱后继,所以我们在每个结点上增加两个指针域fwd和bawd,分别指示结点在任一次序遍历时得到的前驱后继信息。
  • 清华大学 数据结构习题解析 邓俊辉。 本书主教材按照面向对象程序设计的思想,根据作者多年的教学积累,系统地介绍各类数据结构的功能、表示和实现,对比各类数据结构适用的应用环境;结合实际问题展示算法设计的...
  • 数据结构实验实现中序线索化二叉树构造哈夫曼树.doc
  • 数据结构】中序线索二叉树

    千次阅读 2021-01-29 11:53:58
    对如图所示的二叉树建立中序线索二叉树,并遍历 #include <cstdio> #include <cstdlib> typedef struct Node{ char data; Node *lchild, *rchild; int lflag, rflag; }Node, *BiTree; Node* new...
  • 中序线索化二叉树实验报告数据结构.doc
  • 何谓线索二叉树 遍历结果是求得结点的一个线性序列指向该线性序列前驱和后继的指针称线索包含线索的存储结构称为线索链表与其相应的二叉树称为线索二叉树对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化2...
  • 数据结构线索二叉树的基本概念和构造1.基本概念2.中序线索二叉树的构造2.1二叉树中序线索化分析 1.基本概念 二叉树的非递归遍历算法避免了系统栈的调用,提高了一定的效率,而线索二叉树可以把用户栈也省掉,把...
  • 数据结构线索树与树和森林PPT学习教案.pptx
  • 数据结构】-线索二叉树(先序)

    千次阅读 2020-08-10 18:19:48
    基本操作4.1 先序建立线索二叉树4.2 初始化tag4.3 先序线索化二叉树4.3.1 访问并建立线索4.3.2 遍历4.3.3 先序线索化主过程4.4 寻找先序后继4.5 先序遍历4.5.1 打印结点4.5.2 利用先序后继实现先序遍历4.6 main函数...
  • 为了不失系统性,作者依据多年的教学积累,对各种数据结构及其算法,按照分层的思想精 心进行归纳和整理,并从数据访问方式、数据逻辑结构、算法构成模式等多个角度,理出线索加 以贯穿,使之构成一个整体,使学生在...
  • 数据结构动画演示.7z

    2020-12-09 09:15:30
    资源包含了几乎所有的数据结构的动画视频,帮助我们更好的理解数据结构与算法的编程思路。 目录如下: 'B树的删除.swf', 'B树的生长过程.swf', '三元组表的转置.swf', '中序线索化二叉树.swf', '串的顺序存储.swf', ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,695
精华内容 15,878
关键字:

数据结构什么是线索

数据结构 订阅