线索二叉树
遍历二叉树以一定的规则将二叉树中的结点排列成一个线性序列,每个结点(第一个和最后一个结点除外)都有一个直接前驱和直接后继。
利用空链域存放指向其直接前驱或后继的指针。
若无左子树,令lchild指向其前驱结点;若无右子树,令rchild指向其后继结点。还需增加两个标志域表明当前指针域所指对象是指左(右)子结点还是直接前驱(后继)。
typedef struct ThreadNode
{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode, *ThreadTree;
对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。
pre标记的是刚刚访问过的结点
void InThread(ThreadTree &p, ThreadTree &pre)
{
//注意这里传的是引用
if(p!=NULL){
InThread(p->Thread,pre);
if(p->lchild==NULL){ //已经没有更左的结点了,访问并建立前驱线索
p->lchild=pre;
p->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL{
//建立前驱结点的后续线索
pre->rchild=p;
pre->rtag=1;
}
pre=p; //标记当前结点为刚刚访问过的结点
InThread(p->rchild, pre);
}
}
void CreateInThread(ThreadTree T)
{
ThreadTree pre=NULL;
if(T!=NULL){
InThread(T, pre);
pre->rchild=NULL; //处理遍历的最后一个结点,因为递归传的是引用,
//最后退出上一句的时候pre指向指向最后一个元素
pre->rtag=1;
}
}
线索二叉树的遍历
中序线索二叉树中中序序列下的第一个结点
ThreadNode *Firstnode(ThreadNode *p){
while(p->ltag==0) p=p->lchild;
return p;
}
中序线索二叉树中结点p在中序序列下的后继结点
ThreadNode *Nextnode(ThreadNode *p){
if(p->rtag==0) return FirstNode(p);
else return p->rchild;
}
不含头结点的中序线索二叉树的中序遍历
void InOrder(ThreadNode *T){
for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
visit(p);
}