head.h

#include<iostream>
#define LINK 0//定义节点类型：指针
#define THREAD 1//定于节点类型：线索
using namespace std;
///////////////////////二叉树树节点类
class BitNode
{
public:
	BitNode();
	char ch;
	BitNode *lchild, *rchild;
	int LTag, RTag;
};
///////////////////////二叉树节点类的构造函数
BitNode::BitNode()
{
	lchild = rchild = NULL;
	LTag = RTag = LINK;
}
///////////////////////////////BiTree_Thread类
class BiTree_Thread
{
public:
	BiTree_Thread();
	void PreOrderCreatBiTree();
	void InOrderTraverse_Thread();
private:
	void ReMove();
	void InOrderThreading();
	void InThreading(BitNode*&);
	void Creat(BitNode*&);
	void ReMoveBiTree(BitNode*&);
	BitNode *root, *pre, *p, *start;
	char ch;
};
///////////////////////////////BiTree_Thread类的构造函数
BiTree_Thread::BiTree_Thread()
{
	root = pre = p = start = NULL;
}
/////////////////////////////////////////先序建立二叉树接口函数
void BiTree_Thread::PreOrderCreatBiTree()
{
	cout << "PreOrderCreatBiTree Called !" << endl << endl;
	cout << "Please Input The BiTree In PreOrder :" << endl << endl;
	ReMove(); //移除原先的树
	Creat(root); //建立新树
	cin.clear(); //解除cin的异常状态
}
//////////////////////////////////////先序递归建立二叉树
void BiTree_Thread::Creat(BitNode *&t)
{
	if (cin >> ch)
	{
		if (ch != '#')
		{
			t = new BitNode; //开辟新节点
			t->ch = ch;
			Creat(t->lchild); //递归建立其左子树
			Creat(t->rchild); //递归建立其右子树
		}
		else
			t = NULL;
	}
}
/////////////////////////////////////////////////中序线索化遍历二叉树接口函数
void BiTree_Thread::InOrderTraverse_Thread()
{
	cout << "InOrderTraverse_Thread Called !" << endl << endl;
	if (root == NULL) //若树空
	{
		cout << "BiTree Is Empty !" << endl << endl;
		PreOrderCreatBiTree(); //新建一棵二叉树
	}
	if (start == NULL) //若未被线索化
		InOrderThreading(); //中序线索化
	p = start->lchild; //p转到root节点
	while (p != start) //循环遍历之
	{
		while (p->LTag == LINK) //如果指向左孩子的是指针
		{
			p = p->lchild; //转到其左孩子
		}
		cout << p->ch << endl; //访问节点
		while (p->RTag == THREAD && p->rchild != start) //当指向右孩子的是线索时
		{
			p = p->rchild; //转向右孩子
			cout << p->ch << endl; //访问之
		}
		p = p->rchild; //转向右孩子
	}
}
//////////////////////////////////////中序线索化主程序
void BiTree_Thread::InOrderThreading()
{
	start = new BitNode; //开辟一个额外的节点作为线索化遍历的起点和终点
	start->LTag = LINK; //左标志设为指针
	start->RTag = THREAD; //右标志初始化为线索
	start->rchild = start; //起点的右孩子回指向其自身
	if (root == NULL) //若不存在一颗二叉树
	{
		start->lchild = start; //左指针回指
	}
	else //否则
	{
		start->lchild = root; //起始点指向二叉树的根节点
		pre = start; //初始化pre指向起始点
		InThreading(root); //从根节点开始线索化
		pre->RTag = THREAD; //处理线索化的最后一个节点
		pre->rchild = start;
		start->rchild = pre;
	}
}
//////////////////////////////////////////中序线索化递归部分
void BiTree_Thread::InThreading(BitNode *&p)
{
	if (p) //若节点存在
	{
		InThreading(p->lchild); //线索化其左子树
		if (p->lchild == NULL) //处理p指向的节点的前驱
		{
			p->LTag = THREAD;
			p->lchild = pre;
		}
		if (pre->rchild == NULL) //处理pre指向的节点的后继
		{
			pre->RTag = THREAD;
			pre->rchild = p;
		}
		pre = p; //pre紧跟p
		InThreading(p->rchild); //线索化其右子树
	}
}
/////////////////////////////////////////移除二叉树主调函数
void BiTree_Thread::ReMove()
{
	if (root != NULL) //如果树不空
	{
		ReMoveBiTree(root); //移除整棵树
		if (start != NULL) //如果已经被线索化
		{
			delete start; //删除start节点
			start = NULL; //置start为NULL
		}
		root = NULL; //置root为NULL
	}
}
////////////////////////////////////////////移除二叉树被调函数
void BiTree_Thread::ReMoveBiTree(BitNode *&t)
{
	if (t != NULL) //此条件用于未线索化的二叉树
	{
		if (t->LTag != THREAD) //此条件用于线索化的二叉树
			ReMoveBiTree(t->lchild); //递归移除其左子树
		if (t->RTag != THREAD) //此条件用于线索化的二叉树
			ReMoveBiTree(t->rchild); //递归移除其右子树
		delete t; //删除节点
	}
}

main.cpp

#include<iostream>
#include"head.h"
using namespace std;

int main()
{
	BiTree_Thread t;
	char choice;
	while (1)
	{
		cout << "Your Choice , Please ?" << endl << endl
				<< "1 . PreOrderCreatBiTree" << endl
				<< "2 . InOrderTraverse_Thread" << endl << "9 . Quit" << endl
				<< endl;
		cin >> choice;
		switch (choice)
		{
		case '1':
			t.PreOrderCreatBiTree();
			break;
		case '2':
			t.InOrderTraverse_Thread();
			break;
		case '9':
			return 0;
			break;
		default:
			cout << "No Such Choice !" << endl << endl;
			break;
		}
	}
	return 0;
}