线索二叉树

线索二叉树是二叉树线索化，实质是在遍历二叉树的过程中，检查当前节点的左右指针域是否为空，若为空，则将它们改为指向前驱节点或后继节点的线索。

1. 定义

typedef struct node
{
    ElemType data;
    int ltag, rtag; //增加线索标记，若为1，则表示指向前驱，否则指向孩子
    struct node *lchild;
    struct node *rchild;
}TBNode;

2. 中序线索二叉树

TBTNode *pre;
void Thread(TBTNode *&p)
{
    if(p!=NULL){
        Thread(p->lchild);
        // 建立当前节点的前驱线索
        if(p->lchild==NULL){
            p->lchild=pre;
            p->ltag=1;
        }
        else p->ltag=0;
        // 建立前驱节点的后继线索
        if(pre->rchild==NULL){
            pre-rchild=p;
            pre->rtag=1;
        }
        else pre->rtag=0;
        pre=p;
        Thread(p->rchild);
    }
}
TBTNode *CreaThread(TBTNode *b)
{    
    // 创建头结点
    TBTNode *root;
    root=(TBTNode *)malloc(sizeof(TBTNode));
    root->ltag=0;
    root->rtag=1;
    root->rchild=b;
    if(b==NUll)
        root->lchild=root;
    else{
        root->lchild=b;
        // pre 是 *p 的前驱节点，供加线索
        pre=root;
        Thread(b);
        // 最后加入指向头结点的线索和头结点线索化
        pre->rchild=root;
        pre->rtag=1;
        root->rchild=pre;
    }
    return root;
}

3. 遍历线索二叉树

void ThInOrder(TBTNode *tb)
{
    TBTNode *p=tb->lchild;
    while(p!=NULL){
        while(p->ltag==0)
            p=p->lchild;
        printf("%c", p->data);
        while(p->rtag==1 && p->rchild!=tb){
            p=p->rchild;
            printf("%c", p->data);
        }
        p=p->rchild;
    }
}