您的位置: 网站首页 > 程序开发 > 数据结构 > 第5章 树与二叉树 > 【5.7 线索二叉树】

5.7 线索二叉树

 

5.7  线索二叉树

前面曾提到为了方便存储LINK字段及节省LINK字段的浪费,将树化为二叉树,据估计可将2/3的浪费减少到1/2左右。一般而言,一个n节点的二叉树,共有2nLINK字段,实际上只用了n-1个,造成2n-(n-1)=n+1LINK字段的浪费,为了充分利用这些空的LINK字段,将空的LINK转换成线索二叉树(Thread Binary Tree)。

如何将二叉树转化成线索二叉树呢?很简单,只要先把二叉树以中序遍历方式将数据排列好,然后把缺少左或右LINK的节点挑出来,看看其相邻的左、右节点。图5-22a)、(b)的中序遍历数据排列是HDIBEAJFKCG

5-22a)中,节点E的相邻左、右节点分别是BA,因此E的左LINK指到B节点,而右LINK指到A节点。读者会问H节点的左LINK指到哪里,而G节点的右LINK又会指到哪里,回答这个问题前,请看线索二叉树的数据结构,如图5-23所示。

a                             b

5-22  将二叉树(a)转成线索二叉树(b

5-23  线索二叉树的数据结构

1)当LBIT=1时,LINK是正常指针。

2)当LBIT=0时,LINK是线索。

3)当RBIT=1时,RLINK是正常指针。

4)当RBIT=0时,RLINK是线索。

假定所有线索二叉树都有一个头节点(Head Node),此时图5-22b)中线索二叉树在内存内完整的表示如图5-24所示。

5-24  线索二叉树在内存内完整表示示意图

在图5-24中,节点H的左LINK和节点G的右LINK都指向头节点。注意头节点没有数据而且头节点的右LINK指向它本身(RBIT永远为1)。当各节点的左或右LINK1时,指向某一节点的指针是实线,否则为虚线。

线索二叉树的优点:可以利用线索二叉树来遍历任一节点的中序后继(Inorder Successor),其做法如下述程序段所示。

C语言程序:搜索线索二叉树节点的中序后继。

Node_type *insuc(Node_type  *ptr)

{

   Node_type *this_n;

   this_n=ptr->rlink;

   if(ptr->rbit==1)

        while(this_n->lbit==1)

           this_n=this_n->llink;     

   return this_n;

}

先将ptrrlink指定给this_n,假设ptrrbit0,则this_n即为ptr的中序后继;若ptrrbit1this_nlbit也是1,将this_nllink指定给this_n,一直做到this_nlbit0为止,此时this_n即为ptr的中序后继。

假设要将线索二叉树的所有节点以中序方式列出,则只要重复调用insuc()即可,做法如下述程序所示。

C语言程序:遍历线索二叉树。

void tinorder(Node_type  *tree,Node_type  *head)

{

   tree=head;

   printf("%d",tree->data);

   for(; ;)

   {

      tree=insuc(tree);

      if(tree==head)

          return;

      printf("%d",tree->data);

   }

}

此函数可以由任一节点来遍历,如可以由B节点(图5-24)开始,以中序法来遍历此线索二叉树的所有节点,结果为BEAJFKCG-HDI

除了可以遍历线索二叉树中序后继者,当然也可以遍历线索二叉树的中序前行者,其做法如下述程序所示。

C语言程序:查找线索二叉树的中序前行者。

Node_type *pred(Node_type  *ptr)

{

   Node_tye *this_n;

   this_n=ptr->llink;

   if(ptr->lbit==1)

      while(this_n->rbit==1 )

         this_n=this_n->rlink;

   return this_n;

}

一般二叉树在中序遍历时需要使用堆栈,而线索二叉树不需要用堆栈。一般二叉树需要事先预留一大块的联机空间,线索二叉树则可以由某一节点知道其前行者与后继者是哪一节点,而不需遍历整棵树。线索二叉树若要插入或删除某一节点,则操作较一般二叉树慢,因为牵涉到线索的重排。下面来讨论如何在线索二叉树中插入一个节点。

如图5-25所示为线索二叉树的插入,将节点5加在节点3的右方,而且节点3rbit0

a                      b

5-25  线索二叉树的插入1

如图5-26所示为线索二叉树的插入,将节点5加在节点2的右方,而且节点2rbit1

S节点的右面加T节点

 

a                       b

5-26  线索二叉树的插入2

假设有一棵线索二叉树如图5-25a)与图5-26a)所示,若各自插入一节点T于节点S的右方,需考虑S节点的右方是实线还是虚线,图形将变成如图5-25b)与图5-26b),注意图5-25a)的S指向3,而图5-26a)的S指向2

参阅下面的程序段。

C语言程序:将新节点插入某节点的右方。

void insert_right(Node_type *S,Node_type *T)

{

   Node_type *w;

   T->rchild=S->rchild;

   T->rbit=S->rbit;

   T->lchild=S;

   T->lbit=0;

   S->rchild=T;

   S->rbit=1 ;

   if(T->rbit==1)                                    /*T下面还有tree */

   {

      w=insucc(T);

      w->lchild=T;

   }

}

读者通过对照上述图形与程序,便能体会其原理。