精华内容
下载资源
问答
  • 数据结构线索树与树和森林PPT学习教案.pptx
  • 何谓线索二叉树 遍历结果是求得结点的一个线性序列指向该线性序列前驱和后继的指针称线索包含线索的存储结构称为线索链表与其相应的二叉树称为线索二叉树对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化2...
  • 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏
  • 数据结构 线索二叉树

    2014-04-27 15:06:01
    当以二叉链表作为储存结构时,只能找到结点的左右孩子的信息,而不能直接找到结点的前驱后继,所以我们在每个结点上增加两个指针域fwd和bawd,分别指示结点在任一次序遍历时得到的前驱后继信息。
  • 数据结构-线索二叉树

    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)线索子树不能共用。

    展开全文
  • 线索二叉树应用实验 实验...线索二叉树是为了快速求解二叉树中结点在指定次序下的前驱和后继而将二叉链表中空的左右孩子指针分别改为指向其前驱和后继结点而得到的结构反映了运算对数据结构的设计的影响因此首先要了解
  • 数据结构 线索二叉树 原理及实现

    千次阅读 2014-11-16 15:58:00
    通过考察各种二叉链表,不管儿叉树的形态如何,空链域的个数总是多过非空链域的个数。准确的说,n各结点的二叉链表共有2n个链域,... 记ptr指向二叉链表中的一个结点,以下是建立线索的规则:  (1)如果ptr->lc
    通过考察各种二叉链表,不管儿叉树的形态如何,空链域的个数总是多过非空链域的个数。准确的说,n各结点的二叉链表共有2n个链域,非空链域为n-1个,但其中的空链域却有n+1个。如下图所示。 
    


        因此,提出了一种方法,利用原来的空链域存放指针,指向树中其他结点。这种指针称为线索。

        记ptr指向二叉链表中的一个结点,以下是建立线索的规则:

        (1)如果ptr->lchild为空,则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱;

        (2)如果ptr->rchild为空,则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继;

        显然,在决定lchild是指向左孩子还是前驱,rchild是指向右孩子还是后继,需要一个区分标志的。因此,我们在每个结点再增设两个标志域ltag和rtag,注意ltag和rtag只是区分0或1数字的布尔型变量,其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。


        其中:

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

        (2)rtag为0时指向该结点的右孩子,为1时指向该结点的后继;

        (3)因此对于上图的二叉链表图可以修改为下图的养子。




    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    typedef struct Binode
    {
        char data;
        struct Binode *lchild,*rchild;
        int ltag,rtag;
    } Binode,*Bitree;
    Bitree pre;
    void CreatTREE(Bitree &T)
    {
        char ch;
        scanf("%c",&ch);
        if(ch==' ')
        {
            T=NULL;
        }
        else
        {
            T=(Bitree)malloc(sizeof(Binode));
            T->data=ch;
            T->ltag=0;
            T->rtag=0;
            CreatTREE(T->lchild);
            CreatTREE(T->rchild);
        }
        return;
    }
    void travel_threadtree(Bitree H)     //中序遍历线索树 从头节点开始
    {
        Bitree p;
        p=H->lchild;                     //p为二叉树头节点
        while(p!=H)                       
        {
            while(p->ltag==0)            //有左子树 则 一直往下
                p=p->lchild;
            printf("%c ",p->data);       
            while(p->rtag==1&&p->rchild!=H)  //根据它的线索一直往后输出
            {
                p=p->rchild;
                printf("%c ",p->data);
            }
            p=p->rchild;                   //当没有线索时 表示有右子树
        }
        return;
    }
    void thread(Bitree T)               //线索化
    {
        if(T)
        {
            thread(T->lchild);
            if(!T->lchild)
            {
                T->ltag=1;
                T->lchild=pre;
            }
            if(!pre->rchild)
            {
                pre->rtag=1;
                pre->rchild=T;
            }
            pre=T;                    //顺序是左子树 节点 右子树的中序遍历 所有 放这里
            thread(T->rchild);
        }
        return;
    }
    void threading_(Bitree &H,Bitree T)  //新增头节点
    {
        H=(Bitree)malloc(sizeof(Binode));
        H->rchild=H;
        H->rtag=0;
        if(!T)                //二叉树为空
        {
            H->lchild=H;
            H->ltag=0;
        }
        else
        {
            pre=H;
            H->lchild=T;
            H->ltag=0;
            thread(T);
            H->rtag=1;
            H->rchild=pre;   //
            pre->rchild=H;    // 构成循环  以备跳出
        }
        return;
    }
    int main()
    {
        Bitree T,H;
        CreatTREE(T);
        threading_(H,T);
        travel_threadtree(H); 
        return 0;
    }
    





    展开全文
  • 数据结构线索二叉树

    千次阅读 2018-08-15 16:15:10
    数据结构线索二叉树 1.二叉链表中空间资源的浪费 我们利用节点建立了二叉链表,但是我们发现二叉链表中存在这许多空指针,那么这部分空间就被浪费了,我们应该想办法解决这个问题 假设有一个节点个数为...

    数据结构—线索二叉树

    1.二叉链表中空间资源的浪费

    我们利用节点建立了二叉链表,但是我们发现二叉链表中存在这许多空指针,那么这部分空间就被浪费了,我们应该想办法解决这个问题

    image.png

    假设有一个节点个数为n的二叉链表,那么其中就有2n个指针域,n个节点就会有n-1个分支线树,也就是说就会有2n-(n-1)=n+1个空指针域。如上图,十个节点的二叉树就会有十一个空指针域。

    我们在上一篇博客中也说过,有三种遍历二叉树的方法(前序,中序,后序),不管是哪一种遍历方法,在遍历时都会产生特定的前后顺序。但是,实际在树的结构中,我们只知道一个节点的两个孩子节点的指针,但是不知道遍历时真正的前驱和后继,所以我们干脆在第一次遍历时就利用这些空指针域,让其指向该节点的前驱或者后继。

    • 我们把这种指向前驱和后继的指针称为线索,加上线索的二叉 链表称为线索链表,相应的二叉树称为线索二叉树

    2.线索化

    对于线索二叉树,我们有这样的规定:
    • 如果一个节点的左孩子节点为空,则让该指针指向其前驱节点
    • 如果一个节点的右孩子节点为空,则让该指针指向其后继节点

    例如上面的二叉树,我们可以用中序遍历的方法使其线索化:

    中序遍历顺序:H,D,I,B,J,E,A,F,C,G

    image.png

    在这次遍历建立了线索二叉树后,我们再此遍历就不需要使用之前的遍历方法了,因为我们已经将二叉树中叶子节点中的空指针充分利用,其实等于将我们的二叉树变成了一个双向链表,这样我们的插入删除节点,查找节点都更方便。

    但现在有一个问题,我如何直到一个节点的左孩子指针是指向它的左孩子还是它的前驱呢?同理,我也没法直到这个节点的右孩子指针是指向其右孩子节点还是其后继。

    wile解决这个问题,我们设立如下的数据结构:

    typedef enum {Link,Thread} PointerTag;//孩子指针域状态(指向孩子节点或前后驱)
    
    typedef struct BiThrNode
    {
        int data;
        BiThrNode *lchild,*rchild;
        PointerTag LTag;    //左孩子指针状态
        PointerTag RTag;    //右孩子指针状态
    } BiThrNode,*BiThrTree;
    我们给每个节点新增两个枚举类型的状态标记,若该标记为Link,则表名:该指针指向的是该节点的孩子节点。若该标记为Thread,则表示该指针指向的是这个节点的前驱或后继。
    接下来就是线索化的过程,下面是中序线索化的核心代码:
    BiThrTree pre;//前驱节点(全局变量)
    
    void InThreading(BiThrTree T)
    {
        if(T)
        {
            InThreading(T->lchild);
            if(!T->lchild)
            {
                T->LTag = Thread;
                T->lchild = pre;
            }
            if(pre != NULL && !pre->rchild)
            {
                pre->RTag = Thread;
                pre->rchild = T;
            }
            pre = T;
            InThreading(T->rchild);
        }
    }

    类似于中序遍历的代码,只不过把中间的输出语句改为了其他的一些操作,这里我们来分析一下:

    • 若该节点不为空,则先对其左孩子节点进行中序线索化。
    • 判断:如果该节点没有左孩子的话,就调整左孩子指针状态,并让左孩子指针指向该节点的前驱节点pre;如果前驱节点没有右孩子的话,就调整右孩子指针状态,并让右孩子指针指向当先节点(pre节点的后继节点,也就是当前节点)。
    • 再对其右孩子节点进行中序线索化

    我们上面也给出了中序线索化之后的二叉树关系图片,可以去验证一下


    3.遍历线索二叉树

    在线索化了二叉树之后,我们的二叉树实际上变成了一个双向链表的结构,那么我们也就不需要再使用之前的三种遍历方法去遍历二叉树了。

    我们在二叉树的线索化之前先先指定一个头节点,让该头节点的左孩子指针指向二叉树的根节点,并且作为第一个访问到的叶子节点的前驱。同时,让该头节点的右孩子指针指向遍历到的最后一个节点,并且最后一个节点的右孩子指针指向该头节点(作为最后一个节点的后继)。以下是我们的实现方式:

    /**
        指定头指针,连接二叉树,并将其线索化后,尾部连接到头指针 
    */
    BiThrTree InOrderThreading(BiThrTree pHead,BiThrTree T)
    {
        pHead = (BiThrTree)malloc(sizeof(BiThrNode));//为头节点申请空间
    
        pHead->LTag = Link; //头节点左孩子指针状态:分支线
        pHead->RTag = Thread;//头节点右孩子指针状态:线索
        pHead->rchild = pHead;//头节点的右孩子指针先指向自己
        if(!T)
        {
            pHead->lchild = pHead;
        }
        else
        {
            pHead->lchild = T;//将头节点的左孩子指针指向树的根节点
    
            pre = pHead;//第一个前驱为头节点
            InThreading(T);//进行中序线索化
    
            pre->RTag = Thread;//此时pre为中序遍历到的最后一个节点
            pre->rchild = pHead;//将最后一个节点的右孩子指针指向头节点
            pHead->rchild = pre;//头节点的右孩子指针指向最后一个节点
        }
        return pHead;
    }

    实际线索化之后的二叉树:

    image.png

    接下来是线索二叉树的遍历,我们有这样的遍历规则:

    • 1.从树根节点开始,声明一个临时的节点指针
    • 2.令该节点指针指向树根,一直向左孩子指针传递,直到左孩子指针为线索,输出该节点的数据
    • 3.判断该节点的右孩子指针是否是线索且不是头节点。如果符合该调节,则继续传递并输出,直到某节点的右孩子指针是不存放线索或右孩子不是头节点
    • 4.传递该临时节点指针指向该节点的右孩子节点,重复2,3过程,直到临时节点指针指向头节点,表明遍历完成

    下面是线索二叉树的遍历代码:

    /**
        线索二叉树的遍历 
    */
    void InOrderTraverse(BiThrTree pHead) //传参为头节点指针
    {
        BiThrTree T = pHead->lchild;
        while(T != pHead)
        {
            while(T->LTag == Link)
                T = T->lchild;
            printf("%d  ",T->data);
            while(T->RTag == Thread && T->rchild != pHead)
            {
                T = T->rchild;
                printf("%d  ",T->data);
            }
            T = T->rchild;
        }
    }

    4.完整代码以及运行结果检验

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef enum {Link,Thread} PointerTag;
    
    typedef struct BiThrNode
    {
        int data;
        BiThrNode *lchild,*rchild;
        PointerTag LTag;
        PointerTag RTag;
    } BiThrNode,*BiThrTree;
    
    BiThrTree pre;
    
    /**
        二叉树中序遍历线索化 
    */
    void InThreading(BiThrTree T)
    {
        if(T)
        {
            InThreading(T->lchild);
            if(!T->lchild)
            {
                T->LTag = Thread;
                T->lchild = pre;
            }
            if(pre != NULL && !pre->rchild)
            {
                pre->RTag = Thread;
                pre->rchild = T;
            }
            pre = T;
            InThreading(T->rchild);
        }
    }
    
    /**
        二叉树的创建 
    */
    BiThrTree CreateBiTree(BiThrTree T,int step)
    {
        printf("请输入%d层的数据:",++step);
        int data;
        scanf("%d",&data);
        if(data == -1)
        {
            T = NULL;
        }
        else
        {
            T = (BiThrTree)malloc(sizeof(BiThrNode));
            T->data = data;
            T->LTag = Link;
            T->RTag = Link;
            T->lchild = CreateBiTree(T->lchild,step);
            T->rchild = CreateBiTree(T->rchild,step);
        }
        return T;
    }
    
    /**
        指定头指针,连接二叉树,并将其线索化后,尾部连接到头指针 
    */
    BiThrTree InOrderThreading(BiThrTree pHead,BiThrTree T)
    {
        pHead = (BiThrTree)malloc(sizeof(BiThrNode));
    
        pHead->LTag = Link;
        pHead->RTag = Thread;
        pHead->rchild = pHead;
        if(!T)
        {
            pHead->lchild = pHead;
        }
        else
        {
            pHead->lchild = T;
    
            pre = pHead;
            InThreading(T);
    
            pre->RTag = Thread;
            pre->rchild = pHead;
            pHead->rchild = pre;
        }
        return pHead;
    }
    
    /**
        线索二叉树的遍历 
    */
    void InOrderTraverse(BiThrTree pHead)
    {
        BiThrTree T = pHead->lchild;
        while(T != pHead)
        {
            while(T->LTag == Link)
                T = T->lchild;
            printf("%d  ",T->data);
            while(T->RTag == Thread && T->rchild != pHead)
            {
                T = T->rchild;
                printf("%d  ",T->data);
            }
            T = T->rchild;
        }
    }
    
    int main()
    {
        BiThrTree T;
        T = CreateBiTree(T,0);
        BiThrTree pHead;
        pHead = InOrderThreading(pHead,T);
        InOrderTraverse(pHead);
        return 0;
    }
    • 注意:这里的代码中二叉树中存放的是整型数据,所以A,B,C,D,E,F,G,H,I,J 我这里用1,2,3,4,5,6,7,8,9,10来代替,其实运行结果是一样的

    image.png

    8,4,9,2,10,5,1,6,3,7
    就等同于:H,D,I,B,J,E,A,F,C,G

    展开全文
  • 线索二叉树 思考:在有n个节点的二叉链表中必定有n+1个空链域(下面会说为什么),遍历运算是最重要也是最常用的运算,之前的无论递归与非递归算法实现遍历效率都不算高。能不能利用这未使用的n+1空指针域,设计出...

    线索二叉树

    •  思考:在有n个节点的二叉链表中必定有n+1个空链域(下面会说为什么),遍历运算是最重要也是最常用的运算,之前的无论递归与非递归算法实现遍历效率都不算高。能不能利用这未使用的n+1空指针域,设计出提高遍历效率的存储结构? 

                                                           

    观察该树可以发现节点(除了根节点)都有一个直接前驱,那么就会知道  如果节点数量为n 树枝数量为b,那么b=n-1;

    链表每个节点都是有两个指针域的所以n个节点有2n个,那么用掉n-1个就剩下上面说的n+1个空的了

     

    那对于上面的思考:引入正题

    线索二叉树就是利用那未使用的空指针域来优化,提高遍历效率的存储结构;

    1. 实现:在二叉链表的节点中增加两个标志域

    当ltag或rtag为0时说明其有左/右孩子,该指针已经被占用,只有当ltag或rtag为1时才能使用

    •   ltag:若ltag = 0,left域指向左孩子 ;  若ltag = 1,left区域指向其遍历序列的前驱;
    •   rtag:若rtag = 0,left域指向右孩子 ;  若rtag = 1,right区域指向其遍历序列的后继;
      leftltagdatartagright
      我们只能使用未使用的指针,例如D的左指针和右指针,所以我们是用空指针域来指向其前驱和后继

     

    以中序线索二叉树为例(可以为前中后):

                若中序序列为:D B G E A F H C K

     

     

    解释: 

    其中虚线为线索指针,实线为指向真实子女

    • 因为A的ltag和rtag标志位都为0,所以A有左右子节点,left和right指向它的真实子女;
    • B节点和A节点类似;
    • D节点的两个标志位都为1,所以其left和right要指向它的前驱和后继,但是D在中序序列中是第一个,没有前驱所以left为NULL,right指向B;
    • E节点的ltag=0,所以指向子节点;rtag=1,所以指向后继
    • 以此类推

     如果我们已经构造二叉链表了,我们该怎样把它转化成线索二叉树呢?

    • 我们来看一下线索二叉树的思想:

                

    下面我们来实现一下线索二叉树

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

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

    • 中序遍历线索化的递归函数代码如下:
    BiTree pre;                 //全局变量,始终指向刚刚访问过的结点
    //中序遍历进行中序线索化
    void InThreading(BiTree 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;
                    //===
            InThreading(p->rchild);      //递归右子树线索化
        }
    }

     

    • 因为此时p结点的后继还没有访问到,因此只能对它的前驱结点pre的右指针rchild做判断,if(!pre->rchild)表示如果为空,则p就是pre的后继,于是pre->rchild = p,并且设置pre->rtag = Thread,完成后继结点的线索化
    •     if(!p->lchild)表示如果某结点的左指针域为空,因为其前驱结点刚刚访问过,赋值了pre,所以可以将pre赋值给p->lchild,并修改p->ltag = Thread(也就是定义为1)以完成前驱结点的线索化。
    •    完成前驱和后继的判断后,不要忘记当前结点p赋值给pre,以便于下一次使用

          有了线索二叉树后,对它进行遍历时,其实就等于操作一个双向链表结构。

    • 和双向链表结点一样,在二叉树链表上添加一个头结点,如下图所示,并令其lchild域的指针指向二叉树的根结点(图中第一步),其rchild域的指针指向中序遍历访问时的最后一个结点(图中第二步)。反之,令二叉树的中序序列中第一个结点中,lchild域指针和最后一个结点的rchild域指针均指向头结点(图中第三和第四步)。这样的好处是:我们既可以从第一个结点起顺后继进行遍历,也可以从最后一个结点起顺前驱进行遍历。

    遍历代码如下:

    //t指向头结点,头结点左链lchild指向根结点,头结点右链rchild指向中序遍历的最后一个结点。
    //中序遍历二叉线索树表示二叉树t
    int InOrderThraverse_Thr(BiTree t)
    {
        BiTree 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. 代码中,p = t->lchild;意思就是上图中的第一步,让p指向根结点开始遍历;
    2. while(p != t)其实意思就是循环直到图中的第四步出现,此时意味着p指向了头结点,于是与t相等(t是指向头结点的指针),结束循环,否则一直循环下去进行遍历操作;
    3.  while(p-ltag == Link)这个循环,就是由A->B->D->G,此时H结点的ltag不是link(就是不等于0),所以结束此循环;
    4.  然后就是打印H;
    5.  while(p->rtag == Thread && p->rchild != t),由于结点B的rtag = Thread(就是等于1),且不是指向头结点。因此打印D的后继B,之后因为B的rtag是Link,因此退出循环;B
    6. p=p->rchild;意味着p指向了结点B的右孩子了;
    7. 就这样不断的循环遍历,直到打印出D B G E A F H C K,结束遍历操作。


        从这段代码可以看出,它等于是一个链表的扫描,所以时间复杂度为O(n)。
        由于充分利用了空指针域的空间(等于节省了空间),又保证了创建时的一次遍历就可以终生受用后继的信息(意味着节省了时间)。所以在实际问题中,如果所用的二叉树需要经过遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表的存储结构就是非常不错的选择。

    哈夫曼树:https://blog.csdn.net/alzzw/article/details/97809047

    二叉搜索(排序)树;https://blog.csdn.net/alzzw/article/details/97563011

    平衡二叉树:https://blog.csdn.net/alzzw/article/details/97613193

    B树~B+树:https://blog.csdn.net/alzzw/article/details/97633941

    红黑树:https://blog.csdn.net/alzzw/article/details/97770753

    到这里线索二叉树就讲解完了,如果喜欢请收藏,谢谢您的支持

    展开全文
  • 主要介绍了C语言数据结构线索二叉树及其遍历的相关资料,为了加快查找节点的前驱和后继。对二叉树的线索化就是对二叉树进行一次遍历,在遍历的过程中检测节点的左右指针是否为空,如果是空,则将他们改为指向前驱和...
  • 数据结构线索二叉树严蔚敏 树方面的知识很难 但只要把递归方面的机制搞懂即可
  • 数据结构-线索链表

    千次阅读 2018-10-09 15:22:32
    若经常遍历或者要求取遍历时结点的前驱、后继信息则应修改二叉链表的结构以保存该遍历顺序链表,加上线索的二叉树称为线索二叉树。分先序、中序、后序线索二叉树。 这里介绍的是中序线索二叉树. 首先是辅助宏的...
  • 线索二叉树的概念 线索化 若无左子树,则将左...这种结点结构构成的二叉链表作为二叉树的存储结构,称为线索链表 前驱结点 若左指针为线索,则其指向结点为前驱结点 若左指针为左孩子,则其左子树的最右侧结点为前
  • 数据结构-线索二叉树的画法: 所有空指针域均被利用。 先写出二叉树相应的前/中/后序遍历序列。 二叉树中每个结点的空左孩子指向前驱,空右孩子指向后继;若无前驱/后继则引出为NIL。
  • 数据结构-线索二叉树(中序线索二叉树及遍历)

    万次阅读 多人点赞 2018-07-15 11:42:02
    1.二叉树线索化 二叉树的遍历是按照一定的规则把二叉树中的节点按照一定的次序排列成线性序列进行访问的,实质上就是对一个非线性结构进行线索化操作,使得每个节点(除第一个和最后一个外)都有前驱和后继节点,...
  • 添加、删除、拷贝、清空、树深度计算、父节点、兄弟节点获取、先中后序递归及非遍历、按层次遍历、中序迭代器(非递归算法)、节点查找、先序和中序序列重建二叉树、数组和二叉链表存储结构相互转换。使用模板偏特化...
  • 数据结构线索二叉树的基本概念和构造1.基本概念2.中序线索二叉树的构造2.1二叉树中序线索化分析 1.基本概念 二叉树的非递归遍历算法避免了系统栈的调用,提高了一定的效率,而线索二叉树可以把用户栈也省掉,把...
  • 该程序是在C语言数据结构课上的一个实验,实现一个线索二叉树
  • 数据结构线索二叉树的基本操作

    千次阅读 2018-02-12 08:51:12
    带头结点的线索二叉树(如图),头结点的lchild指针指向二叉树的根结点(A),rchild指针指向中序遍历时访问的最后一个结点(G)。源码:#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define...
  • [数据结构]——线索二叉树

    千次阅读 2020-12-16 01:17:04
    这篇文章介绍了在数据结构中,如何作出线索二叉树。
  • 数据结构中,树是一种很重要的结构类型。而其中线索二叉树又是一种比较难掌握的结构。提供一下代码,谢谢大家顶一下哦
  • 二叉链表作为存储结构时只能找到结点的左、右孩子的信息,而不能...只有中序遍历才可以对其进行线索化!! 把树的结构遍历的时候看一下哪些地方有空余,会发现中序刚好每个结点间都有 结点类 public class BiNode<T
  • 学习了严蔚敏的《数据结构》为了加深映像,把上面的代码自己敲了一遍。在VC6.0里,编译 和链接都通过了,但是没有办法运行,恳求各位高手和大师告诉我,哪里出问题了,我实在 是找不出来啊!!! #include "stdafx.h...
  • InThreading()、InOrderThreading()、InOrderTraverse_Thr()等几个函数来自于严蔚敏老师的数据结构教材,本人编写了main()函数,在VC++6.0和DEV-C++下编译通过。 #include "stdio.h" #include "malloc.h" typedef ...
  • 线索树(数据结构

    千次阅读 2017-06-23 19:28:15
    线索树(Threaded Tree) 个人理解: 对于一棵二叉树中,它的一些节点的左右孩子不一定都在,这样的话,我们基于原先的节点结构template class Node{ Type data; Node* leftChild; Node* rightChild; }(1)...
  • 线索二叉树可以这样理解:  1. PreCreate(): 对于线索二叉树的先序创建过程和一般二叉树的先序创建没有区别(都是建立结点,然后结点赋值)  2.InThread():中序线索化的过程就是在1.中创建的基础上贴上标签(即...
  • 目的:设计并实现基于后序线索二叉树的后序遍历的非递归算法。 要求: (1)创建二叉树。 (2)转换为后序线索二叉树。 (3)实现后序遍历的非递归算法。 (4)其它要求同课后作业-01要求。 二、实验环境 软件环境:...
  • 1.前序线索二叉树的遍历 2.中序线索二叉树的遍历 3.后序线索二叉树的遍历 代码 #define CHAR 1 /* 字符型 */ #if CHAR typedef char TElemType; TElemType Nil=' '; /* 字符型以空格符为空 */ #else typedef ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,853
精华内容 14,341
关键字:

数据结构线索

数据结构 订阅