tree.h

是一个在学习数据结构时编写的图结构

#include<iostream>
using namespace std;
template <class T, class E >
class TreeNode {
public:
	TreeNode(){}
	TreeNode (T x) {key = x; }	    //构造函数
	T getKey() const { return key; }	    //读取关键码
	void setKey (T x) { key = x; }	    //修改关键码

	//子女及兄弟指针
	void setFirstChild(TreeNode<T,E> *&p);
	void setNextSibling(TreeNode<T,E> *&q);
	TreeNode<T,E> *getFirstChild()
	{return firstChild;}
	TreeNode<T,E> *getNextSibling()
	{return nextSibling;}
	TreeNode<T,E> operator = (TreeNode<T,E> node){key = node.key;other = node.other;return this;}
private:
	T key;			//关键码域  
	E other;		          //其他域（视问题而定）
	TreeNode<T,E> *firstChild, *nextSibling;

};
template<class T,class E>
void TreeNode<T,E>::setFirstChild(TreeNode<T,E> *&p)
{
	firstChild = p;

}
template<class T,class E>
void TreeNode<T,E>::setNextSibling(TreeNode<T,E> *&q)
{
	nextSibling = q;
}

template <class T,class E>
class Tree {			//树类
private:
	TreeNode<T,E> *root, *current;				//根指针及当前指针
	int Find (TreeNode<T,E> *p, T value);			//在以*p为根的树中搜索value
	void RemovesubTree (TreeNode<T,E> *p);		//删除以*p为根的子树
	bool FindParent (TreeNode<T,E> *t, TreeNode<T,E> *p); 
	//在以*t为根的树中找*p的双亲
public:
	Tree () { root= NULL;  current = NULL; }	//构造函数
	void SetRoot(TreeNode<T,E>* p);
	TreeNode<T,E> *GetRoot();
	bool Root ();	           //置根结点为当前结点
	void PrintTree(TreeNode<T,E>* t);
	bool IsEmpty () { return root == NULL; }
	bool FirstChild ();
	//将当前结点的第一个子女置为当前结点
	bool NextSibling ();
	//将当前结点的下一个兄弟置为当前结点
	bool Parent ();
	//将当前结点的双亲置为当前结点
	bool Find (T value);
	//搜索含value的结点, 使之成为当前结点
	TreeNode<T,E>* create_tree(TreeNode<T,E> *t);
	void SetDepthToNode(TreeNode<T,E> *t);
	void show_tree(TreeNode<T,E> *t);
};

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

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

template <class T,class E> 
bool Tree<T,E>::NextSibling () {
//在树中找当前结点的兄弟, 并置为当前结点
     if (current != NULL && current->nextSibling != NULL ) {
          current = current->nextSibling;
          return true;
     }
     current = NULL;  return false;
};
template<class T,class E>
TreeNode<T,E> *Tree<T,E>::GetRoot()
{
	return root;
}
template<class T,class E>
TreeNode<T,E>* Tree<T,E>::create_tree(TreeNode<T,E> *t)
{
}
template<class T,class E>
void Tree<T,E>::SetDepthToNode(TreeNode<T,E> *t)
{
	int d = find_depth(t);
	t->depth = d;
}
	
template<class T,class E>
void Tree<T,E>::show_tree(TreeNode<T,E> *t){
	if(t != NULL)
	{
		cout << '(';
		cout << t->getKey();
		for(TreeNode<T,E> *p = t ->getFirstChild();p!= NULL;p = p->getNextSibling())
		show_tree(p);
		cout << ')';
	}
}