#include<iostream>

using namespace std;

struct Student
{
    char number[10];
    char name[8];
    int grade;
};           //data数据域
typedef Student EType;

struct BinaryTreeNode
{
    EType data;
    BinaryTreeNode *LChild;
    bool Lflag;
    BinaryTreeNode *RChild;
    bool Rflag;
};   

EType STATUS[12]={{"200701","肖象",100},{"200702","李明明",98},{"200703","刘辉",96},{"200704","陈晓曼",95},{"200705","邓昌华",92},{"200706","方伟文",85},{"200707","曾宁新",83},{"200708","罗逸",80},{"200709","谢彤彤",77},{"200710","孙冉冉",68},{"200711","田宁梦",67},{"200712","王博涵",65}};
//关于堆栈的一些结构
struct SType
{
      BinaryTreeNode *p;
};

struct Stack
{
      SType *element;
      int top;
      int Maxsize;
};

void CreateStack(Stack &S,int maxsize)
{
    S.Maxsize=maxsize;
    S.top=-1;
    S.element=new SType[S.Maxsize];
}

bool IsEmpty(Stack &S)
{
    if(S.top==-1) return true;
    else return false;
}

void Push(Stack &S,SType &x)
{
    S.top++;
    S.element[S.top]=x;
}

void Pop(Stack &S,SType &x)
{
    x=S.element[S.top];
    S.top--;
}

//构造二叉树
BinaryTreeNode *MakeNode(EType &x)
{
    BinaryTreeNode *p;
    p=new BinaryTreeNode;
    if(!p) return NULL;
    p->data=x;
    p->LChild=NULL;
    p->Lflag=false;
    p->RChild=NULL;
    p->Rflag=false;
    return p;
}


void MakeBinaryTree(BinaryTreeNode *root,BinaryTreeNode *left,BinaryTreeNode *right)
{
    root->LChild=left;
    root->RChild=right;
}


//二叉树转化为前序二叉线索树
void PreOrderThreading (BinaryTreeNode *BT)
{//二叉树转化为前序线索树算法
    SType            temp;
    Stack            S;
    BinaryTreeNode    *p = BT,*q=NULL;        //q始终指在p结点前驱
    int                MaxStackSize=50;
    CreateStack(S , MaxStackSize);            //产生一个空栈，这一过程函数可以不在这里进行
    while ( ( p || !IsEmpty(S)))
    {
        while (p )
        {
            temp.p=p;
            Push (S, temp);                    //根结点指针进栈，以后回朔时再退栈
            if (p->RChild)
                p->Rflag = false;
            else
                p->Rflag = true;
            if (p->LChild)                    //如果p仍有左子树继续向左推进
            {
                if (!p->RChild)
                    p->RChild=p->LChild;
                p->Lflag = false;
                q = p;
                p = p->LChild;  
            }
            else            
            {//如果p没有左子树，p的左链接域指向前驱；并准备退栈
                p->Lflag = true;
                p->LChild= q;     
                q=p;
                break;
            }
        }
        if (!IsEmpty(S))
        {
            Pop(S,temp);
            p=temp.p;
            if (!p->Rflag)
            {   
                q->RChild=p->RChild;
                p=p->RChild;                //指针指向回朔结点的右子树
            }
            else
                p=NULL;                        //p设为空，进行再次退栈
        }
    }
    q-> Rflag=true;                            //将二叉树的最右子孙的右链接域标志设为1
    q->RChild=NULL;   
}


//二叉树转化为中序二叉线索树
void InOrderThreading(BinaryTreeNode *BT)
{
    Stack S;
    SType x;
    BinaryTreeNode *p=BT,*q=NULL;
    int maxsize=50;
    CreateStack(S,maxsize);
    while(p||(!IsEmpty(S)))
    {
        while(p)
        {
            x.p=p;
            Push(S,x);
            if(p->LChild)
            {
                p->Lflag=false;
                p=p->LChild;
            }
            else
            {
                p->LChild=q;
                p->Lflag=true;
                q=p;
                p=NULL;
            }
        }
        if(!IsEmpty(S))
        {
            Pop(S,x);
            p=x.p;
            p->Rflag=false;
            if(!q->RChild&&q!=p)
            {
                q->RChild=p;
                q->Rflag=false;
                q=p;
            }
            p=p->RChild;
        }
    }
    q->Rflag=true;
}

//中序线索树中插入T节点作为S节点的左孩子
void InOrderThreadInsertLeft(BinaryTreeNode *S,BinaryTreeNode *T)
{
    BinaryTreeNode *q;
    T->Rflag=true;
    T->RChild=S;
    T->Lflag=S->Lflag;
    T->LChild=S->LChild;
    S->LChild=T;
    S->Lflag=false;
    if(!T->Lflag)
    {
        q=T->LChild;
        while(!q->Rflag)
        {
            q=q->RChild;
        }
        q->RChild=T;
    }
}

//中序线索树中插入T节点作为S节点的右孩子
void InOrderThreadInsertRight(BinaryTreeNode *S,BinaryTreeNode *T)
{
    BinaryTreeNode *q;
    T->Lflag=true;
    T->LChild=S;
    T->Rflag=S->Rflag;
    T->RChild=S->RChild;
    S->Rflag=false;
    S->RChild=T;
    if(!T->Rflag)
    {
        q=T->RChild;
        while(!q->Lflag)
        {
            q=q->LChild;
        }
        q->LChild=T;
    }
}




void PreOrderThreadTraversalOutPut(BinaryTreeNode *BT)
{//二叉线索树的遍历
        BinaryTreeNode *p=BT;
        cout<<endl;
        cout<<"    LChild      Lflag     学号      姓名     成绩    Rflag     RChild         "<<endl;
        cout<<" ------------------====================================-------------------"<<endl;
        while (p)
        {
            if (!p ->LChild)
                cout<<"  NULL";
            else
                cout<<"   "<<p ->LChild->data.number;
            if (!p ->Lflag)
                cout<<"<─";
            else
                cout<<"<--";

            cout<<"     "<<p ->Lflag
                << " \t"<<p->data.number
                << "      "<<p->data.name
                << "    "<<p->data.grade
                <<"       "<<p->Rflag;
            if (!p ->Rflag)
                cout<<"       ─>";
            else
                cout<<"       -->";

            if (!p ->RChild)
                cout<<"NULL";
            else
                cout<<" "<<p ->RChild->data.number;
        
            cout << endl;
            if (!p ->Lflag)
                p = p ->LChild;
            else
                p = p->RChild;
        }
}



int main()
{
      BinaryTreeNode *p[12];
      for(int i=0;i<12;i++)
      {
           p[i]=MakeNode(STATUS[i]);
      }
      MakeBinaryTree(p[0],p[1],p[2]);
       MakeBinaryTree(p[1],p[3],p[4]);
          MakeBinaryTree(p[2],p[5],p[6]);
     MakeBinaryTree(p[3],p[7],NULL);
      MakeBinaryTree(p[4],p[8],p[9]);
PreOrderThreading(p[0]);
PreOrderThreadTraversalOutPut(p[0]);
cout<<endl<<endl;
InOrderThreadInsertLeft(p[5],p[10]);
PreOrderThreadTraversalOutPut(p[0]);
cout<<endl<<endl;
InOrderThreadInsertRight(p[7],p[11]);
PreOrderThreadTraversalOutPut(p[0]);
return 0;
}