线索二叉树及其运算

一.线索二叉树的定义:
　　 n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded   BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
  注意：
    　线索链表解决了二叉链表找左、右孩子困难的问题，出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题。
二.线索链表的结点结构
    　线索链表中的结点结构为：
typedef int ElemType;
struct ThreNode
{ ElemType data;
  ThreNode *lch,*rch;
  int ltag,rtag;
}

说明：ltag=0 lchild是指向结点的左孩子的指针

ltag=1 lchild是指向结点的前趋的左线索。

rtag=0 rchild是指向结点的右孩子的指针

rtag=1 rchild是指向结点的后继的右线索针；     
三.线索化二叉树类
    将二叉树变为线索二叉树的过程称为线索化。
    按某种次序将二叉树线索化的实质是：按该次序遍历二叉树，在遍历过程中用线索取代空指针。
线索化二叉树这一数据结构，具有自己的存储结构和一系列相关运算。主要运算有二叉树的建立；二叉树的先根线索化、中根线索化、后根线索化；以及在某种线索化二叉树上进行查找等等。这里我们重点介绍下二叉树的中根线索化。
二叉树的中序线索化
（1）分析
    　算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。
    　该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。
（2）将二叉树按中序线索化的算法
void inthread (Btnode *p)
{ if (p!=NULL)
   {inthread (p->lch) ；
   printf ( “ ％ 6c ”， p->data) ；
   if (p->lch!=NULL) p->ltag=0 ；
  else { p->ltag=1 ；
         p->lch=pr ；
       }  /* 建立 p 结点的左线索，指向前趋结点 pr */
  if (pr!=NULL)
    { if (pr->rch!=NULL) pr->rtag=0 ；
  else{ pr->rtag=1 ；
        pr->rch=p ；
      }    /* 建立前趋结点 pr 的右线索，指向结点 p */
   }
         pr=p ；　　 /* 前驱指针 pr 跟上当前指针 p ，以便 p 向后移动 */
         inthread (p → rch) ；
   }
} /* inthread */
（3）算法分析
    　此算法之中 pr 是全局变量，在主程序中置初值为空。在 inthread 函数中 pr 始终做为当前结点 p 的前趋结点指针。在线索化过程中，一边判断二叉树的结点有无孩子，一边给标志域置 0 或 1 ，一边建立线索。在阅读此算法时，将 printf ( “ ％ 6c ”， p->data) 语句开始到 pr=p 语句为止的 一组语句看成一个整体，把整段语句理解为“访问”操作，这就是典型的中根遍历的算法思路。

四．线索二叉树的运算
在中根线索树上查找某结点的前趋和后继
(1) 已知 q 结点，找出它的前趋结点。
　　根据线索树的基本概念，当 q->ltag ＝ 1 时， q->lch 就指向 q 的前趋。当 q->ltag=0 时，表明 q 有左孩子。由中根遍历的规律可知，做为根 q 的前趋结点 ( 或者说以根结点为后继的结点 ) ，它应是中根遍历 q 的左子树时 , 所访问的最后一个结点，即左子树的最右尾结点。若用 p 指针记录 q 的前趋前趋结点，求 q 的前趋结点的算法如下：
ThreNode*inpre(ThreNode *q)
 { ThreNode *p,*r;
  if(q->ltag==1)p=q->lch;    //找到q的前驱
  else{ r=q->lch;     //在q的左子树，找最右尾结点
        while(r->rtag!=1)r=r->rch;
        p=r;
   }
 returnp;
 }
(2) 已知 q 结点，找出它的后继结点。
　　当 q->rtag ＝ 1 时， q->rch 即指向 q 的后继结点。若 q->rt ＝ 0 ，表明 q 有右孩子，那么 q 的后继应是中序遍历 q 的右子树时 , 访问的第一个结点，即右子树的最左结点。算法如下：
ThreNode *ThTree::insucc(ThreNode *q)
 { ThreNode *p,*r;
   if(q->rtag==1)p=q->rch;
   else{r=q->rch;
        while(r->ltag!=1)r=r->lch;
        p=r;
       }
   returnp;
 }

在中根线索树上遍历二叉树
　　遍历某种次序的线索二叉树，只要从该次序下的开始结点开发，反复找到结点在该次序下的后继，直至终端结点。
　　遍历中序线索二叉树算法：
void ThTree::inthorder()
 { ThreNode *p;
   p=root;
   if(p!=NULL)
   while(p->lch!=NULL)p=p->lch;    //查找树的最左结点
   cout<<"\n  "<data;
   while(p->rch!=NULL){p=insucc(p);
   cout<<"  "<data;
 };
}
　分析：
　　① 中序序列的终端结点的右线索为空，所以do语句的终止条件是p==NULL。
　　② 该算法的时间复杂性为O(n)。因为是非递归算法，常数因子上小于递归的遍历算法。因此，若对一棵二叉树要经常遍历，或查找结点在指定次序下的前趋和后继，则应采用线索链表作为存储结构为宜。
　　③ 以上介绍的线索二叉树是一种全线索树（即左右线索均要建立）。许多应用中只要建立左右线索中的一种。
　　④ 若在线索链表中增加一个头结点，令头结点的左指针指向根，右指针指向其遍历序列的开始或终端结点会更方便。