binarytree.h

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

#ifndef BINARYThreadTree_H
#define BINARYThreadTree_H
template <class T>
struct ThreadTreeNode {			//树的结点类
	T data;				//结点数据
     ThreadTreeNode<T> *leftChild, *rightChild;
 		                                         //子女及兄弟指针
    ThreadTreeNode (T value = 0, ThreadTreeNode<T> *fc = NULL,   ThreadTreeNode<T> *ns = NULL)     //构造函数
	    : data (value), leftChild (fc), rightChild (ns) { }
};

template <class T>
class ThreadTree {			//树类
private:
     ThreadTreeNode<T> *root, *current;				//根指针及当前指针
     bool Find (ThreadTreeNode<T> *p, T value);			//在以p为根的树中搜索value
public:
     ThreadTree () { root = current = NULL; }	//构造函数
     bool Find (T value);
	     //搜索含value的结点, 使之成为当前结点
	 bool setRoot(const T& rt) {
		 root = new ThreadTreeNode<T>(rt);
		 if(root) return true;
		 else return false;
	 } //设置根值为rt
	 ThreadTreeNode<T>* & getRoot ()  { return root; }
	 ThreadTreeNode<T>* & getCurrent ()  { return current; }
	 static ThreadTreeNode<T>* &leftChild (ThreadTreeNode<T> *t)
       { return t->leftChild; }
                                                          //返回首子女
     static ThreadTreeNode<T>* &rightChild (ThreadTreeNode<T> *t)
       { return t->rightChild; }                //返回下一兄弟
	 bool MakeLink(const T ex, const T ap, char linkmark); 
};

template<class T>
bool ThreadTree<T>::MakeLink(const T ex, const T ap, char linkmark) {
	if(linkmark != eptmark) {
		//结束标志
		ThreadTreeNode<T> *p = new ThreadTreeNode<T>(ap);//将ap转化为结点
		Find(ex);//找ex,置为current
		if(current) {
			switch(linkmark) {
                case 'c': current -> leftChild = p; 
					break;//建立“首子女”关系
                case 's': current -> rightChild = p; 
					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(ThreadTreeNode<T> *p, T value) {
	bool result = 0;
	if(p ->data == value) {result = 1; current = p;}
	//result == 1代表成功
	else {
		ThreadTreeNode<T> *q = p ->leftChild;
		while(q != NULL && !(result = Find(q, value))) q = q->rightChild;
		//递归搜首子女数未果后递归搜下一兄弟树
	}
	return result;
}

#endif