（1）线索二叉树

我只能说很难的了

#include<bits/stdc++.h>
using namespace std;
typedef char ElemType;
struct ThreadNode{
	ElemType data;
	ThreadNode *lchild;
	ThreadNode *rchild;
	int ltag;
	int rtag;
};
typedef ThreadNode* ThreadTree;
string str="ABDH#K###E##CFI###G#J##";
int indx=0;
ThreadTree prev;
void createTree(ThreadTree *T)
{
	ElemType ch;
	ch=str[indx++];
	if(ch=='#')
	{
		*T=NULL;
	}
	else
	{
		*T=new ThreadNode;
		(*T)->data=ch;
		createTree(&(*T)->lchild);//&的优先级最小 
		if((*T)->lchild!=NULL)
		{
			(*T)->ltag=0;
		}
		createTree(&(*T)->rchild);
		{
			(*T)->rtag=0;
		}
	}
}
void threading(ThreadTree T)
{
	if(T!=NULL)
	{
		threading(T->lchild);
		if(T->lchild==NULL)
		{
			T->ltag=1;
			T->lchild=prev;
		}
		if(prev->rchild==NULL)
		{
			prev->rtag=1;
			prev->rchild=T;
		}
		prev=T;//相当于中序遍历的输出 
		threading(T->rchild);//相当于中序遍历 
	}
}
void inOrderThreading(ThreadTree *head,ThreadTree T)
{
	*head =new ThreadNode;
	(*head)->ltag=0;
	(*head)->rtag=1;
	(*head)->rchild=(*head);
	if(T==NULL)
	{
		(*head)->lchild=*head;
	}
	else
	{
		(*head)->lchild=T;
		prev=(*head);
		threading(T);
		//最后一个节点线索化 
		prev->rchild=*head;
		prev->rtag=1;
		//头节点右孩子指向最后一个结点
		(*head)->rchild=prev; 
	}
}
void inOrder(ThreadTree T)
{
	ThreadTree curr;
	curr=T->lchild;
	while(curr!=T)
	{
		while(curr->ltag==0)
		{
			curr=curr->lchild;
		}
		cout<<curr->data;
		while(curr->rtag==1&&curr->rchild!=T)
		{
			curr=curr->rchild;
			cout<<curr->data;
		}
		curr=curr->rchild;
	}
	cout<<endl;
}

int main()
{
	ThreadTree head;
	ThreadTree T;
	createTree(&T);
	inOrderThreading(&head,T);
	inOrder(head);
}