tree.h

数据结构中 树的基本操作 可完成遍历 查找 删除子女 子树的功能

#include<stack.h>
#include<queue.h>
#define DefaultSize 20


template <class Type> class Tree;

template <class Type> class TreeNode {
	friend class Tree<Type>;
  private:
	  Type data;
	  TreeNode<Type> *firstChild, *nextSibling;
	  TreeNode ( Type value=0, TreeNode<Type> *fc=NULL, TreeNode<Type> *ns=NULL ):data (value), firstChild (fc), nextSibling (ns) { }
};


template <class Type> class Tree {
  public:
	  Tree ( ) { root = current = NULL; }
	  void BuildRoot(Type rootVal);
	  int  Root();
	  int  FirstChild();
	  int  NextSibling();
	  int  Parent();
	  int  Find(Type target);
	  void InsertChild(Type value);
	  int  RemoveChild(int i);
	  void RemovesubTree();
	  void PreOrder();
	  void NorecPreOrder();
	  void PostOrder();
	  void PostOrder1();
	  void LevelOrder();
	  int  IsEmpty();
	  void visit();
	 
  private:
	  TreeNode<Type> *root, *current;
	  void PreOrder ( ostream & out, TreeNode<Type> *p );
	  int Find ( TreeNode<Type> *p, Type target );
	  void RemovesubTree ( TreeNode<Type> *p );
	  int FindParent ( TreeNode<Type> *t, TreeNode<Type> *p );
};


template <class Type> void Tree<Type>::BuildRoot ( Type rootVal ) {
    root = current = new TreeNode<Type> (rootVal);
}

template <class Type> int Tree<Type>:: Root ( ) {
    if ( root == NULL ) {
		current = NULL;
		return 0;
	}
	else {
		current = root;
		return 1;
	}
}

template <class Type> int Tree<Type>::FirstChild ( ) {
    if ( current != NULL && current->firstChild != NULL ) {
		current = current->firstChild;  return 1;
	}
    current = NULL;
    return 0;
}

template <class Type> int Tree<Type>::NextSibling ( ) {
    if ( current != NULL && current->nextSibling != NULL ) {
		current = current->nextSibling;
		return 1;
	}
    current = NULL;  return 0;
}

template <class Type> int Tree<Type>::Parent ( ) {
    TreeNode<Type> *p = current,  *t;
    if ( current == NULL || current == root ) { current = NULL;  return 0; }
    t = root;
    int k = FindParent ( t, p );
    return k;
}

template <class Type> int Tree<Type>::FindParent ( TreeNode<Type> * t,TreeNode<Type> * p ){
    TreeNode<Type> *q = t->firstChild;
    while ( q != NULL && q != p ) {
		int i=FindParent(q,p);
		if( i )  return i;
		q = q->nextSibling;
	}
    if ( q != NULL && q ==p ) { current = t;  return 1; }
	return 0;
}

template <class Type> int Tree<Type>::Find ( Type target ) {
    if ( IsEmpty ( ) ) return 0;
    return Find ( root, target );
}

template <class Type> int Tree<Type>::Find ( TreeNode<Type> *p, Type target ) {
    int result = 0;
    if ( p->data == target ) { result = 1;  current = p; }
	else {
		TreeNode<Type> *q = p->firstChild;
		while ( q != NULL && ! ( result = Find ( q, target ) ) ) q = q->nextSibling;
	}
	return result;
}

template <class Type> void Tree<Type>::InsertChild ( Type value ) {
    TreeNode<Type> *newNode = new TreeNode<Type> (value);
    if ( current->firstChild == NULL ) current->firstChild = newNode;
	else {
		TreeNode<Type> *p = current->firstChild;
		while ( p->nextSibling != NULL ) p = p->nextSibling;
		p->nextSibling = newNode;
	}
}

template <class Type> int Tree<Type>::RemoveChild ( int i ) {
    TreeNode<Type> * s;
    if ( i == 1 ) {
		s = current->firstChild;
		if ( s != NULL ) current->firstChild = s->nextSibling;
		else return 0;
	}
	else {
		TreeNode<Type> *q = current->firstChild;  int k = 1;
		while ( q != NULL && k < i-1 ) { q = q->nextSibling;  k++; }
		if ( q != NULL ) {
			s = q->nextSibling;
			if ( s != NULL )q->nextSibling = s->nextSibling;
			else return 0;
		}
		else return 0;
	}
    RemovesubTree(s);
    return 1;
}

template <class Type> void Tree<Type>::RemovesubTree ( TreeNode<Type> *p ) {
    TreeNode<Type> *q = p->firstChild,  *next;				
    while ( q != NULL ) {
		next = q->nextSibling;
		RemovesubTree ( q );  q = next;
	}
    delete p;
}

template <class Type> void Tree<Type>::RemovesubTree ( ) {
    if ( current != NULL ) {
		if ( current == root ) root = NULL;
		RemovesubTree ( current );  current = NULL;
	}
}

template <class Type> void Tree<Type>::PreOrder ( ) {
    if ( !IsEmpty ( ) ) {
		visit ( );
		TreeNode<Type> *p = current;
		int i = FirstChild ( );
		while (i) { PreOrder ( );  i = NextSibling ( ); }
		current = p;
	}
}

template <class Type> void Tree<Type>::PostOrder ( ) {
    if ( !IsEmpty ( ) ) {
		TreeNode<Type> *p = current;
		int i = FirstChild ( );
		while (i) {
			PostOrder ( );
			i = NextSibling ( );
		}
		current = p;
		visit ( );
	}
}

template <class Type> void Tree<Type>::NorecPreOrder( ) {
    Stack<TreeNode<Type>*> st;
    TreeNode<Type> *p = current;
    do {
		while ( !IsEmpty ( ) ) {
			visit ( );
			st.Push ( current );
			FirstChild ( );
		}
		while ( IsEmpty ( ) && !st.IsEmpty ( ) ) {
			current = st.Pop ( );
			NextSibling ( );
		}
	} while ( !IsEmpty ( ) );
    current = p;
}

template <class Type> void Tree<Type>::PostOrder1 ( ) {
    Stack<TreeNode<Type>* > st(DefaultSize);
    TreeNode<Type> *p = current;
    do {
		while ( !IsEmpty ( ) ) {
			st.Push(current);
			FirstChild ( );
		}
		while ( IsEmpty ( ) && !st.IsEmpty ( ) ) {
			current = st.Pop ( );
			visit ( );
			NextSibling ( );
		}
	} while ( !IsEmpty ( ) );
    current = p;
}

template <class Type> void Tree<Type>::LevelOrder ( ) {
    Queue<TreeNode<Type> * > Qu ;
    if ( ! IsEmpty ( ) ) {
		TreeNode<Type> *p = current;  Qu.EnQueue ( current );
		while ( !Qu.IsEmpty ( ) ) {
			current = Qu.DeQueue ( );
			visit ( );
			FirstChild ( );
			while ( !IsEmpty ( ) ) { Qu.EnQueue ( current );  NextSibling ( ); }
		}
		current = p;
    }
}
template<class Type> void Tree<Type>::visit(){
    cout<<current->data<<endl;
}

template<class Type> int Tree<Type>::IsEmpty(){
    return current==NULL;
}