//创建二叉树，线索化二叉树，中序遍历二叉树

include <stdio.h>

include <stdlib.h>

typedef struct ThreadNode
{
char data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag;
} ThreadNode, *ThreadTree;
ThreadTree pre = NULL;
void CreateBTNode(ThreadTree T)
{
char ch;
scanf("%c", &ch);
if (ch == '#')
{
T = NULL;
}
else
{
T = (ThreadNode )malloc(sizeof(ThreadNode));
(T)->data = ch;
CreateBTNode(&(T)->lchild);
CreateBTNode(&(T)->rchild);
}
}
void InThread(ThreadTree p)
{
if (p != NULL)
{
InThread(p->lchild);
if (p->lchild == NULL)
{
p->lchild = pre;
p->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL)
{
pre->rchild = p;
pre->rtag = 1;
}
pre = p;
InThread(p->rchild);
}
}
void InOrderThraverse_Thr(ThreadTree p)
{
while (p)
{
//一直找左孩子，最后一个为中序序列中排第一的
while (p->ltag == 0)
{
p = p->lchild;
}
printf("%c ", p->data); //操作结点数据
//当结点右标志位为1时，直接找到其后继结点
while (p->rtag == 1 && p->rchild != NULL)
{
p = p->rchild;
printf("%c ", p->data);
}
//否则，按照中序遍历的规律，找其右子树中最左下的结点，也就是继续循环遍历
p = p->rchild;
}
}
int main()
{
ThreadTree T, p;
printf("创建二叉树："); //输入ABC##DE#G##F###
CreateBTNode(&T);
InThread(T);
printf("\n中序遍历：\n");
InOrderThraverse_Thr(T);
printf("\n");
return 0;
}