数据结构线索二叉树

矫情吗；* 2023-10-08 07:23 5阅读 0赞

一、线索二叉树的原理

通过考察各种二叉链表，不管儿叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n+1个。如下图所示。

![26548237_13584035961B18.jpg][]

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

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

（1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱；

（2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继；

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

![26548237_13584034551s55.jpg][]

其中：

（1）ltag为0时指向该结点的左孩子，为1时指向该结点的前驱；

（2）rtag为0时指向该结点的右孩子，为1时指向该结点的后继；

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

![26548237_1358403668csC7.jpg][]

二、线索二叉树结构实现

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

/* 二叉树的二叉线索存储结构定义*/
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          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，完成后继结点的线索化。如图：

![Center][]

if(!p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过，赋值了pre，所以可以将pre赋值给p->lchild，并修改p->ltag = Thread（也就是定义为1）以完成前驱结点的线索化。

![Center 1][]

完成前驱和后继的判断后，不要忘记当前结点p赋值给pre，以便于下一次使用。

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

![Center 2][]

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

![26548237_1358405432AqdL.jpg][]

遍历代码如下所示。

//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->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)。  
由于充分利用了空指针域的空间（等于节省了空间），又保证了创建时的一次遍历就可以终生受用后继的信息（意味着节省了时间）。所以在实际问题中，如果所用的二叉树需要经过遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

#include <stdio.h>
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          #include <stdlib.h>
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          #define ERROR  0
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          #define OK  1
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          typedef 
         
         
          enum{Link, Thread} PointerTag;      
         
         
          //link = 0表示指向左右孩子指针
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
                                                     
         
         
          //Thread = 1表示指向前驱或后继的线索
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          typedef 
         
         
          struct BitNode
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          char data;                              
         
         
          //结点数据
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          struct BitNode *lchild;                 
         
         
          //左右孩子指针
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          struct BitNode *rchild; 
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             PointerTag ltag;                        
         
         
          //左右标志
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             PointerTag rtag;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         }BitNode, *BiTree;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         BiTree pre;                                 
         
         
          //全局变量，始终指向刚刚访问过的结点
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          //前序创建二叉树
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          void CreateTree(BiTree *t)
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          char ch;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          scanf(
         
         
          "%c", &ch);
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
              
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          if(ch == 
         
         
          '#')
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 *t = 
         
         
          NULL;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          else
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 (*t) = (BiTree)
         
         
          malloc(
         
         
          sizeof(BitNode));
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
                 
         
         
          if((*t) == 
         
         
          NULL)
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
                     
         
         
          return;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 (*t)->data = ch;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 CreateTree(&((*t)->lchild));
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 CreateTree(&((*t)->rchild));
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          //t指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          //中序遍历二叉线索树表示的二叉树t
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          int InOrderThraverse_Thr(BiTree t)
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             BiTree p;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             p = t->lchild;           
         
         
          //p指向根结点
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          while(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;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          //中序遍历进行中序线索化
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          void InThreading(BiTree p)
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          if(p)
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 InThreading(p->lchild);              
         
         
          //递归左子树线索化
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
                 
         
         
          if(!p->lchild)                       
         
         
          //没有左孩子
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                     p->ltag = Thread;                
         
         
          //前驱线索
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                     p->lchild = pre;             
         
         
          //左孩子指针指向前驱,这里是第3步
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
                 
         
         
          if(!pre->rchild)                 
         
         
          //没有右孩子
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                     pre->rtag = Thread;              
         
         
          //后继线索
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                     pre->rchild = p;             
         
         
          //前驱右孩子指针指向后继(当前结点p)
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 pre = p;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 InThreading(p->rchild);              
         
         
          //递归右子树线索化
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          //建立头结点，中序线索二叉树
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          int InOrderThread_Head(BiTree *h, BiTree t)
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             (*h) = (BiTree)
         
         
          malloc(
         
         
          sizeof(BitNode));
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          if((*h) == 
         
         
          NULL)
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
                 
         
         
          return ERROR;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             (*h)->rchild = *h;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             (*h)->rtag = Link;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          if(!t)      
         
         
          //如果为NULL
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 (*h)->lchild = *h;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 (*h)->ltag = Link;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          else
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 pre = *h;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 (*h)->lchild = t;        
         
         
          //第一步
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 (*h)->ltag = Link;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 InThreading(t);         
         
         
          //找到最后一个结点
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 pre->rchild = *h;        
         
         
          //第四步
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 pre->rtag = Thread;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
                 (*h)->rchild = pre;      
         
         
          //第二步
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         }
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
         
         
          int main(int argc, char **argv)
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         {
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             BiTree t;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             BiTree temp;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
          
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          printf(
         
         
          "请输入前序二叉树的内容:\n");
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             CreateTree(&t);                 
         
         
          //建立二叉树
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             InOrderThread_Head(&temp, t);       
         
         
          //加入头结点，并线索化
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          printf(
         
         
          "输出中序二叉树的内容:\n");
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
             InOrderThraverse_Thr(temp);
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
              
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          printf(
         
         
          "\n");
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
             
         
         
          return 
         
         
          0;
        
        
         
       
       
        
       
       
       
        
        
        
         
       
       
        
       
       
        
        
        
         
          
         
         }

[26548237_13584035961B18.jpg]: http://blog.chinaunix.net/attachment/201301/17/26548237_13584035961B18.jpg
[26548237_13584034551s55.jpg]: http://blog.chinaunix.net/attachment/201301/17/26548237_13584034551s55.jpg
[26548237_1358403668csC7.jpg]: http://blog.chinaunix.net/attachment/201301/17/26548237_1358403668csC7.jpg
[Center]: https://img-blog.csdn.net/20141026170851882?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxNDQ5MjYwOQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20141026171113750?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxNDQ5MjYwOQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: https://img-blog.csdn.net/20141026171202062?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxNDQ5MjYwOQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[26548237_1358405432AqdL.jpg]: http://blog.chinaunix.net/attachment/201301/17/26548237_1358405432AqdL.jpg