#include<iostream>
using namespace std;
struct BinaryTreeNode{
    int ltag,rtag;
    char data;
    BinaryTreeNode* leftChild;
    BinaryTreeNode* rightChild;
    BinaryTreeNode(char newdata,int newltag=0,int newrtag=0){
        data=newdata;
        ltag=newltag;
        rtag=newrtag;
    }
};
BinaryTreeNode* treeRoot;//声明树根节点指针
//前序和中序遍历重构二叉树
BinaryTreeNode* createBinaryTree(char* VLR,char* LVR,int n){
    if(n==0){
        return NULL;
    }
    int k=0;
    while(VLR[0]!=LVR[k]){
        k++;
    }
    BinaryTreeNode* p=new BinaryTreeNode(VLR[0]);
    p->leftChild=createBinaryTree(VLR+1,LVR,k);
    p->rightChild=createBinaryTree(VLR+k+1,LVR+k+1,n-k-1);
    return p;
}
void createInThread(BinaryTreeNode* current,BinaryTreeNode* &pre){
    if(current==NULL){
        return;
    }
    createInThread(current->leftChild,pre);
    if(current->leftChild==NULL){
        current->leftChild=pre;
        current->ltag=1;
    }
    if(pre!=NULL&&pre->rightChild==NULL){
        pre->rightChild=current;
        pre->rtag=1;
    }
    pre=current;
    createInThread(current->rightChild,pre);
}
//中序线索化二叉树
void createInThread(BinaryTreeNode* root){
    BinaryTreeNode* pre=NULL;
    if(root!=NULL){
        createInThread(root,pre);
        pre->rightChild=NULL;
        pre->rtag=1;
    }
}
//First
BinaryTreeNode* First(BinaryTreeNode* current){
    BinaryTreeNode* p=current;
    while(p->ltag==0){
        p=p->leftChild;
    }
    return p;
}
//Last
BinaryTreeNode* Last(BinaryTreeNode* current){
    BinaryTreeNode* p=current;
    while(p->rtag==0){
        p=p->rightChild;
    }
    return p;
}
//Next
BinaryTreeNode* Next(BinaryTreeNode* current){
    BinaryTreeNode* p=current->rightChild;
    if(current->rtag==0){
        return First(p);
    }else{
        return p;
    }
}
//Prior
BinaryTreeNode* Prior(BinaryTreeNode* current){
    BinaryTreeNode* p=current->leftChild;
    if(current->ltag==0){
        return Last(p);
    }else{
        return p;
    }
}
//中序遍历
void inOrder(BinaryTreeNode* root){
    BinaryTreeNode* p;
    for(p=First(root);p!=NULL;p=Next(p)){
        cout<<p->data;
    }
}
//前序遍历
void preOrder(BinaryTreeNode* root){
    BinaryTreeNode* p=root;
    while(p!=NULL){
        cout<<p->data;
        if(p->ltag==0){
            p=p->leftChild;
        }
        else if(p->rtag==0){
            p=p->rightChild;
        }
        else{
            while(p!=NULL&&p->rtag==1){
                p=p->rightChild;
            }
            if(p!=NULL) p=p->rightChild;
        }
    }
}
//寻找父节点
BinaryTreeNode* parent(BinaryTreeNode* t){
    BinaryTreeNode* p;
    if(t==treeRoot){
        return NULL;
    }
    for(p=t;p->ltag==0;p=p->leftChild);
    if(p->leftChild!=NULL){
        for(p=p->leftChild;p!=NULL&&p->leftChild!=t&&p->rightChild!=t;p=p->rightChild);
    }
    if(p==NULL||p->leftChild==NULL){
        for(p=t;p->rtag==0;p=p->rightChild);
        for(p=p->rightChild;p!=NULL&&p->leftChild!=t&&p->rightChild!=t;p=p->leftChild);
    }
    return p;
}
//后序遍历
void postOrder(BinaryTreeNode* root){
    cout<<"暂时没写";
}
int main(){
    char* vlr = "ABCDEFGH";//前序
    char* lvr = "CBEDFAGH";//中序
    //后序应为:CEFDBHGA
    treeRoot=createBinaryTree(vlr,lvr,8);//根据前序和中序序列创建二叉树，并返回根节点指针
    createInThread(treeRoot);
    cout<<"中序线索二叉树的中序遍历：";
    inOrder(treeRoot);
    cout<<endl;
    cout<<"前序线索二叉树的前序遍历：";
    preOrder(treeRoot);
    cout<<endl;
    cout<<"后序线索二叉树的后序遍历：";
    postOrder(treeRoot);
    cout<<endl;
    cout<<"查找父节点：";
    cout<<parent(treeRoot->leftChild)->data;//应该输出根节点data
    cout<<endl;
    return 0;
}