threadtree.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#ifndef THREADTREE
#define THREADTREE
#define eptmark '@'
template <class T>
struct ThreadNode {	      //线索二叉树的结点类
     int ltag, rtag;		      //线索标志
     ThreadNode<T> *leftChild, *rightChild;		
                                               //线索或子女指针
     T data;			      //结点数据
     ThreadNode ( const T item)             //构造函数
          : data(item), leftChild (NULL),
            rightChild (NULL), ltag(0), rtag(0) {}	
};
template <class T>
class ThreadTree {			//线索化二叉树类
protected:
     ThreadNode<T> *root;	//树的根指针
     void createInThread (ThreadNode<T> *current,  
            ThreadNode<T> *& pre);
	    //中序遍历建立线索二叉树
     ThreadNode<T> *parent (ThreadNode<T> *t);	 
        //寻找结点t的双亲结点
public:
     ThreadTree () : root (NULL) { }	//构造函数
	 void InitThreadTree();
	 void createInThread();        //建立中序线索二叉树
     ThreadNode<T> *First (ThreadNode<T> *current);
		//寻找中序下第一个结点
     ThreadNode<T> *Last (ThreadNode<T> *current);
		//寻找中序下最后一个结点
	  ThreadNode<T> *Next (ThreadNode<T> *current);
		//寻找结点在中序下的后继结点
	  ThreadNode<T> *Prior (ThreadNode<T> *current);
		//寻找结点在中序下的前驱结点
	  void InOrder (void (*visit) (ThreadNode<T> *t));
	  //线索化二叉树的中序遍历
	  void PreOrder (void (*visit) (ThreadNode<T> *t));
	  //线索化二叉树的前序遍历
	  void PostOrder (void (*visit) (ThreadNode<T> *t));
	  //线索化二叉树的后序遍历
	 
	  bool Find (T value);
	  //在二叉树中找value,成功返true,并置current为此结点;否则返false
	  ThreadNode<T>* & getCurrent ()  { return current; }
	  //返回current
private:
	ThreadNode<T> *current;
	bool Find (ThreadNode<T> *p, T value);			//在以p为根的树中搜索value
	bool setRoot(const T& rt) {
		 root = new ThreadNode<T>(rt);
		 if(root) return true;
		 else return false;
	 } //设置根值为rt

    
	 static ThreadNode<T>* &leftChild (ThreadNode<T> *t)
       { return t->leftChild; }                                                        //返回首子女
     static ThreadNode<T>* &rightChild (ThreadNode<T> *t)
       { return t->rightChild; }                //返回下一兄弟
	 bool MakeLink(const T ex, const T ap, char linkmark); 
	 void show(ThreadNode<T>* &p, int i);
	 
};

template<class T>
bool ThreadTree<T>::MakeLink(const T ex, const T ap, char linkmark) {
	if(linkmark != eptmark) {
		//结束标志
		ThreadNode<T> *p = new ThreadNode<T>(ap);//将ap转化为结点
		if(Find(ex))//找ex,置为current
		{}
		if(current) {
			switch(linkmark) {
                case 'l': current -> leftChild = p; 
					cout<<"输入成功"<<endl;break;//建立“首子女”关系
                case 'r': current -> rightChild = p; 
					cout<<"输入成功"<<endl;break;//建立“下一兄弟”关系
				default: cout << "错误，请重新输入" << endl;
			}
			return false;
		}
		else {
			cout << "错误，请重新输入" << endl;
			return false;
		}
	}
	else return true;//结束条件
}


template<class T> 
bool ThreadTree<T>::Find(T value) {
	if(!root) return 0;
	else return Find(root, value);
}

template<class T>
bool ThreadTree<T>::Find(ThreadNode<T> *p, T value) {
	if(p)
		if(p ->data == value) {current = p;return true; }
		else return Find(p->leftChild,value) || Find(p->rightChild, value);
	else return false;
}

template<class T>
void ThreadTree<T>::InitThreadTree(){
	cout << "输入根结点：" << endl;//输入根结点
	char elem1, elem2, elem3;
	cin >> elem1;
	while(1){
		if(setRoot(elem1)) {
			cout << "输入成功" << endl;
			break;
		}
		else cout << "出错，请重新输入"  << endl;
	}
	cout << "输入结点关系，如 (Parent) (leftChild) l 或 (Parent) (rightChild) r" << endl;
	//输入除根外的所有结点，要求elem1为已加入的结点
	//elem2为新建结点，且二者或为首子女关系，或为下一兄弟关系
	while(1){
        cin >> elem1 >> elem2 >> elem3;//按格式输入
		
		if(MakeLink(elem1, elem2, elem3)) 
		{
			cout << "输入成功" << endl;
		break;//建立关联
		}
	}
	cout << "生成的树为：" << endl;
	show(root,0);
	return;
}

template<class T>
void ThreadTree<T>::show(ThreadNode<T>* &p, int i) {
	//i为制表符计数
	if(p) {
		for(int j = 0; j < i; ++j) cout << '\t';
		cout << p->data << endl;
	    //输出当前结点
		if(ThreadTree<T>::leftChild(p) || ThreadTree<T>::rightChild(p)){
			//到树叶终止
			++i;
			show(ThreadTree<T>::leftChild(p), i);//递归输出首子女树
			show(ThreadTree<T>::rightChild(p), i);//递归输出下一兄弟树
		}
	}
	return;
}
#endif