前面曾提到为了方便存储LINK字段及节省LINK字段的浪费,将树化为二叉树,据估计可将2/3的浪费减少到1/2左右。一般而言,一个n节点的二叉树,共有2n个LINK字段,实际上只用了n-1个,造成2n-(n-1)=n+1个LINK字段的浪费,为了充分利用这些空的LINK字段,将空的LINK转换成线索二叉树(Thread Binary Tree)。
如何将二叉树转化成线索二叉树呢?很简单,只要先把二叉树以中序遍历方式将数据排列好,然后把缺少左或右LINK的节点挑出来,看看其相邻的左、右节点。图5-22(a)、(b)的中序遍历数据排列是HDIBEAJFKCG。
图5-22(a)中,节点E的相邻左、右节点分别是B和A,因此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-22(b)中线索二叉树在内存内完整的表示如图5-24所示。
图5-24 线索二叉树在内存内完整表示示意图
在图5-24中,节点H的左LINK和节点G的右LINK都指向头节点。注意头节点没有数据而且头节点的右LINK指向它本身(RBIT永远为1)。当各节点的左或右LINK为1时,指向某一节点的指针是实线,否则为虚线。
线索二叉树的优点:可以利用线索二叉树来遍历任一节点的中序后继(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;
}
先将ptr的rlink指定给this_n,假设ptr的rbit是0,则this_n即为ptr的中序后继;若ptr的rbit是1且this_n的lbit也是1,将this_n的llink指定给this_n,一直做到this_n的lbit是0为止,此时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的右方,而且节点3的rbit为0。
(a) (b)
图5-25 线索二叉树的插入1
如图5-26所示为线索二叉树的插入,将节点5加在节点2的右方,而且节点2的rbit为1。
在S节点的右面加T节点
(a) (b)
图5-26 线索二叉树的插入2
假设有一棵线索二叉树如图5-25(a)与图5-26(a)所示,若各自插入一节点T于节点S的右方,需考虑S节点的右方是实线还是虚线,图形将变成如图5-25(b)与图5-26(b),注意图5-25(a)的S指向3,而图5-26(a)的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;
}
}
读者通过对照上述图形与程序,便能体会其原理。