线索二叉树，或者说，对二叉树线索化，实质上就是遍历一棵二叉树，在遍历的过程中，检查当前结点的左、右指针域是否为空。如果为空，将它们改为指向前驱结点或后继结点的线索。
当以二叉链表作为存储结构时，只能找到左右孩子信息，而不能直接得到结点在任意序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。 解决此问题最简单的办法是在每个节点上增加两个指针域fwd和bkwd，分别指示结点依任意次序遍历时得到前驱和后继信息。显然这样做使得结构的存储密度 大大降低，另一方面，在有n个结点的二叉链表中必定存在n+1个空链域。由此设想能否利用这些空链域来存放前驱和后继信息。
试做如下规定：若结点有左子树，则其lchild域指向其左孩子，否则域指示其前驱，若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。为了避免混淆，尚需改变结点结构，增加两个标志域。
lchild LTag data RTag rchild
其中：
LTag=0 lchild域指示结点的左孩子
LTag=1 lchild域指示结点的前驱
RTag=0 rchild域指示结点的右孩子
RTag=1 rchild域指示结点的后继
以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称为线索二叉树。对二叉树进行某种次序遍历使其变为线索二叉树的过程叫做线索化。
头文件：
/*****************************************************************************************************
*Copyright: Yue Workstation
*
*FileName: IndexTree.h
*
*Function: 线索二叉树数据结构定义
*
*Author: Abel Lee
*
*CreateOn: 2012-2-19
*
*Log: 2012-2-19 由Abel Lee创建
*****************************************************************************************************/
#ifndef INDEX_TREE_H
#define INDEX_TREE_H
#include "global.h"
typedef enum{Link,Thread} PointerTag; //指针标志
typedef int DataType;
typedef struct BiThreTree
{ //定义结点元素
PointerTag LTag,RTag;
DataType data;
struct BiThreTree *lchild,*rchild;
}BiThreTree;
BiThreTree *pre; //全局变量，用于二叉树的线索化
BiThreTree *CreateTree(void);
void InThread(BiThreTree *T);
BiThreTree *InOrderThrTree(BiThreTree *T);
void InThrTravel(BiThreTree *Thre);
#endif
源文件：
/*****************************************************************************************************
*Copyright:Yue Workstation
*
*FileName: IndexTree.c
*
*Function: 线索二叉树操作
*
*Author:Abel Lee
*
*CreateOn:2012-2-19
*
*Log:2011-5-3 由Abel Lee创建
*****************************************************************************************************/
#include "../inc/IndexTree.h"
/****************************************************************************************************
*Function Name: CreateTree
*
*Function: 按先序输入建立二叉树
*
*Parameter: 无
*
*Return Value:成功返回树的指针，失败返回NULL
*
*Author:Abel Lee
*
*Log:2012-2-19
***************************************************************************************************/
BiThreTree *CreateTree(void)
{
BiThreTree *T;
DataType e;
scanf("%d",&e);
if(e==0)
{
T=NULL;
}
else
{
T=(BiThreTree *)malloc(sizeof(BiThreTree));
T->data=e;
T->LTag=Link; //初始化时指针标志均为Link
T->RTag=Link;
T->lchild=CreateTree();
T->rchild=CreateTree();
}
return T;
}
/****************************************************************************************************
*Function Name: InThread
*
*Function:
*
*Parameter: 无
*
*Return Value:成功返回树的指针，失败返回NULL
*
*Author:Abel Lee
*
*Log:2012-2-19
***************************************************************************************************/
void InThread(BiThreTree *T)
{
BiThreTree *p;
p=T;
if(p)
{
InThread(p->lchild);
if(!p->lchild)
{
p->LTag=Thread;
p->lchild=pre;
}
if(!pre->rchild)
{
pre->RTag=Thread;
pre->rchild=p;
}
pre=p;
InThread(p->rchild);
}
}
/****************************************************************************************************
*Function Name: InOrderThrTree
*
*Function: 中序线索化二叉树
*
*Parameter: T:二叉树指针
*
*Return Value:成功返回树的指针，失败返回NULL
*
*Author:Abel Lee
*
*Log:2012-2-19
***************************************************************************************************/
BiThreTree *InOrderThrTree(BiThreTree *T)
{
BiThreTree *Thre; //Thre为头结点的指针
Thre=(BiThreTree *)malloc(sizeof(BiThreTree));
if(Thre == NULL)
{
perror("Thre == NULL,malloc error!\n");
return NULL;
}
Thre->lchild=T;
Thre->rchild=Thre;
pre=Thre;
InThread(T);
pre->RTag=Thread;
pre->rchild=Thre;
Thre->rchild=pre;
return Thre;
}
/****************************************************************************************************
*Function Name: InThrTravel
*
*Function: 中序遍历二叉树
*
*Parameter: Thre:二叉树指针
*
*Return Value:成功返回树的指针，失败返回NULL
*
*Author:Abel Lee
*
*Log:2012-2-19
***************************************************************************************************/
void InThrTravel(BiThreTree *Thre)
{
BiThreTree *p;
p=Thre->lchild;
while(p!=Thre) //指针回指向头结点时结束
{
while(p->LTag==Link)
p=p->lchild;
printf("%4d",p->data);
while(p->RTag==Thread&&p->rchild!=Thre)
{
p=p->rchild;
printf("%4d",p->data);
}
p=p->rchild;
}
}0daybank
文章评论