线索二叉树的构建和遍历，为什么遍历出来的是错误的，求大佬解答



#include<stdio.h>
#include<iostream.h>  
#include<stdlib.h>  
#include<malloc.h>
typedef enum  
{  
    Link,   
    Thread  
} PointTag;  

typedef struct BTNode//定义结点类型  
{  
char data;  
struct BTNode *lchild;  
struct BTNode *rchild;
  PointTag  Ltag, Rtag;
}BTNode;  
BTNode *pre;  

  
  
void create(BTNode *&p)//创建二叉树，输入'^'表示空  
{  
char a;  
a=getchar();//12^3^^4^^这样子输入  
if(a=='^')  
p=NULL;  
else  
{  
p=(BTNode *)malloc(sizeof(BTNode));  
p->data=a;  
create(p->lchild);  
create(p->rchild);  
}  
return;  
}  
  
void output(BTNode *p)//先序输出二叉树的内容  
{  
if(p)  
{  
printf("%c\n",p->data);  
output(p->lchild);  
output(p->rchild);  
}  
}
 

//先序线索化二叉树
void _PreOrderThreading(BTNode *&T)  
    {  
        if (T == NULL)  
        {  
            return;  
        }
        if (T->lchild == NULL) //没有左子树  
        {  
             T->lchild = pre;   //前驱  
            T->Ltag = Thread;  
        }  
        if (pre!= NULL && pre->rchild == NULL) // 上一个节点有没有  右子树  
        {  //Prev第一次进来 为空   
            pre->rchild = T;   //后继  
            pre->Rtag = Thread;  
        }  
        pre = T;//前驱  ， 每次记住上次的节点  
  
        //判断Root是否有左右孩子  
        if (T->Ltag == Link)  
            _PreOrderThreading(T->lchild);  
        if (T->Rtag == Link)  
            _PreOrderThreading(T->rchild);  
    }  
 
//先序遍历线索二叉树
void _PreOrder(BTNode * T)  
    {  
        if (T==NULL)  
        {  
            return;  
        }  
        BTNode * p=T;  
        while (p!= NULL)  
        {  
            while (p->lchild != NULL && p->Ltag == Link)//找到最左边的节点,左标记一直为Link  
            {  
                cout << p->data << ' ';  
                p = p->lchild;  
            }  
            //到这来，左边的的节点还没有访问  
            cout << p->data<< ' ';  
  
            if (p->Ltag == Thread)//遇到线索 就看右节点  
            {  
                p = p->rchild;  
            }  
            while (p != NULL)//循环右节点  
            {  
                if (p->lchild != NULL && p->Ltag == Link)//遇到左节点存在 ， 则访问  
                {  
                    break;  
                }  
                cout << p->data << ' ';  
                p = p->rchild;  
            }  
        }
   
    }  

//中序遍历线索化二叉树

void _InOrderThreading(BTNode *& T)  
    {  
        if (T==NULL)  
        {  
            return;  
        }  
        _InOrderThreading(T->lchild);    // 左  
           
        if (T->lchild== NULL) //根  
        {  
            T->Ltag = Thread;  
            T->lchild = pre;  
        }  
        if (pre != NULL && pre->rchild == NULL)  
        {  
            pre->rchild = T;  
            pre->Rtag = Thread;  
        }  
        pre = T;  
        _InOrderThreading(T->rchild);   //右  
    }  

//中序遍历线索二叉树

void _InOrder(BTNode * T)  
    {  
        if (T == NULL)  
        {  
            return;  
        }  
         
        while (pre)  
        {  
            while (pre->Ltag == Link) //找最左边的节点  
            {  
                pre= pre->lchild;  
            }  
            cout << pre->data << ' ';  
            while ( pre && pre->Rtag == Thread )//找中序后继节点  
            {  
                pre = pre->rchild;  
                cout << pre->data << ' ';  
            }  
            //没有后继，有右子树     
            pre = pre->rchild;  
        }  
    }  
//后序线索化二叉树
void _PostThreading(BTNode *&T)  
    {  
        if (T)  
        {  
            _PostThreading(T->lchild);  
            _PostThreading(T->rchild);  
            if (T->lchild == NULL)  
            {  
                T->lchild = pre;  
                T->Ltag = Thread;  
            }  
            if (pre && pre->rchild == NULL ) //条件 Prev  
            {  
                pre->rchild = T;  
                pre->Rtag = Thread;  
            }  
            pre = T;  
        }  
    }  


      
int main()//主函数  
{  
BTNode *q=NULL;  
printf("please input data:");  
create(q);  
output(q);
cout<<"选择线索化和遍历方式（1：先序；2：中序；3：后序）"<<endl;
int a;
cin>>a;
switch(a){
case 1:
  _PreOrderThreading(q);
  _PreOrder(q);
 break;
case 2:
  _InOrderThreading(q);
  _InOrder(q);
  break;
case 3:
  _PostThreading(q);
  break;
default:
    cout<<endl<<"输入错误";
    break;
}
return 0;  
  
}