精华内容
下载资源
问答
  • 数据结构 线索二叉树

    2019-11-06 19:09:27
    数据结构 线索二叉树

    一、线索二叉树的原理

        通过考察各种二叉链表,不管儿叉树的形态如何,空链域的个数总是多过非空链域的个数。准确的说,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)因此对于上图的二叉链表图可以修改为下图的养子。



    二、线索二叉树结构实现

        二叉线索树存储结构定义如下:

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

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

        中序遍历线索化的递归函数代码如下:

    1. BiTree pre; //全局变量,始终指向刚刚访问过的结点
    2. //中序遍历进行中序线索化
    3. void InThreading(BiTree p)
    4. {
    5. if(p)
    6. {
    7. InThreading(p->lchild); //递归左子树线索化
    8. //===
    9. if(!p->lchild) //没有左孩子
    10. {
    11. p->ltag = Thread; //前驱线索
    12. p->lchild = pre; //左孩子指针指向前驱
    13. }
    14. if(!pre->rchild) //没有右孩子
    15. {
    16. pre->rtag = Thread; //后继线索
    17. pre->rchild = p; //前驱右孩子指针指向后继(当前结点p)
    18. }
    19. pre = p;
    20. //===
    21. InThreading(p->rchild); //递归右子树线索化
    22. }
    23. }

    上述代码除了//===之间的代码以外,和二叉树中序遍历的递归代码机会完全一样。只不过将打印结点的功能改成了线索化的功能。


        中间部分代码做了这样的事情:

    因为此时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域指针均指向头结点(图中第三和第四步)。这样的好处是:我们既可以从第一个结点起顺后继进行遍历,也可以从最后一个结点起顺前驱进行遍历。



        遍历代码如下所示。

    1. //t指向头结点,头结点左链lchild指向根结点,头结点右链rchild指向中序遍历的最后一个结点。
    2. //中序遍历二叉线索树表示二叉树t
    3. int InOrderThraverse_Thr(BiTree t)
    4. {
    5. BiTree p;
    6. p = t->lchild; //p指向根结点
    7. while(p != t) //空树或遍历结束时p == t
    8. {
    9. while(p->ltag == Link) //当ltag = 0时循环到中序序列的第一个结点
    10. {
    11. p = p->lchild;
    12. }
    13. printf("%c ", p->data); //显示结点数据,可以更改为其他对结点的操作
    14. while(p->rtag == Thread && p->rchild != t)
    15. {
    16. p = p->rchild;
    17. printf("%c ", p->data);
    18. }
    19. p = p->rchild; //p进入其右子树
    20. }
    21. return OK;
    22. }
    说明:


        (1)代码中,p = t->lchild;意思就是上图中的第一步,让p指向根结点开始遍历;
        (2)while(p != t)其实意思就是循环直到图中的第四步出现,此时意味着p指向了头结点,于是与t相等(t是指向头结点的指针),结束循环,否则一直循环下去进行遍历操作;
        (3)while(p-ltag == Link)这个循环,就是由A->B->D->H,此时H结点的ltag不是link(就是不等于0),所以结束此循环;
        (4)然后就是打印H;
        (5)while(p->rtag == Thread && p->rchild != t),由于结点H的rtag = Thread(就是等于1),且不是指向头结点。因此打印H的后继D,之后因为D的rtag是Link,因此退出循环;
        (6)p=p->rchild;意味着p指向了结点D的右孩子I;
        (7).....,就这样不断的循环遍历,直到打印出HDIBJEAFCG,结束遍历操作。


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

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #define ERROR 0
    4. #define OK 1
    5. typedef enum{Link, Thread} PointerTag; //link = 0表示指向左右孩子指针
    6. //Thread = 1表示指向前驱或后继的线索
    7. typedef struct BitNode
    8. {
    9. char data; //结点数据
    10. struct BitNode *lchild; //左右孩子指针
    11. struct BitNode *rchild;
    12. PointerTag ltag; //左右标志
    13. PointerTag rtag;
    14. }BitNode, *BiTree;
    15. BiTree pre; //全局变量,始终指向刚刚访问过的结点
    16. //前序创建二叉树
    17. void CreateTree(BiTree *t)
    18. {
    19. char ch;
    20. scanf("%c", &ch);
    21. if(ch == '#')
    22. {
    23. *t = NULL;
    24. }
    25. else
    26. {
    27. (*t) = (BiTree)malloc(sizeof(BitNode));
    28. if((*t) == NULL)
    29. {
    30. return;
    31. }
    32. (*t)->data = ch;
    33. CreateTree(&((*t)->lchild));
    34. CreateTree(&((*t)->rchild));
    35. }
    36. }
    37. //t指向头结点,头结点左链lchild指向根结点,头结点右链rchild指向中序遍历的最后一个结点。
    38. //中序遍历二叉线索树表示的二叉树t
    39. int InOrderThraverse_Thr(BiTree t)
    40. {
    41. BiTree p;
    42. p = t->lchild; //p指向根结点
    43. while(p != t)
    44. {
    45. while(p->ltag == Link) //当ltag = 0时循环到中序序列的第一个结点
    46. {
    47. p = p->lchild;
    48. }
    49. printf("%c ", p->data); //显示结点数据,可以更改为其他对结点的操作
    50. while(p->rtag == Thread && p->rchild != t)
    51. {
    52. p = p->rchild;
    53. printf("%c ", p->data);
    54. }
    55. p = p->rchild; //p进入其右子树
    56. }
    57. return OK;
    58. }
    59. //中序遍历进行中序线索化
    60. void InThreading(BiTree p)
    61. {
    62. if(p)
    63. {
    64. InThreading(p->lchild); //递归左子树线索化
    65. if(!p->lchild) //没有左孩子
    66. {
    67. p->ltag = Thread; //前驱线索
    68. p->lchild = pre; //左孩子指针指向前驱,这里是第3步
    69. }
    70. if(!pre->rchild) //没有右孩子
    71. {
    72. pre->rtag = Thread; //后继线索
    73. pre->rchild = p; //前驱右孩子指针指向后继(当前结点p)
    74. }
    75. pre = p;
    76. InThreading(p->rchild); //递归右子树线索化
    77. }
    78. }
    79. //建立头结点,中序线索二叉树
    80. int InOrderThread_Head(BiTree *h, BiTree t)
    81. {
    82. (*h) = (BiTree)malloc(sizeof(BitNode));
    83. if((*h) == NULL)
    84. {
    85. return ERROR;
    86. }
    87. (*h)->rchild = *h;
    88. (*h)->rtag = Link;
    89. if(!t) //如果为NULL
    90. {
    91. (*h)->lchild = *h;
    92. (*h)->ltag = Link;
    93. }
    94. else
    95. {
    96. pre = *h;
    97. (*h)->lchild = t; //第一步
    98. (*h)->ltag = Link;
    99. InThreading(t); //找到最后一个结点
    100. pre->rchild = *h; //第四步
    101. pre->rtag = Thread;
    102. (*h)->rchild = pre; //第二步
    103. }
    104. }
    105. int main(int argc, char **argv)
    106. {
    107. BiTree t;
    108. BiTree temp;
    109. printf("请输入前序二叉树的内容:\n");
    110. CreateTree(&t); //建立二叉树
    111. InOrderThread_Head(&temp, t); //加入头结点,并线索化
    112. printf("输出中序二叉树的内容:\n");
    113. InOrderThraverse_Thr(temp);
    114. printf("\n");
    115. return 0;
    116. }


    展开全文
  • 何谓线索二叉树 遍历结果是求得结点的一个线性序列指向该线性序列前驱和后继的指针称线索包含线索的存储结构称为线索链表与其相应的二叉树称为线索二叉树对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化2...
  • 线索二叉树 #include <stdio.h> #include <stdlib.h> typedef char ElemType; //线索存储标志位 //Link(0):表示指向左右孩子的指针 //Thread(1):表示指向前驱后继的线索 typedef enum {Link,...

    拓展四(1)


    线索二叉树

    #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, rtag;
    }BiThrNode, *BiThrTree;
    
    //全局变量 始终指向上一访问的结点
    BiThrTree pre;
    
    //创建一棵二叉树,约定用户遵照前序遍历的方式输入数据
    void CreateBiThrTree(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;
    
            CreateBiThrTree(&(*T)->lchild);
            CreateBiThrTree(&(*T)->rchild);
        }
    }
    
    //中序遍历线索化
    void InThreading(BiThrTree T)
    {
        if(T)
        {
            InThreading(T->lchild); //递归左孩子线索化
    
            if(!T->lchild) //如果该结点没有左孩子 则ltag赋值Thread lchild指向上一访问的结点
            {
                T->ltag = Thread;
                T->lchild = pre;
            }
    
            if(!pre->rchild)
            {
                pre->rtag = Thread;
                pre->rchild = T;
            }
    
            pre = T;
    
            InThreading(T->rchild); //递归右孩子线索化
        }
    }
    
    void InOrderThreading(BiThrTree *p, BiThrTree T)
    {
        *p = (BiThrNode *)malloc(sizeof(BiThrNode));
        if(!T)
        {
            (*p)->lchild = *p;
            (*p)->ltag = Thread;
    
            (*p)->rchild = *p;
            (*p)->rtag = Thread;
        }
        else
        {
            (*p)->lchild = T;
            (*p)->ltag = Link;
    
            pre = *p;
    
            InThreading(T);
    
            pre->rchild = (*p);
            pre->rtag = Thread;
    
            (*p)->rchild = pre;
            (*p)->rtag = Thread;
        }
    }
    
    void visit(char c)
    {
        printf("%c", c);
    }
    
    //迭代 非递归 中序遍历二叉树
    void InOrderTraverse(BiThrTree T)
    {
        BiThrTree p;
        p = T->lchild;
    
        while(T != p)
        {
            while(Link == p->ltag)
            {
                p = p->lchild;
            }
    
            visit(p->data);
    
            while(Thread == p->rtag && T != p->rchild)
            {
                p = p->rchild;
                visit(p->data);
            }
    
            p = p->rchild;
        }
    }
    
    int main()
    {
        BiThrTree P, T=NULL;
    
        CreateBiThrTree(&T);
    
        InOrderThreading(&P, T);
    
        printf("迭代中序遍历输出结果为:");
    
        InOrderTraverse(P);
    
        return 0;
    }
    
    // e.g. : ABC  D  E F  \n
    
    

    【额外】

    展开全文
  • 以二叉链表来作为储存结构的时候,只能找到左右孩子的信息,不能直接得到结点的前驱和后继信息,这种信息只有在遍历的过程中才能实现。在n个结点的二叉链表中必定存在n+1个空链域。可以用这些空链域来保存这些信息;...

    以二叉链表来作为储存结构的时候,只能找到左右孩子的信息,不能直接得到结点的前驱和后继信息,这种信息只有在遍历的过程中才能实现。在n个结点的二叉链表中必定存在n+1个空链域。可以用这些空链域来保存这些信息;做以下规定:若结点有左子树,则lchild指向其左孩子,若没有左孩子则指向其前驱;若结点有右子树,则rchild指向其右子树,否则指向其后继;为了标志指针是线索还是指针,需要添加两个标志位来表示指针的性质

    lchild LTag rchild RTag

     

    LTag,RTag是枚举类对象, 值为0的时候表示指针, 值为1表示线索

     1 typedef enum PointerTag{Link, Thread}; 

     

    当我们能知道结点的前驱和后继信息的时候,只要找到序列中的第一个结点,然后依次查找后继结点,直到后继为空时而止;

    怎么在二叉树中求结点的后继信息?

    对于右孩子为空的结点来说,其右孩子指针指向其后继。但是当结点的右孩子不为空的时候,怎么找到其后继信息?根据后序遍历的规定可以直到,结点的后继结点应该是遍历其右子树最左下角的结点。当结点的左孩子为空的时候,左孩子指针指向其前驱, 当左孩子不为空的时候, 结点的前驱是遍历左子树的最后一个结点,也就是左子树最右下角的结点;(这些都是针对中序遍历而言)

    对线索树的结点做一下定义, 为了简便,结点类型用int类型

    1 typedef struct BiThrNode{
    2     int val;
    3     struct BiThrNode *lchild, *rchild;
    4     PointerTag LTag, RTag;
    5 }BiThrNode, *BiThrTree;

     

    对二叉树进行线索化:pre是上一个访问的结点,pre的初始值指向表头结点(即后面的Thrt,其左孩子指向根节点); 线索化的过程是一个从叶子结点到根节点的过程,从左子树到右子树的过程;根据上面的分析可以知道,当一个结点的孩子为null的时候,就指向前驱或者后继。 调用这个函数后除最后一个结点,结点的指针都指向孩子结点或者前驱后继。

     1 void InThreading(BiThrTree p, BiThrTree& pre){
     2     if(p){
     3         InThreading(p->lchild, pre);    //左子树线索化
     4         if(!p->lchild){                    //p左孩子为null,则指向pre,指向p的前驱
     5             p->LTag = Thread;
     6             p->lchild = pre;
     7         }else p->LTag = Link;
     8         if(!pre->rchild){                //pre右孩子为null,则指向p,表示p是pre的后驱
     9             pre->RTag = Thread;
    10             pre->rchild = p;
    11         }else pre->RTag = Link;
    12         pre = p;                        //更新p的位置
    13         InThreading(p->rchild, pre);    //右子树线索化
    14     }
    15 }

     

    建立一个循环到线索树:Thrt是一个头结点,左孩子指向根节点, 右孩子指向树的最后一个结点。又让树的最后一个结点右孩子指向Thrt。这样就构成一个循环的线索树。当对树进行中序遍历的时候,若某一个结点的右孩子指向Thrt,则表示遍历完成

     1 void InOrderThreading(BiThrTree& Thrt, BiThrTree& T){
     2     Thrt = (BiThrNode*) malloc(sizeof(BiThrNode));
     3     Thrt->LTag = Link; Thrt->RTag = Thread;
     4     Thrt->rchild = Thrt;
     5     BiThrTree pre;
     6     if(!T) Thrt->lchild = Thrt;
     7     else{
     8         Thrt->lchild = T;
     9         pre = Thrt;
    10         InThreading(T, pre);                    //中序遍历线索化
    11         pre->rchild = Thrt; pre->RTag = Thread; //最后一个结点线索化
    12         Thrt->rchild = pre;
    13     }
    14 }

     

    根据线索树进行中序遍历:由上面的分析可以写出下面的中序遍历程序,先找到要遍历的第一个结点,在中序遍历中,即数的最左下角的结点。找到第一个结点后就根据当前节点的后继结点来进行遍历;当结点的右孩子指针不指向后继节点的时候,这继续访问当前结点的右子树(由中序遍历先遍历左子树可以知道, 当访问的结点有右孩子的时候,其右孩子一定已经访问完成),重复上面的过程就遍历所有的结点

     1 void InOrderTraverse(BiThrTree Thrt){
     2     BiThrNode *p = Thrt->lchild;    //让p指向树的根节点
     3     while(p!=Thrt){
     4         while(p->LTag==Link) p = p->lchild;    //指向树的最左下方
     5         cout<<p->val<<" ";
     6         while(p->RTag==Thread && p->rchild!=Thrt){  //根据后继结点进行遍历
     7             p = p->rchild;
     8             cout<<p->val<<" ";
     9         } //接待右孩子不为空的时候,退出循环,继续访问当前结点的右子树
    10         p = p->rchild;  //
    11     }
    12     cout<<endl;
    13 }

    在将二叉树线索化之前,需要建立一个二叉树,这里通过递归的方式来建立一棵树

     1 BiThrTree CreateBiTree(BiThrTree T, int val){
     2     if(!T){
     3         T = (BiThrNode*) malloc(sizeof(BiThrNode));
     4         T->val = val;
     5         T->lchild = T->rchild = NULL;
     6         return T;
     7     }
     8     if(val<T->val) T->lchild = CreateBiTree(T->lchild, val);
     9     if(val>T->val) T->rchild = CreateBiTree(T->rchild, val);
    10     return T;
    11 }

     

    完整代码

    把数的结点信息按照,层序遍历的顺序储存在数组t之中,建立通过CreateBiTree()建立二叉树, 再通过inorder()来验证二叉树建立是否正确,这里给出的例子,如果建立二叉树正确,二叉遍历的结果应该是一个从1到7的升序数列; 然后验证上面的线索二叉树的构造过程是否正确,先通过InorderThreading来将二叉树线索化, 然后再通过InorderTrverse()来验证;

     1 #include<iostream>
     2 using namespace std;
     3 /*
     4     author: Lai XingYu
     5       date: 2018/5/18
     6   describe: threaded binary tree
     7 */
     8 
     9 typedef enum PointerTag{Link, Thread}; //标志指针类型,前者表示指针, 后者表示线索
    10 typedef struct BiThrNode{
    11     int val;
    12     struct BiThrNode *lchild, *rchild;
    13     PointerTag LTag, RTag;
    14 }BiThrNode, *BiThrTree;
    15 
    16 /*
    17     对二叉树线索化, pre表示上一个访问的结点
    18 */
    19 void InThreading(BiThrTree p, BiThrTree& pre){
    20     if(p){
    21         InThreading(p->lchild, pre);    //左子树线索化
    22         if(!p->lchild){                    //p左孩子为null,则指向pre,指向p的前驱
    23             p->LTag = Thread;
    24             p->lchild = pre;
    25         }else p->LTag = Link;
    26         if(!pre->rchild){                //pre右孩子为null,则指向p,表示p是pre的后驱
    27             pre->RTag = Thread;
    28             pre->rchild = p;
    29         }else pre->RTag = Link;
    30         pre = p;                        //更新p的位置
    31         InThreading(p->rchild, pre);    //右子树线索化
    32     }
    33 }
    34 
    35 /*
    36     Thr是头结点, 其左孩子指向根节点, 右孩子指向树的最后一个结点
    37     树的最后一个结点的右孩子指向THr,构成一个回环
    38 */
    39 void InOrderThreading(BiThrTree& Thrt, BiThrTree& T){
    40     Thrt = (BiThrNode*) malloc(sizeof(BiThrNode));
    41     Thrt->LTag = Link; Thrt->RTag = Thread;
    42     Thrt->rchild = Thrt;
    43     BiThrTree pre;
    44     if(!T) Thrt->lchild = Thrt;
    45     else{
    46         Thrt->lchild = T;
    47         pre = Thrt;
    48         InThreading(T, pre);                    //中序遍历线索化
    49         pre->rchild = Thrt; pre->RTag = Thread; //最后一个结点线索化
    50         Thrt->rchild = pre;
    51     }
    52 }
    53 
    54 void InOrderTraverse(BiThrTree Thrt){
    55     BiThrNode *p = Thrt->lchild;    //让p指向树的根节点
    56     while(p!=Thrt){
    57         while(p->LTag==Link) p = p->lchild;    //指向树的最左下方
    58         cout<<p->val<<" ";
    59         while(p->RTag==Thread && p->rchild!=Thrt){
    60             p = p->rchild;
    61             cout<<p->val<<" ";
    62         }
    63         p = p->rchild;
    64     }
    65     cout<<endl;
    66 }
    67 
    68 BiThrTree CreateBiTree(BiThrTree T, int val){
    69     if(!T){
    70         T = (BiThrNode*) malloc(sizeof(BiThrNode));
    71         T->val = val;
    72         T->lchild = T->rchild = NULL;
    73         return T;
    74     }
    75     if(val<T->val) T->lchild = CreateBiTree(T->lchild, val);
    76     if(val>T->val) T->rchild = CreateBiTree(T->rchild, val);
    77     return T;
    78 }
    79 
    80 void inorder(BiThrTree T){
    81     if(!T) return;
    82     if(T->lchild) inorder(T->lchild);
    83     cout<<T->val<<" ";
    84     if(T->rchild) inorder(T->rchild);
    85 }
    86 
    87 int main(){
    88     int t[] = {4,2,5,1,3,6,7}, i;
    89     BiThrTree T = NULL, Thrt;
    90     for(i=0; i<7; i++) T = CreateBiTree(T, t[i]);
    91     inorder(T);
    92     cout<<endl;
    93     InOrderThreading(Thrt, T);
    94     InOrderTraverse(Thrt);
    95 return 0;}

     

     在准备408考试的时候接触到这个线索二叉树,理解还是有些吃力;不能理解的是,这样的储存结构的意义在哪里?就算保存了前驱后继信息,也到先找到该节点, 此外,根据实现的过程来看, 当二叉树建立之后, 若要插入新的节点又要重新对二叉树进行线索化, 这个开销也是不小的

     

    后序线索树的构造

    后序线索树的构造比,中序线索树更为复杂,可以分为以下四种情况

    1. 如果节点为根节点,则后继结点为空
    2. 结点是双亲的右孩子,或者是左孩子且没有兄弟结点, 则后继结点是双亲结点
    3. 结点为双清结点的左孩子,且有兄弟结点,则后继结点双亲右子树按照后序遍历的第一个结点。
    4. 结点为双亲的右孩子,后继为双亲结点

     

    转载于:https://www.cnblogs.com/mr-stn/p/9058000.html

    展开全文
  • 为什么线索化二叉树?对于二叉树的遍历,我们知道每个节点的前驱与后继,但是这是建立在遍历的基础上,否则我们只知道后续的左右子树。现在我们充分利用二叉树左右子树的空节点,分别指向当前节点的前驱、后继,便于...

    029bb14355049c58fdc9caa94e9b1479.png

    为什么线索化二叉树?

    对于二叉树的遍历,我们知道每个节点的前驱与后继,但是这是建立在遍历的基础上,否则我们只知道后续的左右子树。现在我们充分利用二叉树左右子树的空节点,分别指向当前节点的前驱、后继,便于快速查找树的前驱后继。

    不多说,直接上代码:

    /// /// 线索二叉树 节点/// /// public class ClueTreeNode<T>{    ///     /// 内容    ///     public T data { get; set; }    ///     /// 左树    ///     public ClueTreeNode leftNode { get; set; }    ///     /// 右树    ///     public ClueTreeNode rightNode { get; set; }    ///     /// 0 标识左树 1 标识 当前节点的前驱    ///     public int leftTag { get; set; }    ///     /// 0标识右树 1 标识 当前节点的后继    ///     public int rightTag { get; set; }    public ClueTreeNode()    {        data = default(T);        leftNode = null;        rightNode = null;    }    public ClueTreeNode(T item)    {        data = item;        leftNode = null;        rightNode = null;    }}
    /// /// 线索化 二叉树 /// /// 为什么线索化二叉树?/// 第一:对于二叉树,如果有n个节点,每个节点有指向左右孩子的两个指针域,所以一共有2n个指针域。/// 而n个节点的二叉树一共有n-1条分支线数,也就是说,其实是有 2n-(n-1) = n+1个空指针。/// 这些空间不存储任何事物,白白浪费内存的资源。/// 第二:对于二叉树的遍历,我们知道每个节点的前驱与后继,但是这是建立在遍历的基础上。/// 否则我们只知道后续的左右子树。/// 第三:对于二叉树来说,从结构上来说是单向链表,引入前驱后继后,线索化二叉树可以认为是双向链表。/// /// public class ClueBinaryTree<T>{    ///     /// 树根节    ///     private ClueTreeNode head { get; set; }    ///     /// 线索化时作为前驱转存    ///     private ClueTreeNode preNode { get; set; }    public ClueBinaryTree(){        head = new ClueTreeNode();    }    public ClueBinaryTree(T val){        head = new ClueTreeNode(val);    }    public ClueTreeNode GetRoot(){        return head;    }    ///     /// 插入左节点    ///     ///     ///     ///     public ClueTreeNode AddLeftNode(T val, ClueTreeNode node){        if (node == null)            throw new ArgumentNullException("参数错误");        ClueTreeNode treeNode = new ClueTreeNode(val);        ClueTreeNode childNode = node.leftNode;        treeNode.leftNode = childNode;        node.leftNode = treeNode;        return treeNode;    }    ///     /// 插入右节点    ///     ///     ///     ///     public ClueTreeNode AddRightNode(T val, ClueTreeNode node){        if (node == null)            throw new ArgumentNullException("参数错误");        ClueTreeNode treeNode = new ClueTreeNode(val);        ClueTreeNode childNode = node.rightNode;        treeNode.rightNode = childNode;        node.rightNode = treeNode;        return treeNode;    }    ///     /// 删除当前节点的 左节点    ///     ///     ///     public ClueTreeNode DeleteLeftNode(ClueTreeNode node){        if (node == null || node.leftNode == null)            throw new ArgumentNullException("参数错误");        ClueTreeNode leftChild = node.leftNode;        node.leftNode = null;        return leftChild;    }    ///     /// 删除当前节点的 右节点    ///     ///     ///     public ClueTreeNode DeleteRightNode(ClueTreeNode node){        if (node == null || node.rightNode == null)            throw new ArgumentNullException("参数错误");        ClueTreeNode rightChild = node.rightNode;        node.rightNode = null;        return rightChild;    }    ///     /// 中序遍历线索化二叉树    ///     public void MiddlePrefaceTraversal(){        ClueTreeNode node = head;        while (node != null)        {            //判断是否是            while (node.leftTag == 0)            {                node = node.leftNode;            }            Console.Write($" {node.data}");            while (node.rightTag == 1)            {                node = node.rightNode;                Console.Write($" {node.data}");            }            node = node.rightNode;        }    }    ///     /// 线索化二叉树    ///     ///     public void MiddleClueNodes(ClueTreeNode node){        if (node == null)        {            return;        }        //线索化左子树        MiddleClueNodes(node.leftNode);        //当左树为空时,指向前驱,标识为 1        if (node.leftNode == null)        {            node.leftNode = preNode;            node.leftTag = 1;        }        //如果 前驱的右树不为空        if (preNode != null && preNode.rightNode == null)        {            preNode.rightNode = node;            preNode.rightTag = 1;        }        preNode = node;        //线索化右子树        MiddleClueNodes(node.rightNode);    }}

    线索化二叉树的过程(中序遍历):

    4058a970f073cd33be305de78442445e.png

    2067627b59ff14b3e882797ac7511ec4.png

    现在我们测试:

    //创建树ClueBinaryTree<string> clueBinaryTree = new ClueBinaryTree<string>("A");ClueTreeNode<string> tree1 = clueBinaryTree.AddLeftNode("B", clueBinaryTree.GetRoot());ClueTreeNode<string> tree2 = clueBinaryTree.AddRightNode("C", clueBinaryTree.GetRoot());ClueTreeNode<string> tree3 = clueBinaryTree.AddLeftNode("D", tree1);clueBinaryTree.AddRightNode("E", tree1);clueBinaryTree.AddLeftNode("F", tree2);clueBinaryTree.AddRightNode("G", tree2);clueBinaryTree.MiddleClueNodes(clueBinaryTree.GetRoot());Console.Write("中序遍历");clueBinaryTree.MiddlePrefaceTraversal();

    打印结果:

    中序遍历 D B E A F C G
    展开全文
  • 为什么线索化二叉树?对于二叉树的遍历,我们知道每个节点的前驱与后继,但是这是建立在遍历的基础上,否则我们只知道后续的左右子树。现在我们充分利用二叉树左右子树的空节点,分别指向当前节点的前驱、后继,便于...
  • 学习了严蔚敏的《数据结构》为了加深映像,把上面的代码自己敲了一遍。在VC6.0里,编译 和链接都通过了,但是没有办法运行,恳求各位高手和大师告诉我,哪里出问题了,我实在 是找不出来啊!!! #include "stdafx.h...
  • 2. 线索二叉树结点的结构 有 n 个结点的二叉链表有 2n 个链域;空链域:n+1个;非空链域:n-1 个(两点之间连的线); 了解线索的概念 按照不同的遍历次序分为:先序线索二叉树、中序线索二叉树、后序线索二叉树...
  • 线索二叉树,设计的思想是什么呢?不用帮我写代码,告诉我思想就行了。比如,用递归算法完成遍历子树功能,我课本有代码,但是看不懂 。,,
  • 线索二叉树基本介绍 1)n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域,存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索") ● 2)...
  • 数据结构线索化二叉树

    千次阅读 2011-10-08 20:33:48
    除了根节点外每个节点都有一个指向父亲的引用,因此有n-1个引用,而n个节点总共有2*n个引用,因此还有n+1个引用没有使用,如果把这些引用分别指向当前节点的前驱或者后继,则将此二叉树线索化。线索化后的二叉树遍历...
  • 数据结构 线索二叉树 原理及实现

    千次阅读 2014-11-16 15:58:00
    通过考察各种二叉链表,不管儿叉树的形态如何,空链域的个数总是多过非空链域的个数。准确的说,n各结点的二叉链表共有2n个链域,... 记ptr指向二叉链表中的一个结点,以下是建立线索的规则:  (1)如果ptr->lc
  • 线索二叉树利用末节点的空指针将其他节点连接起来,达到整个树枝顺序和逆序都能遍历的...详细请看源代码: 为了以后快速查找,我还是简单说下怎么输入数据,如下图所示的数据结构: 像这样的数据结构我们怎么输入呢?
  • 中序线索二叉树线索二叉树概述线索二叉树代码实现线索二叉树的数据结构线索二叉树的遍历线索二叉树示例完整代码线索二叉树类 ThreadedBinaryTree线索二叉树节点类 ThreadedNode测试类 TestThreadBinaryTree ...
  • 首先要谈一谈线索二叉树为什么会产生,很多东西不是无缘无故的突然出现在书本,那么肯定是有他出现的理由,我先举个你们熟悉的案例,比如开始我们是使用单链表进行数据的存储和访问,但是访问方法只能从一端跑到顶,...
  • 数据结构——线索二叉树 指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树就称为线索二叉树(Threaded Binary Tree)。 请看图6-10-2,我们把这棵二叉树进行中序遍历后,将所有的空指针域...
  • 线索二叉树线索二叉树:前序遍历的线索二叉树:中序遍历的线索二叉树(常):后序遍历的线索二叉树:线索二叉树的节点结构及代码实现:中序线索二叉树的构造:中序线索二叉树的遍历: 线索二叉树: 在实现一颗二叉树...
  • C语言数据结构线索二叉树 tips:前些天学习了二叉树的相关操作,今天来总结一下线索二叉树的操作。 线索二叉树:对二叉树以某种次序遍历得到序列中的前驱和后继,其中指向结点前驱和后继的指针称为线索,再加上...
  • 数据结构-线索二叉树

    2020-03-16 23:30:33
    线索二叉树 ###为什么要有线索二叉树?   比如单向链表因为无法快速获得前驱结点,所以有了双向链表。...将每一隔加点扩展为五个元素的结构,每个节点包括:数据域、左标签、右标签、左指针、右...
  • 在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。 文章目录一、c语言实现先序线索、中序线索、...
  • 主要介绍了C语言数据结构线索二叉树及其遍历的相关资料,为了加快查找节点的前驱和后继。对二叉树的线索化就是对二叉树进行一次遍历,在遍历的过程中检测节点的左右指针是否为空,如果是空,则将他们改为指向前驱和...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,959
精华内容 783
关键字:

数据结构线索

数据结构 订阅