中序遍历的线索二叉树

#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;

/*
 * 线索二叉树:
 *      用来加速查找前驱和后继
 * 中序线索二叉树:
 *      1.初始结点是最左下的结点
 *      2.终止结点是最右下的结点
 *      3.线索二叉树中结点p的前驱结点是p的左子树的最右下结点
 *      4.线索二叉树中结点p的后继结点是p的右子树的最左下结点
 * 线索二叉树的算法思想:
 * 　　 1.因为要设置前驱和后继,所以需要一个前驱指针pre(pre是p的前驱)和指向当前结点的指针p(我们的算法是中序线索二叉树,初始结点是最左下的节点,所以pre就是他的前驱,pre结点初始可以为空)
 *　　　2.中序遍历过程中,如果p的左指针为空,则将其指向pre,如果pre的右指针为空,则将其指向p
 */

//线索二叉树的存储结构
typedef struct ThreadNode
{
    ElemType data;
    ThreadNode *lchild,*rchild;
    int ltag,rtag;
    int sum;
}ThreadNode,*ThreadTree;

//先序递归建立线索二叉树
void CreateThreadTree(ThreadTree &tree)
{
    char ch;
    if ((ch=getchar())==‘#‘)
        tree=NULL;
    else
    {
        tree=(ThreadTree)malloc(sizeof(ThreadNode));
        tree->data=ch;
        CreateThreadTree(tree->lchild);
        CreateThreadTree(tree->rchild);
    }

}

//中序遍历线索化
void InThread(ThreadTree &p,ThreadTree &pre)
{
    //pre初始是一个空指针,就是用来充当前驱的
    if (p!=NULL)    //递归的终止条件
    {
        InThread(p->lchild,pre); //找到最左边的初始结点
        if (p->lchild==NULL)
        {
            p->lchild=pre;    //p的前驱结点是pre
            p->ltag=1;
        }
        if(pre!=NULL&&p->rchild!=NULL)
        {
            pre->rchild=p;  //pre的后继结点是p
            pre->rtag=1;
        }
        pre=p;
        InThread(p->rchild,pre); //递归遍历右子树
    }
}

//中序遍历建立线索二叉树的算法
void CreateInThread(ThreadTree &T)
{
    ThreadTree pre;  //用来保存前驱结点的指针
    if (T!=NULL){  //对非空的线索二叉树进行线索化
        InThread(T,pre);   //线索化二叉树
        pre->rchild=NULL;    //处理遍历的最后一个结点
        pre->rtag=1;
    }
}

//求中序线索二叉树中序序列下的第一个节点
ThreadTree FirstNode(ThreadTree p)
{
    while (p->ltag==0)
        p=p->lchild;   //找到初始结点(最左下结点)
    return p;
}
//求线索二叉树中序序列的最后一个结点
ThreadTree FinalNode(ThreadTree p)
{
    while (p->rtag==0)
        p=p->rchild;   //得到终止结点(最右下结点)
    return p;
}

//求线索二叉树中结点p在中序序列下的后继
ThreadTree NextNode(ThreadTree p)
{
    //p的后继结点是p的右子树的最左下结点
    //因为中序是LNR顺序访问
    if (p->rtag==0)
        return FirstNode(p->rchild);//得到p的右子树的最左下结点
    else    //否则直接返回后继线索,证明该节点没有右孩子
        return p->rchild;
}

//求线索二叉树中结点p在中序序列下的前驱
ThreadTree PreNode(ThreadTree p)
{
    //p的前驱结点是p的左子树的最右下结点
    if (p->ltag==0)
        return NextNode(p->lchild);
    else
        return p->lchild;
}

//先序遍历线索二叉树
void InOrder(ThreadTree tree)
{
    if (tree!=NULL)
    {
        tree->sum++;
        printf("%c ",tree->data);
        InOrder(tree->lchild);
        InOrder(tree->rchild);
    }
}
int main()
{
    ThreadTree tree;
    CreateThreadTree(tree);  //先序递归建立线索二叉树
    CreateInThread(tree);
    printf("%c\n",FirstNode(tree)->data);
    printf("%c",NextNode(tree)->data);
    InOrder(tree);

    return 0;
}