#include <iostream>
using namespace std;
enum Tag{
    Link,
    Thread
};
struct Node{
    char data;
    Node *left;
    Node *right;
    Tag lTag;
    Tag rTag;
};
typedef Node*  Btree;
/*前序遍历创建二叉树*/
void createTree(Btree &T){
    char ch;
    cin >> ch;
    if(ch == '#')  T = NULL;
    else{
        T = (Btree)malloc(sizeof(Btree));
        T->data = ch;
        T->lTag = Link;
        T->rTag = Link;
        T->left = NULL;
        T->right = NULL;
        createTree(T->left);
        createTree(T->right);
    }
}
/*中序遍历进行中序线索化*/
Btree pre = NULL; /*始终指向刚刚访问过的节点*/
void inThreading(Btree &T){
    if(T == NULL) return;
    inThreading(T->left);
    if(T->left == NULL){
        T->lTag = Thread;
        T->left = pre;
    }
    if(pre && pre->right == NULL){
        pre->rTag = Thread;
        pre->right = T;
    }
    pre = T;
    inThreading(T->right);
}

/*中序遍历*/
void inOrderTraverse(Btree &T){
    if(T == NULL) return;
    inOrderTraverse(T->left);
    printf("%c ", T->data);
    inOrderTraverse(T->right);
}
/*
在中序线索二叉树中，查找结点 *p 的中序后继结点分两种情形：
a). 若 *p 的右子树空 ( 即 p->rtag 为 Thread) ，则 p->rchild 为右线索，直接指向 *p 的中序后继。
b). 若 *p 的右子树非空 ( 即 p->rtag 为 Link) ，则 *p 的中序后继必是其右子树中第一个中序遍历到的结点。
    也就是从 *p 的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有左孩子的结点为止，该结点是 *p 的右子树中 “ 最左下 ” 的结点，即 *P 的中序后继结点。
*/
void inorder(Btree &T){
    /*循环找到中序遍历的第一个节点*/
    Btree cur = T;
    while(cur->lTag == Link){  //这里中序第一个节点的lTag为Thread设置过了
        cur = cur->left;
    }
    while(cur)
    {
        printf("%c ", cur->data);
        if(cur->rTag == Thread) {
            cur = cur->right;
        }
        else{
            cur = cur->right;  // 这个地方要小心
            while(cur && cur->lTag == Link)
            {
                cur = cur->left;
            }
        }
    }
}
int main() {
    cout << "请输入中序遍历的扩展二叉树序列" << endl;
    /*#B#D#A#C#*/
    Btree boot;
    createTree(boot);
    cout << endl;
    /*中序打印*/
    cout << "普通中序遍历" << endl;
    inOrderTraverse(boot);
    cout << endl;
    /*中序遍历进行中序线索化*/
    cout << "中序线索化开始" << endl;
    inThreading(boot);
    cout << "中序线索化结束" << endl;
    /*按照链表的方式进行遍历*/
    cout << "中序线索二叉树遍历" << endl;
    inorder(boot);
    cout<<endl; 
    while(1);
    return 0;
}