线索二叉树 订阅
在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。 [1] 展开全文
在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。 [1]
信息
外文名
Threaded BinaryTree
领    域
计算机科学
中文名
线索二叉树
线索二叉树概念
对于n个结点的二叉树,在二叉链存储结构中有n+1个空链域,利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针,这些指针称为线索,加上线索的二叉树称为线索二叉树。 这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。注意:线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题,解决了二叉链表找左、右孩子困难的问题。
收起全文
精华内容
下载资源
问答
  • 线索二叉树

    2019-04-10 21:19:27
    通过前序序列创建线索二叉树 1:中序遍历 2:查找节点前驱后继 3:插入节点 4:删除节点 0:退出
  • 目录链式存储线索二叉树中序线索二叉树中序线索化实现实现的代码过程中序线索二叉树的遍历遍历代码中序线索二叉树可运行代码先序线索二叉树先序线索化实现先序线索二叉树的遍历遍历代码先序线索二叉树可运行代码后序...
  • 线索二叉树应用实验 实验报告 实验目的 1掌握线索二叉树的有关知识 2掌握求解线索二叉树中结点前趋和后继的算法以及以相应次序遍历线索二叉树的算法 3掌握二叉树的线索化算法的设计 实验运行环境 Visual C++ 实验...
  • NULL 博文链接:https://128kj.iteye.com/blog/1634367
  • 在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。 文章目录一、c语言实现先序线索、中序线索、...
     
    

    在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。


    一、c语言实现先序线索、中序线索、后续线索二叉树

    代码如下(示例):

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct BiTNode {
    	int data;
    	BiTNode* lchild, * rchild;
    	int ltag=0, rtag=0;
    }BiTNode,*BiTree;
    
    BiTree pre = NULL;//全局变量
    
    void visit(BiTree P) {
    	if (P->lchild == NULL) {
    		P->lchild = pre;
    		P->ltag=1;
    	}
    	if (pre != NULL && pre->rchild == NULL) {
    		pre->rchild = P;
    		pre->rtag = 1;
    	}
    	if(P!=NULL) printf("%d\n", P->data);
    	if (P == NULL) printf("no rchild");
    	pre = P;
    }
    
    //中序线索二叉树,一边遍历一边线索化
    void MBuild(BiTree P) {
    	if(P!=NULL){
    	MBuild(P->lchild);
    	visit(P);
    	MBuild(P->rchild);
    	}
    }
    
    //中序线索树节点p的前驱节点
    BiTree MPreNode(BiTree p) {
    	if (p->ltag == 1) p = p->lchild;
    	else {
    	if (p->ltag != 1) {
    			p = p->lchild;
    			while (p->rtag != 1 && p->rchild != NULL)//注意p->rtag != 1 && p->rchild != NULL而不是p->rchild != NULL
    				p = p->rchild;
    		}
    	}
    	
    	return p;
    }
    
    //中序线索树节点p的后继节点
    BiTree MSucceedNode(BiTree p) {
    	if (p->rtag == 1) {
    		p = p->rchild; 
    	}
    	else {
    	if (p->rtag ==0) {
    			p = p->rchild;
    			while (p->ltag != 1 && p->lchild != NULL)//注意
    				p = p->lchild;
    		}
    	}
    	return p;
    }
    
    
    //先序线索树,一边遍历一边线索化
    void PBuild(BiTree T) {
    	if (T != NULL) {
    	visit(T);
    		if(T->ltag!=1)	PBuild(T->lchild);
    		PBuild(T->rchild);
    	}
    	
    }
    
    //先序线索树节点p的前驱节点   注意else!!!!!!!!!!!!!
    BiTree PPreNode(BiTree p) {
    	if (p->ltag == 1) p = p->lchild;
    	else {
    		if (p->ltag != 1) {
    			printf("can not by this way!");
    		}
    	}
    	return p;
    }
    
    //先序线索树节点p的后继节点     注意else!!!!!!!!!!!!
    BiTree PSucceedNode(BiTree p)  {
    	if (p->rtag == 1) p = p->rchild;
    	else {
    	if (p->rtag != 1) {
    			if (p->ltag!=1)  p=p->lchild;
    			else
    			if (p->ltag==1) p = p->rchild;
    		}
    	}
    	return p;
    }
    
    
    //后序线索二叉树,一边遍历一边线索化
    void LBuild(BiTree P) {
    	if (P != NULL) {
    		MBuild(P->lchild);
    		MBuild(P->rchild);
    		visit(P);
    	}
    }
    
    //后序线索树节点p的前驱节点
    BiTree LPreNode(BiTree p){
    	if (p->ltag == 1) p = p->lchild;
    	else {
    	if (p->ltag != 1) {
    			if (p->rtag!=1) p = p->rchild;
    			if (p->rtag==1) p = p->lchild;
    		}
    	}
    	return p;
    }
    
    //后序线索树节点p的后继节点
    BiTree LSucceedNode(BiTree p) {
    	if (p->rtag == 1) p = p->rchild;
    	else {
    	if (p->rtag != 1) {
    			printf("can not by this way!");
    		}
    	}
    	return p;
    }
    
    int main() {
    	BiTree a1 = (BiTree)malloc(sizeof(BiTNode));
    	a1->data = { 1 };
    	a1->ltag = 0;
    	a1->rtag = 0;
    	a1->lchild = NULL;
    	a1->rchild = NULL;
    
    	BiTree a2 = (BiTree)malloc(sizeof(BiTNode));
    	a2->data = { 2 };
    	a1->lchild = a2;
    	a2->ltag = 0;
    	a2->rtag = 0;
    	a2->lchild = NULL;
    	a2->rchild = NULL;
    
    	BiTree a3 = (BiTree)malloc(sizeof(BiTNode));
    	a3->data = { 3 };
    	a1->rchild = a3;
    	a3->lchild = NULL;
    	a3->rchild = NULL;
    	a3->ltag = 0;
    	a3->rtag = 0;
    
    	BiTree a5 = (BiTree)malloc(sizeof(BiTNode));
    	a5->data = { 5 };
    	a2->rchild = a5;
    	a5->lchild = NULL;
    	a5->rchild = NULL;
    	a5->ltag = 0;
    	a5->rtag = 0;
    
    	BiTree a6 = (BiTree)malloc(sizeof(BiTNode));
    	a6->data = { 6 };
    	a3->lchild = a6;
    	a6->lchild = NULL;
    	a6->rchild = NULL;
    	a6->ltag = 0;
    	a6->rtag = 0;
    
    	BiTree a7 = (BiTree)malloc(sizeof(BiTNode));
    	a7->data = { 7 };
    	a3->rchild = a7;
    	a7->lchild = NULL;
    	a7->rchild = NULL;
    	a7->ltag = 0;
    	a7->rtag = 0;
    
    //中序的测试
    //	MBuild(a1); 
    //	pre->rchild = NULL;
    //	BiTree n = MPreNode(a3);
    //	BiTree m = MSucceedNode(a2);
    //	printf(" %d\n",n->data);
    
    //先序的测试
    	PBuild(a1);
    	pre->rchild = NULL;
    	printf("%d\n",PPreNode(a3)->data);
    	printf("%d\n",PSucceedNode(a3)->data);
    
    //后序的测试
    //	LBuild(a1);
    //	pre->rchild = NULL;
    //	printf("  %d\n", LPreNode(a5)->data);
    //	printf("  %d\n", LSucceedNode(a6)->data);
    
    }
    

    总结

    关注一下吧!好想有几个粉丝啊

    展开全文
  • (1)递归实现二叉树的中序线索化 (2)非递归实现二叉树的中序线索化 (3)实现中序线索二叉树上遍历二叉树
  • 文章目录线索二叉树的概念线索二叉树的结构二叉树的线索化使用线索二叉树进行遍历双向线索二叉树的概念双向线索二叉树的实现过程双向线索二叉树的遍历 线索二叉树的概念 当我们对普通的二叉树进行遍历时需要使用栈...

    工科生一枚,热衷于底层技术开发,有强烈的好奇心,感兴趣内容包括单片机,嵌入式Linux,Uboot等,欢迎学习交流!
    爱好跑步,打篮球,睡觉。
    欢迎加我QQ1500836631(备注CSDN),一起学习交流问题,分享各种学习资料,电子书籍,学习视频等。

    线索二叉树的概念

      当我们对普通的二叉树进行遍历时需要使用栈结构做重复性的操作。线索二叉树不需要如此,在遍历的同时,使用二叉树中空闲的内存空间记录某些结点的前趋和后继元素的位置(不是全部)。这样在算法后期需要遍历二叉树时,就可以利用保存的结点信息,提高了遍历的效率。使用这种方法构建的二叉树,即为“线索二叉树”。

    线索二叉树的结构

      每一棵二叉树上,很多结点都含有未使用的指向NULL 的指针域。除了度为2 的结点,度为1 的结点,有一个空的指针域;叶子结点两个指针域都为NULL。

      线索二叉树实际上就是使用这些空指针域来存储结点之间前趋和后继关系的一种特殊的二叉树。线索二叉树中,如果结点有左子树,则lchild 指针域指向左孩子,否则lchild 指针域指向该结点的直接前趋;同样,如果结点有右子树,则rchild 指针域指向右孩子,否则rchild 指针域指向该结点的直接后继。
    在这里插入图片描述
      LTag 和RTag 为标志域。实际上就是两个布尔类型的变量:
       LTag 值为0 时,表示lchild 指针域指向的是该结点的左孩子;为1 时,表示指向的是该结点的直接前趋结点;
       RTag 值为0 时,表示rchild 指针域指向的是该结点的右孩子;为1 时,表示指向的是该结点的直接后继结点。
      结点结构代码实现:

    #define TElemType int//宏定义,结点中数据域的类型
    //枚举,Link 为0,Thread 为1
    typedef enum PointerTag{
    Link,
    Thread
    }PointerTag;
    //结点结构构造
    typedef struct BiThrNode{
    TElemType data;//数据域
    struct BiThrNode* lchild,*rchild;//左孩子,右孩子指针域
    PointerTag Ltag,Rtag;//标志域,枚举类型
    }BiThrNode,*BiThrTree;
    

    二叉树的线索化

      将二叉树转化为线索二叉树,实质上是在遍历二叉树的过程中,将二叉链表中的空指针改为指向直接前趋或者直接后继的线索。
      线索化的过程即为在遍历的过程中修改空指针的过程。在遍历过程中,如果当前结点没有左孩子,需要将该结点的lchild 指针指向遍历过程中的前一个结点,所以在遍历过程中,设置一个指针(名为pre ),时刻指向当前访问结点的前一个结点。
      代码实现(拿中序遍历为例):

    /**
     * @Description: 中序对二叉树进行线索化
     * @Param: BiThrTree p 二叉树的结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void InThreading(BiThrTree p)
    {
        //如果当前结点存在
        if (p)
        {
            //递归当前结点的左子树,进行线索化
            InThreading(p->lchild); 
            //如果当前结点没有左孩子,左标志位设为1,左指针域指向上一结点pre
            if (!p->lchild)
            {
                 //前驱线索
                p->Ltag = Thread;
                 //左孩子指针指向前驱
                p->lchild = pre; 
            }
            //如果pre 没有右孩子,右标志位设为1,右指针域指向当前结点。
            if (pre && !pre->rchild)
            {
                //后继线索
                pre->Rtag = Thread;
                //前驱右孩子指针指向后继(当前结点p)
                pre->rchild = p;
            }
            pre = p;                //pre 指向当前结点
            InThreading(p->rchild); //递归右子树进行线索化
        }
    }
    
    

      注意:中序对二叉树进行线索化的过程中,在两个递归函数中间的运行程序,和之前介绍的中序遍历二叉树的输出函数的作用是相同的。将中间函数移动到两个递归函数之前,就变成了前序对二叉树进行线索化的过程;后序线索化同样如此。

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
    本文链接:https://blog.csdn.net/qq_16933601/article/details/106478780

    线索二叉树进行遍历

      下图中是一个按照中序遍历建立的线索二叉树。其中,实线表示指针,指向的是左孩子或者右孩子。虚线表示线索,指向的是该结点的直接前趋或者直接后继。
    在这里插入图片描述
      使用线索二叉树时,会经常遇到一个问题,如上图中,结点8的直接后继直接通过指针域获得,为结点5;而由于结点5的度为2 ,无法利用指针域指向后继结点,整个链表断掉了。当在遍历过程,遇到这种问题是解决的办法就是:寻找先序、中序、后序遍历的规律,找到下一个结点。
      在先序遍历过程中,如果结点因为有右孩子导致无法找到其后继结点,如果结点有左孩子,则后继结点是其左孩子;否则,就一定是右孩子。拿上图举例,结点2的后继结点是其左孩子结点4 ,如果结点4不存在的话,就是结点5 。
      在中序遍历过程中,结点的后继是遍历其右子树时访问的第一个结点,也就是右子树中位于最左下的结点。例如上图中结点5,后继结点为结点11,是其右子树中位于最左边的结点。反之,结点的前趋是左子树最后访问的那个结点。
      后序遍历中找后继结点需要分为3 种情况:
      1. 如果该结点是二叉树的根,后继结点为空;
      2. 如果该结点是父结点的右孩子(或者是左孩子,但是父结点没有右孩子),后继结点是父结点;
      3. 如果该结点是父结点的左孩子,且父结点有右子树,后继结点为父结点的右子树在后序遍历列出的第一个结点。
      使用后序遍历建立的线索二叉树,在真正使用过程中遇到链表的断点时,需要访问父结点,所以在初步建立二叉树时,宜采用三叉链表做存储结构。
    遍历线索二叉树非递归代码实现:

    /**
     * @Description: 中序遍历线索二叉树 非递归
     * @Param: BiThrTree p 二叉树的结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void InOrderThraverse_Thr(BiThrTree p)
    {
        while (p)
        {
            //一直找左孩子,最后一个为中序序列中排第一的
            while (p->Ltag == Link)
            {
                p = p->lchild;
            }
             //此时p指向中序遍历序列的第一个结点(最左下的结点)  
             
            //打印(访问)其左子树为空的结点  
            printf("%c ", p->data); 
            //当结点右标志位为1 时,直接找到其后继结点
            while (p->Rtag == Thread && p->rchild != NULL)
            {
                p = p->rchild;
                //访问后继结点 
                printf("%c ", p->data);
            }
            
            //当p所指结点的rchild指向的是孩子结点而不是线索时,p的后继应该是其右子树的最左下的结点,即遍历其右子树时访问的第一个节点  
            p = p->rchild;
        }
    }
    

    完整代码如下:

    /*
     * @Description: 线索二叉树
     * @Version: V1.0
     * @Autor: Carlos
     * @Date: 2020-05-20 16:31:33
     * @LastEditors: Carlos
     * @LastEditTime: 2020-06-01 20:19:22
     */
    #include <stdio.h>
    #include <stdlib.h>
    #define TElemType char //宏定义,结点中数据域的类型
    //枚举,Link 为0,Thread 为1
    typedef enum
    {
        Link,
        Thread
    } PointerTag;
    //结点结构构造
    typedef struct BiThrNode
    {
        //数据域
        TElemType data;                    
        //左孩子,右孩子指针域
        struct BiThrNode *lchild, *rchild; 
        //标志域,枚举类型
        PointerTag Ltag, Rtag;             
    } BiThrNode, *BiThrTree;
    BiThrTree pre = NULL;
    /**
     * @Description: 初始化二叉树
     * @Param: BiTree *T 二叉树的结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void CreateBiTree(BiThrTree *T){
        *T=(BiThrNode*)malloc(sizeof(BiThrNode));
        (*T)->data=1;
        (*T)->lchild=(BiThrNode*)malloc(sizeof(BiThrNode));
        (*T)->rchild=(BiThrNode*)malloc(sizeof(BiThrNode));
       
        (*T)->lchild->data=2;
        (*T)->lchild->lchild=(BiThrNode*)malloc(sizeof(BiThrNode));
        (*T)->lchild->rchild=(BiThrNode*)malloc(sizeof(BiThrNode));
        (*T)->lchild->rchild->data=5;
        (*T)->lchild->rchild->lchild=NULL;
        (*T)->lchild->rchild->rchild=NULL;
       
        (*T)->rchild->data=3;
        (*T)->rchild->lchild=(BiThrNode*)malloc(sizeof(BiThrNode));
        (*T)->rchild->lchild->data=6;
        (*T)->rchild->lchild->lchild=NULL;
        (*T)->rchild->lchild->rchild=NULL;
       
        (*T)->rchild->rchild=(BiThrNode*)malloc(sizeof(BiThrNode));
        (*T)->rchild->rchild->data=7;
        (*T)->rchild->rchild->lchild=NULL;
        (*T)->rchild->rchild->rchild=NULL;
       
        (*T)->lchild->lchild->data=4;
        (*T)->lchild->lchild->lchild=NULL;
        (*T)->lchild->lchild->rchild=NULL;
    }
    
    /**
     * @Description: 采用前序初始化二叉树  中序和后序只需改变赋值语句的位置即可
     * @Param: BiThrTree *tree 二叉树的结构体指针数组
     * @Return: 无
     * @Author: Carlos
     */
    void CreateTree(BiThrTree *tree)
    {
        char data;
        scanf("%c", &data);
        if (data != '#')
        {
            if (!((*tree) = (BiThrNode *)malloc(sizeof(BiThrNode))))
            {
                printf("申请结点空间失败");
                return;
            }
            else
            {
                //采用前序遍历方式初始化二叉树
                (*tree)->data = data;          
                //初始化左子树 
                CreateTree(&((*tree)->lchild));
                //初始化右子树 
                CreateTree(&((*tree)->rchild)); 
            }
        }
        else
        {
            *tree = NULL;
        }
    }
    
    /**
     * @Description: 中序对二叉树进行线索化
     * @Param: BiThrTree p 二叉树的结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void InThreading(BiThrTree p)
    {
        //如果当前结点存在
        if (p)
        {
            //递归当前结点的左子树,进行线索化
            InThreading(p->lchild); 
            //如果当前结点没有左孩子,左标志位设为1,左指针域指向上一结点pre
            if (!p->lchild)
            {
                 //前驱线索
                p->Ltag = Thread;
                 //左孩子指针指向前驱
                p->lchild = pre; 
            }
            //如果pre 没有右孩子,右标志位设为1,右指针域指向当前结点。
            if (pre && !pre->rchild)
            {
                //后继线索
                pre->Rtag = Thread;
                //前驱右孩子指针指向后继(当前结点p)
                pre->rchild = p;
            }
            pre = p;                //pre 指向当前结点
            InThreading(p->rchild); //递归右子树进行线索化
        }
    }
    
    /**
     * @Description: 中序遍历线索二叉树 非递归
     * @Param: BiThrTree p 二叉树的结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void InOrderThraverse_Thr(BiThrTree p)
    {
        while (p)
        {
            //一直找左孩子,最后一个为中序序列中排第一的
            while (p->Ltag == Link)
            {
                p = p->lchild;
            }
             //此时p指向中序遍历序列的第一个结点(最左下的结点)  
             
            //打印(访问)其左子树为空的结点  
            printf("%c ", p->data); 
            //当结点右标志位为1 时,直接找到其后继结点
            while (p->Rtag == Thread && p->rchild != NULL)
            {
                p = p->rchild;
                //访问后继结点 
                printf("%c ", p->data);
            }
            
            //当p所指结点的rchild指向的是孩子结点而不是线索时,p的后继应该是其右子树的最左下的结点,即遍历其右子树时访问的第一个节点  
            p = p->rchild;
        }
    }
    int main()
    {
        BiThrTree t;
        printf("输入前序二叉树:\n");
        CreateTree(&t);
        // CreateBiTree(&t);
        InThreading(t);
        printf("输出中序序列:\n");
        InOrderThraverse_Thr(t);
        return 0;
    }
    
    

    双向线索二叉树的概念

      在遍历使用中序序列创建的线索二叉树时,对于其中的每个结点,即使没有线索的帮助
    下,也可以通过中序遍历的规律找到直接前趋和直接后继结点的位置。也就是说,建立的线索二叉链表可以从两个方向对结点进行中序遍历。线索二叉链表可以从第一个结点往后逐个遍历。但是起初由于没有记录中序序列中最后一个结点的位置,所以不能实现从最后一个结点往前逐个遍历。双向线索链表的作用就是可以让线索二叉树从两个方向实现遍历。

    双向线索二叉树的实现过程

      在线索二叉树的基础上,额外添加一个结点。此结点的作用类似于链表中的头指针,数据域不起作用,只利用两个指针域(由于都是指针,标志域都为0 )。左指针域指向二叉树的树根,确保可以正方向对二叉树进行遍历;同时,右指针指向线索二叉树形成的线性序列中的最后一个结点
      这样,二叉树中的线索链表就变成了双向线索链表,既可以从第一个结点通过不断地找后继结点进行遍历,也可以从最后一个结点通过不断找前趋结点进行遍历。
    在这里插入图片描述
    代码实现

    /**
     * @Description: 建立双向线索链表
     * @Param: BiThrTree *h 结构体指针数组 BiThrTree t 结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void InOrderThread_Head(BiThrTree *h, BiThrTree t)
    {
        //初始化头结点
        (*h) = (BiThrTree)malloc(sizeof(BiThrNode));
        if ((*h) == NULL)
        {
            printf("申请内存失败");
            return;
        }
        (*h)->rchild = *h;
        (*h)->Rtag = Link;
        //如果树本身是空树
        if (!t)
        {
            (*h)->lchild = *h;
            (*h)->Ltag = Link;
        }
        else
        {
            //pre 指向头结点
            pre = *h;        
            //头结点左孩子设为树根结点 
            (*h)->lchild = t; 
            (*h)->Ltag = Link;
            //线索化二叉树,pre 结点作为全局变量,线索化结束后,pre 结点指向中序序列中最后一个结点
            InThreading(t); 
            //链接最后一个节点(最右下角G节点)和头结点
            pre->rchild = *h;
            pre->Rtag = Thread;
            //将头结点的右指针指向中序序列最后一个节点
            (*h)->rchild = pre;
        }
    }
    

    双向线索二叉树的遍历

      双向线索二叉树遍历时,如果正向遍历,就从树的根结点开始。整个遍历过程结束的标志是:当从头结点出发,遍历回头结点时,表示遍历结束。

    /**
     * @Description: 中序正向遍历双向线索二叉树
     * @Param: BiThrTree h 二叉树的结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void InOrderThraverse_Thr(BiThrTree h)
    {
        BiThrTree p;
        //p 指向根结点
        p = h->lchild; 
        while (p != h)
        {
            //当ltag = 0 时循环到中序序列的第一个结点。
            while (p->Ltag == Link) 
            {
                p = p->lchild;
            }
            //显示结点数据,可以更改为其他对结点的操作
            printf("%c ", p->data); 
            
            //如果当前节点经过了线索化,直接利用该节点访问下一节点
            while (p->Rtag == Thread && p->rchild != h)
            {
                p = p->rchild;
                printf("%c ", p->data);
            }
            //如果没有线索化或者跳出循环,说明其含有右子树。p 进入其右子树
            p = p->rchild; 
        }
    }
    

      逆向遍历线索二叉树的过程即从头结点的右指针指向的结点出发,逐个寻找直接前趋结点,结束标志同正向遍历一样:

    /**
     * @Description: 中序逆方向遍历线索二叉树 和正向的区别在于 p = p->rchild 。逆向遍历我们要一直访问到右子树的最后一个。
     * @Param: BiThrTree h 二叉树的结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void InOrderThraverse_Thr(BiThrTree h)
    {
        BiThrTree p;
        p = h->rchild;
        while (p != h)
        {
            while (p->Rtag == Link)
            {
                p = p->rchild;
            }
            printf("%c", p->data);
            //如果lchild 为线索,直接使用,输出
            while (p->Ltag == Thread && p->lchild != h)
            {
                p = p->lchild;
                printf("%c", p->data);
            }
            p = p->lchild;
        }
    }
    

      完整代码如下

    /*
     * @Description: 双向线索二叉树的遍历
     * @Version: V1.0
     * @Autor: Carlos
     * @Date: 2020-06-01 20:46:38
     * @LastEditors: Carlos
     * @LastEditTime: 2020-06-01 21:17:23
     */
    #include <stdio.h>
    #include <stdlib.h>
    //宏定义,结点中数据域的类型
    #define TElemType char 
    //枚举,Link 为0,Thread 为1
    typedef enum
    {
        Link,
        Thread
    } PointerTag;
    //结点结构构造
    typedef struct BiThrNode
    {
        //数据域
        TElemType data;    
        //左孩子,右孩子指针域                
        struct BiThrNode *lchild, *rchild; 
        //标志域,枚举类型
        PointerTag Ltag, Rtag;             
    } BiThrNode, *BiThrTree;
    BiThrTree pre = NULL;
    /**
     * @Description: 采用前序初始化二叉树  中序和后序只需改变赋值语句的位置即可
     * @Param: BiThrTree *tree 二叉树的结构体指针数组
     * @Return: 无
     * @Author: Carlos
     */
    void CreateTree(BiThrTree *tree)
    {
        char data;
        scanf("%c", &data);
        if (data != '#')
        {
            if (!((*tree) = (BiThrNode *)malloc(sizeof(BiThrNode))))
            {
                printf("申请结点空间失败");
                return;
            }
            else
            {
                //采用前序遍历方式初始化二叉树
                (*tree)->data = data;           
                //初始化左子树
                CreateTree(&((*tree)->lchild)); 
                //初始化右子树
                CreateTree(&((*tree)->rchild)); 
            }
        }
        else
        {
            *tree = NULL;
        }
    }
    /**
     * @Description: 中序对二叉树进行线索化 
     * @Param: BiThrTree p 二叉树的结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void InThreading(BiThrTree p)
    {
        //如果当前结点存在
        if (p)
        {
            //递归当前结点的左子树,进行线索化
            InThreading(p->lchild); 
            //如果当前结点没有左孩子,左标志位设为1,左指针域指向上一结点pre
            if (!p->lchild)
            {
                p->Ltag = Thread;
                //pre为头结点,链接中序遍历的第一个节点(最左边的结点)与头结点
                p->lchild = pre;
            }
            //如果pre 没有右孩子,右标志位设为1,右指针域指向当前结点。
            if (pre && !pre->rchild)
            {
                pre->Rtag = Thread;
                pre->rchild = p;
            }
            //pre 指向当前结点
            pre = p;             
            //递归右子树进行线索化   
            InThreading(p->rchild); 
        }
    }
    
    /**
     * @Description: 建立双向线索链表
     * @Param: BiThrTree *h 结构体指针数组 BiThrTree t 结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void InOrderThread_Head(BiThrTree *h, BiThrTree t)
    {
        //初始化头结点
        (*h) = (BiThrTree)malloc(sizeof(BiThrNode));
        if ((*h) == NULL)
        {
            printf("申请内存失败");
            return;
        }
        (*h)->rchild = *h;
        (*h)->Rtag = Link;
        //如果树本身是空树
        if (!t)
        {
            (*h)->lchild = *h;
            (*h)->Ltag = Link;
        }
        else
        {
            //pre 指向头结点
            pre = *h;        
            //头结点左孩子设为树根结点 
            (*h)->lchild = t; 
            (*h)->Ltag = Link;
            //线索化二叉树,pre 结点作为全局变量,线索化结束后,pre 结点指向中序序列中最后一个结点
            InThreading(t); 
            //链接最后一个节点(最右边下角)和头结点
            pre->rchild = *h;
            pre->Rtag = Thread;
            (*h)->rchild = pre;
        }
    }
    
    /**
     * @Description: 中序正向遍历双向线索二叉树
     * @Param: BiThrTree h 二叉树的结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void InOrderThraverse_Thr(BiThrTree h)
    {
        BiThrTree p;
        //p 指向根结点
        p = h->lchild; 
        while (p != h)
        {
            //当ltag = 0 时循环到中序序列的第一个结点。
            while (p->Ltag == Link) 
            {
                p = p->lchild;
            }
            //显示结点数据,可以更改为其他对结点的操作
            printf("%c ", p->data); 
            
            //如果当前节点经过了线索化,直接利用该节点访问下一节点
            while (p->Rtag == Thread && p->rchild != h)
            {
                p = p->rchild;
                printf("%c ", p->data);
            }
            //如果没有线索化或者跳出循环,说明其含有右子树。p 进入其右子树
            p = p->rchild; 
        }
    }
    /**
     * @Description: 中序逆方向遍历线索二叉树 和正向的区别在于 p = p->rchild 。逆向遍历我们要一直访问到右子树的最后一个。
     * @Param: BiThrTree h 二叉树的结构体指针
     * @Return: 无
     * @Author: Carlos
     */
    void InOrderThraverse_Thr(BiThrTree h)
    {
        BiThrTree p;
        p = h->rchild;
        while (p != h)
        {
            while (p->Rtag == Link)
            {
                p = p->rchild;
            }
            printf("%c", p->data);
            //如果lchild 为线索,直接使用,输出
            while (p->Ltag == Thread && p->lchild != h)
            {
                p = p->lchild;
                printf("%c", p->data);
            }
            p = p->lchild;
        }
    }
    int main()
    {
        BiThrTree t;
        BiThrTree h;
        printf("输入前序二叉树:\n");
        CreateTree(&t);
        InOrderThread_Head(&h, t);
        printf("输出中序序列:\n");
        InOrderThraverse_Thr(h);
        return 0;
    }
    

    总结

      二叉树的线索化就是充分利用了节点的空指针域。所有节点线索化的过程也就是当前节点指针和上一结点指针进行链接的过程,不断递归所有节点。线索化二叉树的访问,以中序遍历为例,首先需要访问到中序遍历的第一个节点,若当前节点进行了线索化,可以直接利用该节点进行下一节点的访问。否则,说明当前节点含有右子树,则进入右子树进行访问。双向线索二叉树的建立,其实就将头结点的左指针和树的根节点链接,头结点的右指针和中序遍历的最后一个节点的链接。这样我们就可以进行双向访问了。当从头结点出发,遍历回头结点时,表示遍历结束。

    展开全文
  • 本文实例讲述了C语言实现线索二叉树的定义与遍历。分享给大家供大家参考,具体如下: #include #include typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // ...
  • 线索二叉树:将指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树。 其实线索二叉树相当于把一棵二叉树变成一个双向链表,这有利于方便插入删除结点和查找某个结点的操作...

    线索二叉树将指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树

    其实线索二叉树相当于把一棵二叉树变成一个双向链表,这有利于方便插入删除结点和查找某个结点的操作。

    线索化对二叉树以某种次序遍历使其变为线索二叉树的过程

    线索二叉树的结点结构:
    lchild - ltag - data - rtag - rchild
    其中:
    1、ltag为0使指向该结点的左孩子,为1时指向该结点的前驱。
    2、rtag为0使指向该结点的右孩子,为1时指向该结点的后继。
    3、在每个结点增设两个标志域ltag和rtag,这两个标志域只存放0和1数字的布尔型变量,其占用内存空间小于指针变量。

    实现线索二叉树结构程序:

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

    其中线索化的实质就是将二叉链表中的空指针改为指向前去或后继的线索,由于前驱和后继的信息只有在遍历该二叉树时才能得到,所以线索化的过程就是在遍历的过程中修改空指针的过程。

    举个例子:中序遍历进行中序线索化

    void InThreading(BiThrTree p)
    {
    	if(p)
    	{
    		InThreading(p->lchild);			//递归左子树线索化
    
    		if (!p->lchild)			    //没有左子树
    		{    
    			p->LTag = Thread;		    //前驱线索
    			p->lchild = pre;		    //左孩子指针指向前驱
    		}
    
    		if(!pre->rchild)			    //前驱没有右孩子
    		{
    			p->RTag = Thread;		    //后继线索
    			p->rchild = p;			    //前驱右孩子指针指向后继
    		}
    		pre = p;
    		InThreading(P->rchild);			//递归右子树线索化
    	}
    }

    创建线索二叉树后,进行遍历,相当于操作一个双向链表结构,和    双向链表结构一样,在二叉树线索链表上添加一个头结点。

    程序:

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

    注意:
    1、充分利用了空指针域的空间,节省空间,保证创建时的一次遍历就可以终生受用前驱后继的信息,节省时间。
    2、如果所用二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继,建议采用线索二叉链表的存储结构。

    展开全文
  • 中序线索二叉树

    2021-08-01 23:45:38
    线索二叉树线索二叉树的基本概念中序线索二叉树的构造中序线索二叉树的遍历 线索二叉树的基本概念 中序线索二叉树的构造 中序线索二叉树的遍历

    线索二叉树的基本概念

    二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到,因此线索化二叉树的实现就是遍历一次二叉树

    以中序线索二叉树的建立为例:

    1. 附设指针pre指向刚刚访问过的结点,指针p指向正在访问的结点,即pre指向p的前驱。
    2. 在中序遍历的过程中,检查p的左指针是否为空,若为空就将它指向pre; 检查pre的右指针是否为空,若为空就将它指向p

    中序线索二叉树的构造

    InThread

    通过中序遍历对二叉树线索化的递归算法(就是让结点的空指针指向其中序遍历的前驱或后继结点)

    //通过中序遍历对二叉树线索化的递归算法(就是让结点的空指针指向其前驱或后继结点)
    //中序线索二叉树的构造, 左根右
    void InThread(ThreadTree &p,ThreadTree &pre){
        if(p != NULL){
            InThread(p->lchild,pre);//递归,线索化左子树
            if(p->lchild == NULL){//左子树为空,建立前驱线索
                p->lchild=pre;
                p->ltag=1;
            }
            if(pre!=NULL && pre->rchild==NULL){
                pre->rchild=p;//建立前驱结点的后继线索
                pre->rtag=1;
            }
            pre=p;//标记当前结点成为刚刚访问过的结点
            InThread(p->rchild, pre);//递归,线索化右子树
        }//if(p != NULL)
    }
    

    CreateInThread

    通过中序遍历建立中序线索二叉树的主过程算法如下:
    这个函数的作用就是建立中序线索二叉树,调用InThread函数,并处理遍历的最后一个结点。
    CreateInThread和InThread的具体关系:前者可以看做统领大局的工头,后者是具体搬砖的小工

    //通过中序遍历建立中序线索二叉树的主过程算法如下:
    void CreateInThread(ThreadTree &T){
        ThreadTree pre=NULL;
        if(T){              //非空二叉树,线索化
            InThread(T,pre);//线索化二叉树
            pre->rchild==NULL;//处理遍历的最后一个结点
            pre->rtag=1;//@@@
        }
    }
    

    带头结点的线索二叉树

    如果不想让中序遍历的第一个结点的lchild 和最后一个结点的rchild 为NULL, 则必须要加头结点,不能将之指向树根,因为如下图所示,根的前驱结点和后继结点已经指向了根,如果再把中序遍历的第一个结点的lchild 和最后一个结点的rchild指向根节点,则遍历的时候无法保证结果的正确性。

    总而言之即:
    若让中序遍历的第一个结点的lchild 和最后一个结点的rchild 不为NULL,则必须额外添加一个Head头结点,不能简单指向根节点
    在这里插入图片描述

    中序线索二叉树的遍历

    中序线索二叉树的结点中隐含了线索二叉树的前驱和后继信息。在对其进行遍历时,只要先找到序列中的第一个结点,然后依次找到结点的后继,直至其后继为空.

    Firstnode

    求中序线索二叉树中,中序序列下的第一个结点

    //求中序线索二叉树中,中序序列下的第一个结点
    ThreadNode *Firstnode(ThreadNode *p){
        //printf("Firstnode:");
        while(p->ltag==0){
            p=p->lchild;//最左下结点(不一定是叶节点)
        }
        return p;
    }
    

    Nextnode

    求中序线索二叉树中,结点p在中序序列下的后继

    //求中序线索二叉树中,结点p在中序序列下的后继
    ThreadNode *Nextnode(ThreadNode *p){
        if(p->rtag==0){
            return Firstnode(p->rchild);
        }
        else{
            return p->rchild;//rtag==1 直接返回后继线索
        }
    }
    

    Inorder

    可以写出不含头结点的中序线索二叉树的中序遍历算法

    //利用上面的两个算法,
    //可以写出不含头结点的中序线索二叉树的中序遍历算法
    void Inorder(ThreadNode *T){
        for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p)){
            visit(p);
        }
    }
    
    

    完整测试代码

    完整测试代码c++

    注意:

    1. 还是要先创建二叉树,然后再对二叉树进行中序遍历线索化
    2. 在创建二叉树的时候要对ltag rtag进行初始化为0,表示lchild,rchild指向的是左/右孩子(而非前驱/后继),且初始化不能在结构体的定义中初始化,因为定义结构体时,并未给其分配内存,所以初值是无法存储的。应该声明结构体变量后,手工赋值。下面代码中是在malloc后就初始化
    3. 因为线索化二叉树后各个结点之间都穿成一个环了,所以在中序递归遍历和后序递归销毁的函数中需要对ltag rtag进行判断。
    //线索二叉树
    #include<stdio.h>
    #include<stdlib.h>
    #define ElemType char
    //tag为0表示指向左/右孩子,为1表示指向结点的前驱/后继
    typedef struct ThreadNode{
        ElemType data;//数据元素
        struct ThreadNode *lchild,*rchild;//左右孩子指针
        int ltag;//因为定义结构体时,并未给其分配内存,所以初值是无法存储的。应该声明结构体变量后,手工赋值
        int rtag;//左右线索标记
    }ThreadNode,*ThreadTree;
    
    void visit(ThreadTree T){
        printf("%c ",T->data);
    }
    
    //中序线索二叉树的构造, 左根右
    void InThread(ThreadTree &p,ThreadTree &pre){
        if(p != NULL){
            InThread(p->lchild,pre);//递归,线索化左子树
            if(p->lchild == NULL){//左子树为空,建立前驱线索
                p->lchild=pre;
                p->ltag=1;
            }
            if(pre!=NULL && pre->rchild==NULL){
                pre->rchild=p;//建立前驱结点的后继线索
                pre->rtag=1;
            }
            pre=p;//标记当前结点成为刚刚访问过的结点
            InThread(p->rchild, pre);//递归,线索化右子树
        }//if(p != NULL)
    }
    
    //通过中序遍历建立中序线索二叉树的主过程算法如下:
    void CreateInThread(ThreadTree &T){
        //ThreadNode *Head = (ThreadNode*)malloc(sizeof(ThreadNode));
       // Head->lchild=T;
        //Head->ltag=1;
        //ThreadTree pre=T;
        ThreadTree pre=NULL;
        if(T){              //非空二叉树,线索化
            InThread(T,pre);//线索化二叉树
    
            //Head->rchild=pre;
            //Head->rtag=1;
    
            pre->rchild==NULL;
            //pre->rchild=T;//处理遍历的最后一个结点
            pre->rtag=1;
        }
    }
    
    
    //求中序线索二叉树中,中序序列下的第一个结点
    ThreadNode *Firstnode(ThreadNode *p){
        //printf("Firstnode:");
        while(p->ltag==0){
            p=p->lchild;//最左下结点(不一定是叶节点)
        }
        return p;
    }
    
    //求中序线索二叉树中,结点p在中序序列下的后继
    ThreadNode *Nextnode(ThreadNode *p){
        if(p->rtag==0){
            return Firstnode(p->rchild);
        }
        else{
            return p->rchild;//rtag==1 直接返回后继线索
        }
    }
    
    //利用上面的两个算法,
    //可以写出不含头结点的中序线索二叉树的中序遍历算法
    void Inorder(ThreadNode *T){
        for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p)){
            visit(p);
        }
    }
    
    //创建线索二叉树,按前序输入, #表示空节点
    bool CreateThreadTree(ThreadTree &T){
        ElemType ch;
        scanf("%c", &ch);
        if(ch == '#'){
            //printf("您要创建一棵空树吗?\n");
            T=NULL;
            return false;
        }
        else{
            T=(ThreadTree)malloc(sizeof(ThreadNode));
            T->ltag=T->rtag=0;
            if(!T){
                printf("malloc failure\n");
                return false;
            }
            T->data = ch;
            CreateThreadTree(T->lchild);
            CreateThreadTree(T->rchild);
            return true;
        }
    }
    
    bool DestroyThreadTree(ThreadTree T){
        if(T==NULL){
            printf("空节点\n");
            return false;
        }
        if(T->ltag!=1)
            DestroyThreadTree(T->lchild);
        if(T->rtag!=1)
            DestroyThreadTree(T->rchild);
        printf("销毁%c\n",T->data);
        free(T);//@@@'
        T=NULL;
        return true;
    }
    
    //中序遍历线索二叉树
    void InOrder(ThreadTree T){
        if(T){
            if(T->ltag!=1)
                InOrder(T->lchild);
    
            visit(T);
    
            if(T->rtag != 1)
                InOrder(T->rchild);
        }
    }
    int main(){
        ThreadTree T=NULL;
        printf("按前序输入二叉树中节点的值(输入#表示空节点)\n");
        CreateThreadTree(T);//输入前序,建立二叉树
    
        CreateInThread(T);//通过中序遍历建立中序线索二叉树
        ThreadNode *p=Firstnode(T);//求中序遍历下的第一个结点
        printf("\n中序遍历的第一个结点p: %c\n",p->data);
        ThreadNode* r=Nextnode(p);//求中序遍历下p的后继
        printf("p的后继r: %c\n",r->data);
        printf("中序遍历线索二叉树(递归InOrder ≈ 正常BinaryTree遍历): \n");
        InOrder(T);
        printf("\n");
    
        printf("\n中序遍历线索二叉树(非递归Inorder ≈ Firstnode+Nextnode): \n");
        Inorder(T);
    
        printf("\n用完要记得销毁哦!\n");
        DestroyThreadTree(T);
    
        return 0;
    }
    

    输入样例

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

    测试结果

    在这里插入图片描述

    展开全文
  • 后序线索二叉树

    2021-08-02 13:47:02
    后序线索二叉树后序线索二叉树的构造三叉链表结构PostThreadCreatePostThread后序线索二叉树的遍历FirstnodeNextnode完整测试代码c++测试样例1测试样例2 后序线索二叉树的构造 三叉链表结构 结构体要用三叉链表,...
  • 线索二叉树、中序线索二叉树的创建和遍历

    千次阅读 多人点赞 2020-11-10 20:49:39
    线索二叉树 按照某种遍历次序对二叉树进行遍历,可以把二叉树中的所有结点排成一个线性序列。在具体应用中,有时需要访问二叉树中的结点在某种遍历序列中的前驱和后继,此时,在存储结构中应保存结点在某种遍历序列...
  • 先序线索二叉树,中序线索二叉树,后序线索二叉树之间的对比 结论: 1.先序线索二叉树找前驱节点困难,找后继节点简单 后序线索二叉树找后继节点困难,找前驱节点简单 中序线索二叉树找前驱节点,后继节点都很...
  • 二叉树模版:包括先序中序构造,后序中序构造,结点的度,统计度为n的结点个数,高度,宽度,结点的最大值,交换每个结点的左右,删除...线索二叉树:包括先序中序构造,中序线索化,中序线索化遍历; 包括测试主函数。
  • 线索二叉树简述

    2021-03-12 10:30:42
    线索二叉树 首先我们回忆一下二叉树的前中后序遍历方式: 先序遍历序列:1 2 4 5 3 6 中序遍历序列:4 2 5 1 6 3 后序遍历序列:4 5 2 6 3 1 我们通过这样的遍历,由一个树形结构得到了一个线性的结构(遍历序列)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,435
精华内容 4,974
关键字:

线索二叉树