#include<stdio.h>
#include<stdlib.h>

#define Max_Size 100

typedef struct Node
{
    char ch;
    int lflag, rflag;
    struct Node *lchild, *rchild;
}Node, *LNode;

Node *Sign_link;

LNode Create_tree();
void Show_tree(LNode root);
void In_Thread(LNode root);
void In_Thorder(LNode root);
Node *In_Subsequence(Node *link);

int main()
{
    LNode root = NULL;
    root = Create_tree();

    printf("————先根遍历————");
    Show_tree(root);

    putchar(10);

    In_Thread(root);
    printf("————线索中根遍历————");
    In_Thorder(root);

    putchar(10);
    return 0;
}

//建立二叉树
LNode Create_tree()
{
    char c;
    int i, j;
    LNode root = NULL;
    Node *s[Max_Size];
    Node *link;
    printf("\n i, c: ");
    scanf("%d%c", &i, &c);
    while((i != 0) && (c != 0))
    {
        link = (Node *)malloc(sizeof(Node));
        link->ch = c;
        link->lchild = NULL;
        link->rchild = NULL;
        s[i] = link;
        if(i == 1)
            root = link;
        else
        {
            j = i / 2;
            if(i % 2 == 0)
                s[j]->lchild = link;
            else
                s[j]->rchild = link;
        }
        printf("\n i, c: ");
        scanf("%d%c", &i, &c);
    }
    return root;
}

//先根遍历
void Show_tree(LNode root)
{
    if(root != NULL)
    {
        printf("%4c", root->ch);
        Show_tree(root->lchild);
        Show_tree(root->rchild);
    }
}

//建立线索二叉树
void In_Thread(LNode root)
{
    if(root != NULL)
    {
        In_Thread(root->lchild);
        if(root->lchild == NULL)
        {
            root->lflag = 1;
            root->lchild = Sign_link;
        }
        else   
            root->lflag = 0;

        if(Sign_link->rchild == NULL)
        {
            Sign_link->rflag = 1;
            Sign_link->rchild = root;
        }
        else   
            Sign_link->rflag = 0;

        Sign_link = root;
        In_Thread(root->rchild);
    }
}

//线索二叉树遍历
void In_Thorder(LNode root)
{
    Node *incept_link;
    if(root == NULL)
    {
        printf("The tree is empty!\n");
        return;
    }
    incept_link = root;
    while(incept_link->lchild != NULL)
        incept_link = incept_link->lchild;
    printf("%4c", incept_link->ch);
    while(incept_link != NULL)
    {
        incept_link = In_Subsequence(incept_link);
        printf("%4c", incept_link->ch);
    }
}

//中跟线索树上一结点，找它的后继结点
Node *In_Subsequence(Node *link)
{
    Node *incept_link, *buffer_link;
    if(link == NULL)
    {
        printf("There is no subsequence!\n");
        return NULL;
    }
    if(link->rflag == 1)
        incept_link = link->rchild;
    else
    {
        buffer_link = link->rchild;
        while(buffer_link->rflag != 1)
            buffer_link = buffer_link->lchild;
        incept_link = buffer_link;
    }
    return incept_link;
}