线索二叉树

线索二叉树

线索二叉树的存储结构

线索二叉树的存储结构描述如下

1
2
3
4
5
ltag = 0 lchild域指示结点的左孩子
ltag = 1 lchild域指示结点的前驱
//
rtag = 0 rchild域指示结点的右孩子
rtag = 1 rchild域指示结点的后继
1
2
3
4
5
typedef struct ThreadNode{
ElemType data; //数据元素
struct ThreadNode *lchild,*rchild; //左右孩子指针
int ltag,rtag; //左右线索标志
}ThreadNode,*ThreadTree;

中序线索二叉树的构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InThread(ThreadTree &p,ThreadNode &pre){
if(p!=NULL){
InThread(p->lchild,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); //递归,线索化右子树
}//if(p!=NULL)
}
}
1
2
3
4
5
6
7
8
void CreateInThread(ThreadTree T){
ThreadTree pre = NULL;
if(T!=NULL){ //非空二叉树。线索化
InThread(T,pre); //线索化二叉树
pre->rchild=NULL; //处理遍历的最后一个结点
pre->rtag=1;
}
}

中序线索二叉树的遍历

1)求中序线索二叉树中中序序列下的第一个结点

1
2
3
4
Thread *Firstnode(ThreadNode *p){
while(p->ltag==0) p=p->lchild; //最左下结点(不一定是叶结点)
return p;
}

2)求中序线索二叉树中结点p在中序序列下的后继

1
2
3
4
ThreadNode *Nextnode(ThreadNode *p){
if(p->rtag==0) return Firstnode(p->rchild);
else return p->rchild; //rtag==1直接返回后继线索
}

3)利用上面两个算法,可以写出不含头节点的中序线索二叉树的中序遍历算法

1
2
3
4
void Inorder(ThreadNode *T){
for(ThreadNode *p=Firstnode;p!=NULL;p=Nextnode(p))
visit(p);
}