1. 前言

n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为"线索")。
这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded   BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
注意:线索链表解决了二叉链表找左、右孩子困难的问题,出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题。

2. 二叉树线索化的定义

n个结点的二叉树,采用链式存储结构时,有n+1个空链域,利用这些空链域存放指向结点的直接前驱和直接后继的指针。若规定结点有左子树,则其lchild域指示其左子女,否则令lchild域指示其前驱;若结点有右子树,则其rchild域指示其右子女,否则令rchild域指示其后继。为了避免混淆,我们需改变结点结构,在二叉存储结构的结点结构上增加两

个标志域,这样,每个结点的存储结构如下:

  • 线索链表:以上述结点结构构成的二叉链表作为二叉树存储结构的链表。
  • 线索:指向结点前驱和后继的指针。
  • 线索二叉树:每个结点上加上线索的二叉树。
  • 线索化:对二叉树以某种次序遍历使其变为线索二叉树的过程。

建立线索二叉树,或者说,对二叉树线索化,实质上就是遍历一棵二叉树,在遍历的过程中,检查当前结点的左、右指针域是否为空。如果为空,将它们改为指向前驱结点或后继结点的线索。

线索链表中的结点结构为:

图 线索链表中的结点结构

其中:ltag和rtag是增加的两个标志域,用来区分结点的左、右指针域是指向其左、右孩子的指针,还是指向其前趋或后继的线索。

线索二叉树的存储结构类型定义描述如下:

C代码  收藏代码
  1. /*Link=0表示指向孩子结点,Thread=1表示指向前驱结点或后继结点*/
  2. typedef enmu {Link, Thread} PointerTag;
  3. /*线索二叉树存储结构定义*/
  4. typedef struct Node
  5. {
  6.         DataType data;                  /*数据域*/
  7.         struct Node *lchild, rchild;  /*指向左孩子结点或右孩子结点的指针*/
  8.         PointerTag ltag, rtag;         /*标志域*/
  9. }*BiThrTree, BiThrNode;

 

3. 线索二叉树的表示

【例】下面(a)图所示的中序线索二叉树,其线索链表如下面(b)图所示。

图 中序线索二叉树及其存储结构

注意:
图中的实线表示指针,虚线表示线索。
结点C的左线索为空,表示C是中序序列的开始结点,无前趋;
结点E的右线索为空,表示E是中序序列的终端结点,无后继。
线索二叉树中,一个结点是叶结点的充要条件为:左、右标志均是1。

4. 二叉树的线索化

(1)线索化和线索化实质
将二叉树变为线索二叉树的过程称为线索化。
按某种次序将二叉树线索化的实质是:按该次序遍历二叉树,在遍历过程中用线索取代空指针。

(2).二叉树的中序线索化
① 分析
算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。
该算法应附设一个指针pre始终指向刚刚访问过的结点(pre的初值应为NULL),而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋,而*p是*pre的后继。

② 将二叉树按中序线索化的算法

C代码  收藏代码
  1. typedef enum { Link,Thread} PointerTag; //枚举值Link和Thread分别为0,1
  2.   typedef struct node{
  3.       DataType data;
  4.       PointerTag ltag,rtag; //左右标志
  5.       Struct node *lchild,*rchild;
  6.     } BinThrNode;\\线索二叉树的结点类型
  7.   typedef BinThrNode *BinThrTree;
  8.   BinThrNode *pre=NULL; //全局量
  9.   void lnorderThreading(BinThrTree p)
  10.     {//将二叉树p中序线索化
  11.       if(p){ //p非空时,当前访问结点是*p
  12.              InorderThreading(p->lchild); //左子树线索化
  13.                  //以下直至右子树线索化之前相当于遍历算法中访问结点的操作
  14.              p->ltag=(p->lchild)?Link:Thread; //左指针非空时左标志为Link
  15.                                              //(即0),否则为Thread(即1)
  16.              p->rtag=(p->rchild)?Link:Thread;
  17.              *(pre){ //若*p的前趋*pre存在
  18.                    if(pre->rtag==Thread) //若*p的前趋右标志为线索
  19.                         pre->rchild=p; //令*pre的右线索指向中序后继
  20.                   if(p->ltag==Thread) //*p的左标志为线索
  21.                        p->lchild=pre; //令*p的左线索指向中序前趋
  22.                  } // 完成处理*pre的线索
  23.              pre=p; //令pre是下一访问结点的中序前趋
  24.              InorderThreeding(p->rehild); //右子树线索化
  25.            }//endif
  26.     } //InorderThreading

③ 算法分析
和中序遍历算法一样,递归过程中对每结点仅做一次访问。因此对于n个结点的二叉树,算法的时间复杂度亦为O(n)。

5. 遍历线索二叉树

遍历某种次序的线索二叉树,只要从该次序下的开始结点开发,反复找到结点在该次序下的后继,直至终端结点。
遍历中序线索二叉树算法:

C代码  收藏代码
  1. void TraverseInorderThrTree(BinThrTree p)
  2.     { //遍历中序线索二叉树
  3.      if(p){//树非空
  4.       while(p->ltag==Link)
  5.        p=p->lchild; //从根往下找最左下结点,即中序序列的开始结点
  6.       do{
  7.        printf("%c",p->data); //访问结点
  8.        p=InorderSuccessor(p); //找*p的中序后继
  9.       }while(p)
  10.      }//endif
  11.     }//TraverselnorderThrTree

分析:
① 中序序列的终端结点的右线索为空,所以do语句的终止条件是p==NULL。
② 该算法的时间复杂性为O(n)。因为是非递归算法,常数因子上小于递归的遍历算法。因此,若对一棵二叉树要经常遍历,或查找结点在指定次序下的前趋和后继,则应采用线索链表作为存储结构为宜。
③ 以上介绍的线索二叉树是一种全线索树(即左右线索均要建立)。许多应用中只要建立左右线索中的一种。
④ 若在线索链表中增加一个头结点,令头结点的左指针指向根,右指针指向其遍历序列的开始或终端结点会更方便。