线索树

using namespace std;
typedef struct bithrnode
{
	char data;
	struct bithrnode *lchild;
	struct bithrnode *rchild;
	int ltag, rtag;
}BiThrNode, *BiThrTree;

BiThrTree pre;

void InitBTree(BiThrTree &BT);
void CreatBTree(BiThrTree &BT);
void AddThread(BiThrTree p);
void ThreadTree(BiThrTree BT, BiThrTree &head);
BiThrTree InorderNext(BiThrTree p);
void ThInorder(BiThrTree head);

void InitBTree(BiThrTree &BT)
{
	BT = NULL;
}


void CreatBTree(BiThrTree &BT)
{
	char ch;
	ch = getchar();
	if (ch == ' ')
		BT = NULL;
	else
	{
		BT = new BiThrNode;
		BT->data = ch;
		BT->ltag = 0;
		BT->rchild = 0;
		CreatBTree(BT->lchild);
		CreatBTree(BT->rchild);
	}
}



void ThreadTree(BiThrTree BT, BiThrTree &head)
{
	head = new BiThrNode;
	head->data = NULL;
	head->ltag = 0;
	head->rtag = 0;
	head->rchild = head;
	if (BT == NULL)
		head->lchild = head;
	else
	{
		pre = head;
		head->lchild = BT;
		AddThread(BT);
		pre->rchild = head;
		pre->rtag = 1;
		head->rchild = pre;
		head->rtag = 1;
	}
}


void AddThread(BiThrTree p)
{
	if (p != NULL)
	{
		AddThread(p->lchild);
		if (p->lchild == NULL)
		{
			p->ltag = 1;
			p->lchild = pre;
		}
		if (pre->rchild == NULL)
		{
			pre->rtag = 1;
			pre->rchild = p;
		}
		pre = p;
		AddThread(p->rchild);
	}
}


BiThrTree InorderNext(BiThrTree p)
{
	if (p->rtag == 1)
		return p->rchild;
	else
	{
		p = p->rchild;
		while (p->ltag == 0)
			p = p->lchild;
		return p;
	}
}


void ThInorder(BiThrTree head)
{
	BiThrTree HT;
	HT = head->lchild;
	while (HT != head)
		if (HT != NULL)
		{
			while (HT->ltag == 0)
				HT = HT->lchild;
			while (HT != head)
			{
				cout << HT->data << ' ';
				HT = InorderNext(HT);
			}
		}
}
void main()
{
	BiThrTree T, head;
	InitBTree(T);
	cout << "InitTree completed!" << endl;
	cout << "Create Tree:" << endl;
	CreatBTree(T);
	ThreadTree(T, head);
	cout << "The ThreadTree is Inordered:" << endl;
	ThInorder(head);
	system("pause");
}