关于二叉线索树的一个例子

二叉线索树：
结构：Ltag,Rtag,LChild,RChild
if   Ltag=1:该节点没有左孩子，链接的是前趋
if   Ltag=0:该节点有左孩子，链接的是左孩子
if   Rtag=1:该节点没有右孩子，链接的是后继
if   Rtag=0:该节点有右孩子，链接的是右孩子

typedef struct Node
{
char data;
int Ltag,Rtag;
struct Node *LChild,*RChild;
}BiTNode,*BiTree;

线索二叉树的构造函数：

void CreateBiTree(BiTree *root)
{
char ch;
ch=getchar();
if(ch=='.')
*root=NULL;
else
{
*root=(BiTree)malloc(sizeof(BiTNode));
(*root)->data=ch;
(*root)->Ltag=0;
(*root)->Rtag=0;
CreateBiTree(&(*root)->LChild);
CreateBiTree(&(*root)->RChild);
}
}
BiTNode *pre;
BiTNode *next;
void InThread(BiTree root)
{
if(root!=NULL)
{
InThread(root->LChild)
if(root->LChild==NULL)
{
root->Ltag=1;
root->LChild=pre;
}
else if(pre!=NULL&&pre->RChild==NULL)
{
pre->RChild=1;
pre->RChild=root;
}
pre=root;
if(pre->RChild==NULL)
pre->Rtag=1;
InThread(root->RChild);
}
}

这个就是线索二叉树的创建，它把一颗二叉树炼成了一个以NULL开头，以NULL结尾的链表。

下面是寻找前趋，寻找后继的算法：

BiTNode *Inpre(BiTNode *p)
{
BiTNode *w;
if(p->Ltag==1)
pre=p->LChild;
else
{
for(w=p->LChild;w->Rtag==0;w=w->RChild);
pre=w;
return pre;
}
}

//中序列后继函数
BiTNode *InNext(BiTNode *p)
{
BiTNode *q;
if(p->RChild==1)
next=p->RChild;
else
{
for(q=p->RChild;q->Ltag==0;q=q->LChild);
next=q;
}
return next;
}

下面是关于线索二叉树的一个完整的例子：

#include<stdio.h>
#include<stdlib.h>


typedef struct Node
{
    char data;
    struct Node *LChild;
    int Ltag;
    struct Node *RChild;
    int Rtag;
}BiTNode,*BiTree;

//建立中序列线索树
void CreateTree(BiTree *root)
{
    char ch;
    ch=getchar();
    if(ch=='.')
        *root=NULL;
    else
    {
        *root=(BiTree)malloc(sizeof(BiTNode));
        (*root)->data=ch;
        (*root)->Ltag=0;
        (*root)->Rtag=0;
        CreateTree(&((*root)->LChild));
        CreateTree(&((*root)->RChild));
    }
}

BiTNode *pre;
BiTNode *next;
void Inthread(BiTree root)
{
 if(root!=NULL)
 {
    Inthread(root->LChild);
    if(root->LChild==NULL)
    {
        root->Ltag=1;
        root->LChild=pre;

    }
    if(pre!=NULL&&pre->RChild==NULL)
    {

        pre->RChild=root;
        pre->Rtag=1;
    }
    pre=root;
    if(pre->RChild==NULL)
        pre->Rtag=1;
    Inthread(root->RChild);
}
}

BiTNode *InPre(BiTNode *p)
{
    BiTNode *w;
    if(p->Ltag==1)
        pre=p->LChild;
    else
    {
        for(w=p->LChild;w->Rtag==0;w=w->RChild);
            pre=w;
    }
    return pre;
}

//寻找后继
BiTNode *InNext(BiTNode *p)
{
    BiTNode *q;
    if(p->Rtag==1)
        next=p->RChild;
    else
    {
        for(q=p->RChild;q->Ltag==0;q=q->LChild);
        next=q;
    }
    return  next;
}
void Find(BiTree root)
{
    BiTNode *p;
    p=root;
    while(p->LChild!=NULL)
        p=p->LChild;
    printf("%c的Ltag=%d，Rtag=%d\n",p->data,p->Ltag,p->Rtag);
    p=p->RChild;
    while(p)
    {
        printf("%c的Ltag=%d，Rtag=%d\n",p->data,p->Ltag,p->Rtag);
        p=p->RChild;
    }
}
void SortVisit(BiTree root)
{
    BiTNode *p,*n;
    BiTNode *q,*m;
    p=root;
    while(p->LChild!=NULL)
            p=p->LChild;
    printf("请找出节点%c的前趋与后继\n",p->data);
    q=(BiTNode *)malloc(sizeof(BiTNode));
    m=(BiTNode *)malloc(sizeof(BiTNode));
    q=InPre(p);
    m=InNext(p);
    if(q==NULL)
        printf("前趋是NULL,后继是%c\n",m->data);
    else if(m==NULL)
        printf("前趋是%c,后继是NULL\n",q->data);
    else
        printf("前趋是%c\t后继是 %c\n",q->data,m->data);
    p=p->RChild;
    while(p)
    {
        printf("请找出节点%c的前趋与后继\n",p->data);
        q=(BiTNode *)malloc(sizeof(BiTNode));
        m=(BiTNode *)malloc(sizeof(BiTNode));
        q=InPre(p);
        m=InNext(p);
        if(q==NULL)
            printf("前趋是NULL,后继是%c\n",m->data);
        else if(m==NULL)
            printf("前趋是%c,后继是NULL\n",q->data);
        else
            printf("前趋是%c\t后继是 %c\n",q->data,m->data);
        p=p->RChild;
    }
}
int main()
{
    BiTree root;
    BiTree t;
    printf("请创建一个线索二叉树\n");
    CreateTree(&root);
    Inthread(root);
    Find(root);
    SortVisit(root);
}

这个例子可以打出所有节点的前趋和后继以及他们是否有左右孩子。