tree.h

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

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

template <class T>
class Tree {			//树类
private:
     TreeNode<T> *root, *current;				//根指针及当前指针
     bool Find (TreeNode<T> *p, T value);			//在以p为根的树中搜索value
     void RemovesubTree (TreeNode<T> *p);		//删除以p为根的子树
     bool FindParent (TreeNode<T> *t, 
          TreeNode<T> *p);
public:
     Tree () { root = current = NULL; }	//构造函数
	 Tree (TreeNode<T>* r, TreeNode<T>* c): root(r), current(c){}
	 void show(void (*visit) (TreeNode<T> *t)) {
		 cout << "树：" << endl;
		 cout << "根为：";
		 if(root) visit(root);
		 cout << endl;
		 cout << "当前结点：";
		 if(current) visit(current);
		 cout << endl;
	 }
     bool Root ();	           //置根结点为当前结点
     bool IsEmpty () { return root == NULL; }
     bool FirstChild ();
	     //将当前结点的第一个子女置为当前结点
	 bool NextSibling ();
	     //将当前结点的下一个兄弟置为当前结点
     bool Parent ();
         //将当前结点的双亲置为当前结点
     bool Find (T value);
	     //搜索含value的结点, 使之成为当前结点
         //树的其他公共操作
	 void PreOrder ( void (*visit) (TreeNode<T> *t) ); 
		 //以当前指针current为根, 先根次序遍历
	 void PostOrder (void (*visit) (TreeNode<T> *t)); 
		 //以当前指针current为根, 按后根次序遍历树
	 void LevelOrder(void (*visit) (TreeNode<T> *t) );
	 //按广度优先次序分层遍历树, 树的根结点是当前指针current
};

template <class T> 
bool Tree<T>::Root () {
//让树的根结点成为树的当前结点
     if (root == NULL) {
          current = NULL;  return false;
     }
     else {
         current = root;  return true;
     }
};
template <class T> 
bool Tree<T>::Parent () {
//置当前结点的双亲结点为当前结点
     TreeNode<T> *p = current;
     if (current == NULL || current == root) 
        { current = NULL;  return false; }     
           //空树或根无双亲
     return FindParent (root, p);					//从根开始找*p的双亲结点
};
template <class T>
bool Tree<T>::
FindParent (TreeNode<T> *t, TreeNode<T> *p) {
//在根为*t的树中找*p的双亲, 并置为当前结点
     TreeNode<T> *q = t->firstChild;     //*q是*t长子
     bool succ;
     while (q != NULL && q != p) {	  //扫描兄弟链
          if ((succ = FindParent (q, p)) == true) 
               return succ;	//递归搜索以*q为根的子树
          q = q->nextSibling;
     }
     if (q != NULL && q == p) {
          current = t;  return true;
     }
     else { current = NULL;  return false; }   //未找到
};

template <class T> 
bool Tree<T>::FirstChild () {
//在树中找当前结点的长子, 并置为当前结点
     if (current && current->firstChild )
         { current = current->firstChild;  return true; }
	 current = NULL;  return false;
};

template <class T> 
bool Tree<T>::NextSibling () {
//在树中找当前结点的兄弟, 并置为当前结点
     if (current && current->nextSibling) {
          current = current->nextSibling;
          return true;
     }
     current = NULL;  return false;
};
template <class T> 
void Tree<T>::
PreOrder ( void (*visit) (TreeNode<T> *t) ) {	
//以当前指针current为根, 先根次序遍历
     if (!IsEmpty ()) {         	//树非空
          visit (current);		//访问根结点
          TreeNode<T> *p = current;     //暂存当前指针
          current = current->firstChild;  //第一棵子树
          while (current != NULL) { 
               PreOrder (visit);	//递归先根遍历子树
               current = current->nextSibling;
          }
          current = p;			//恢复当前指针
     }
};

template <class T>
void Tree<T> :: 
PostOrder (void (*visit) (TreeNode<T> *t)) {
//以当前指针current为根, 按后根次序遍历树
	     if ( ! IsEmpty () ) {                         //树非空
          TreeNode<T> *p = current;     //保存当前指针
          current = current->firstChild;   //第一棵子树 
          while (current != NULL) {        //逐棵子树	
               PostOrder (visit);
               current = current->nextSibling;
          }
          current = p;                                //恢复当前指针
          visit (current);                            //访问根结点
     }
};

template <class T> 
void Tree<T>::
LevelOrder(void (*visit) (TreeNode<T> *t) ) {
//按广度优先次序分层遍历树, 树的根结点是
//当前指针current。   
     Queue<TreeNode<T>*> Q;
     TreeNode<T> *p;
     if (current != NULL) { 	      //树不空 
          p = current;                             //保存当前指针
          Q.EnQueue (current);             //根结点进队列
          while (!Q.IsEmpty ()) {
               Q.DeQueue (current);        //退出队列
               visit (current);                    //访问之
			   current = current->firstChild;
			   while (current != NULL) { 
				   Q.EnQueue (current);
				   current = current->nextSibling;
			   }
			   current = p;	  //恢复算法开始的当前指针
		  }
	 }
};

template <class T> 
bool Tree<T>::Find(T value) {
	if (IsEmpty()) return false;
	return Find(root, value);
};

template <class T> 
bool Tree<T>::Find(TreeNode <T> *p, T value) {
//在根为 *p 的树中找值为value的结点, 找到后该结点成为当前结点, 否则当前结点不变。
//函数返回成功标志：=true, 成功; =false, 失败
	bool result = false;
	if (p->data == value) {result = true;  current = p;}	//搜索成功
	else {													//搜索失败
		TreeNode<T> *q = p->firstChild;
		while (q != NULL && !(result = Find(q, value))) 
			q = q->nextSibling;}
	return result;
};

template<class T> 
void Tree<T>::RemovesubTree(TreeNode<T> *p) {
	//私有函数: 若指针subTree不为空, 则删除根为subTree的子树
	if (subTree != NULL) {
		RemovesubTree(subTree->firstChild); 		//递归删除subTree的左子树
 	    RemovesubTree(subTree->nextSibling); 		//递归删除subTree的右子树
 	    delete subTree; 					//递归subTree
	}
};


#endif