线索二叉树

1.用土办法找到中序前驱

//进行中序遍历 
void InOrder(BiTree T){
    if(T!= NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild); 
    }
} 

//访问结点q
void visit(BiTNode *q)
{
    if(q == p)
     final = pre;//当前刚问结点正好是结点p，那么找到p的前驱 
    else 
     pre = q;//pre指向当前结点 
 } 

//辅助全局变量查找结点p的前驱
BiNode *p; //p指向目标结点
BiTNode * pre=NULL; //指向当前访问结点的前驱
BiTNode *final =NULL //用于记录最终结果  

2.中序线索化

//全局变量 pre 指向当前访问结点的前驱
ThreadNode *pre = NULL;

//中序线索化二叉树
void CreatInThread(ThreadTree T){
    pre = NULL; //pre初始为NULL
    if(T != NULL){   //非空二叉树才能进行线索化 
        InThread(T); // 中序线索化二叉树
        if (pre->rchild == NULL)
         pre->rtag = 1; //处理遍历的最后一个结点 
    } 
}

//线索化二叉树结点
typedef struct ThreadNode{
    Elemtype data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;  //左右线索标志 
}ThreadNode,* ThreadTree;

//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T)
{
    if(T!= NULL)
    {
        InThread(T->lchild);//中序遍历左子树 
        visit(T);//访问根节点 
        InThread(T->rchild);//中序遍历右子树 
    }
 } 

 void visit(ThreadNode *q)
  {
    if(q->lchild == NULL){//左子树为空，建立前驱线索 
        q->lchild = pre;
        q->ltag = 1;
    }
    if(pre != NULL&&pre->rchild ==NULL)
    {
        pre->rchild = q;//建立前驱结点的后继线索 
        rtag = 1;
    }

        pre = q;

  }

遍历步骤：
1.设立一个pre表示当前访问结点的前驱结点
2.访问当前结点，如果当前结点左子树为空则将左子树指向pre
3.如果pre结点的右子树为空，则指向当前结点
4.遍历 结束后检查pre的rchild是否为NUll，如果是则令rtag=1

先序线索化与中序线索化的区别
1. 先visit
2.对结点的访问可能会出现无限循环，原地打转的情况

void PreThread(ThreadTree T)
{
    if(T!= NULL)
    {
        visit(T);  //先处理根节点 
        if(T->ltag == 0) //lchild不是前驱线索 
        PreThread (T->lchild);
        PreThread(T->rchild);

    }
}

后序线索化没有无限循环问题，因为先把左子树和右子树全部处理完了

void postThread(ThreadTree T)
{
    if(T!= NULL)
    {   
        PostThread(T->lchild);
        PostThread(T->rchild);
        visit(T);//左右根 
    }
 } 

不管什么线索化都要注意最后一个结点的处理