二叉树的输入、遍历、与线索化

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define Thread 0 //线索
#define Link 1 //孩子指针

//--------------------------二叉树存储节点----------------------------------
typedef struct BiNode
{
    char ch;
    int ltag,rtag; //是孩子还是线索的标志位
    struct BiNode *lchild,*rchild;
}BiNode ,*BiTree;

//------------------------打印----------------------------
void print(BiTree T)
{
    printf("%c",T->ch);
}



//-------------------前序创建二叉树---------------------------
/*
  (1)前序创建时最简单的，其他的有点复杂（因为创建头结
     点问题这里不深入讨论，以后都用前序创建）
  (2)用双重指针**T是因为在main中T=NULL直接把空指针T传
     过来会有问题，需要把T的地址传过来
*/
void CreatBiTree(BiNode **T)
{
    char c;
    scanf("%c",&c); //不能用fflush,由于是一次过输入多个

    if( ' ' == c )
    {
        *T = NULL;
    }
    else
    {
        *T=(BiNode *)malloc(sizeof(BiNode));
        (*T)->ch = c;
        CreatBiTree(&((*T)->lchild));//别忘了传的是地址，记得加&
        CreatBiTree(&((*T)->rchild));
    }

}




//-------------------------------------前序遍历---------------------------------------
void PreTravelBiTree(BiTree T)
{
    if(T) //别忘了递归反回条件
    {
    print(T);//放在最前面就是前序。。。
    PreTravelBiTree(T->lchild);
    PreTravelBiTree(T->rchild);
    }
}



//-------------------------------------中序遍历---------------------------------------
void MidTravelBiTree(BiTree T)
{
    if(T)
    {
    MidTravelBiTree(T->lchild);
    print(T);
    MidTravelBiTree(T->rchild);
    }
}


//-------------------------------------后序遍历---------------------------------------
void LastTravelBiTree(BiTree T)
{
    if(T)
    {
    LastTravelBiTree(T->lchild);
    LastTravelBiTree(T->rchild);
    print(T);
    }
}






//----------------------前序遍历线索化----------------------------------
/*
 * 如果孩子为空就把标志位变成线索标志位，原来的NULL r/lchild用来储存线索
 *如果孩子不为空，就跳过，并标注为孩子标志位
*/

BiTree pre;
PreThreadTree(BiTree T)
    if(T)
    {
        PreThreadTree(T->lchild);
        if( T->lchild == NULL )//由于还不知道下个节点（后继）是哪个，所以这个节点只能算出它的前驱
        {
            T->ltag=Thread;//如果左孩子为空就把标志位变成线索标志位（Thread），存放前一个节点（前驱）pre
            T->lchild=pre;
        }
        else
        {
            T->ltag=Link;
        }

        /*
         *这个节点是前一个节点的后继，可以知道前一个节点的
         *后继，前一个节点可以用pre全局变量暂存起来
        */
        if( pre->rchild==NULL )
        {
            pre->rtag=Thread;/*如果右孩子为空就把标志位变成线索标志位（Thread）
                              存放前一个节点pre的后继，就是本次的T*/
            pre->rchild=T;

        }
        else
        {
            pre->rtag=Link;
        }
        pre=T;
        PreThreadTree(T->rchild);
        /*
        if(T->ltag == Link) //前序时记得加上这条判断
        PreThreadTree(T->lchild);
        if(T->rtag == Link)
        PreThreadTree(T->rchild);
        */
    }
}



BiTree ThreadInit(BiTree T)
{
    BiTree p;//头结点
    p = (BiTree)malloc(sizeof(BiNode));
    p->lchild = NULL;
    p->rchild = NULL;
    /*注意，这里之前p->rchild=T;中序遍历头结点指向的不是树根T，如果p->rchild=T，
     *118处会跳过if，以至头结点指向树根，和194行错误，提前退出while循环
     */
    p->ltag = Thread;
    p->rtag = Thread;
    pre = p;//头结点变成前一个节点存放在pre中
    PreThreadTree(T);
    p->lchild=pre;
    /*变成一个循环双向链表，注意由于最后一个节点有可能没有空孩子，存放不了头结点
     *的地址，（也就是说这个双向链表有可能在头结点可以指向尾节点，而尾节点指不向头结点）
    */
    return p;
}


//------------------中序线索二叉树的遍历后继--------------------------------
void PreThreadTravel(BiTree p)
{
    BiTree q;
    printf("\n\n中序线索二叉树的后继遍历:\n");
    while( p != pre )//别忘了循环，到尾节点结束
    {
    if( p->rtag == Thread )
    {
        p=p->rchild;
        print(p);
    }
    else
    {
        q=p->rchild;
        while( q->ltag != Thread )
            q=q->lchild;
        print(q);
        p=q;
    }
    }
}


//---------------------------中序线索二叉树的遍历前继-------------------------------
void LastThreadTravel(BiTree f)

{
    BiTree q,p;
    p=f;
    printf("\n\n中序线索二叉树的前继遍历:\n");
    while( p != f->rchild )//到第一个节点结束（头结点的后继）
    {
    if( p->ltag == Thread )
    {
        p=p->lchild;
        print(p);
    }
    else
    {
        q=p->lchild;
        while( q->rtag != Thread )
            q=q->rchild;
        print(q);
        p=q;
    }
    }
}

//-----------------------------------------------------------------------------------
main()
{

    BiTree T,p;
    T = NULL;

    printf("前序创建输入数据\n");
    CreatBiTree(&T); //由于T=NULL，所以用传指针的地址，即双重指针

    printf("前序遍历打印二叉树：\n");
    PreTravelBiTree(T);
    printf("\n");

    printf("中序遍历打印二叉树：\n");
    MidTravelBiTree(T);
    printf("\n");

    printf("后序遍历打印二叉树：\n");
    LastTravelBiTree(T);
    printf("\n");

    p=ThreadInit(T);//p为建立的线索二叉树的头结点

    PreThreadTravel(p);//中序线索二叉树的遍历前驱
    LastThreadTravel(p);//中序线索二叉树的遍历前继

    return 0;
}