tree.cpp

数据结构实验课中的所有实验程序

// Tree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "tree.h"


template <class Type> class Tree{

	public: Tree() {root=current=NULL;}
            void BuildRoot(Type rootVal);
			int FirstChild();
            int Root();
			int NextSibling();
            int Parent();
			void InsertChild(Type value);
			int FindParent(TreeNode<Type>*t,TreeNode<Type> *p);
		    int Find(Type target);
			int RemoveChild(int i);
			void RemovesubTree();
			void NorecPreOrder();
			void PreOrder();
            void LevelOrder();
	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>::FirstChild()
{if(current !=NULL && current->firstChild!=NULL)
{current = current->firstChild;return 1;}
current = NULL;return 0;}

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>::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)
{if((int i=FindParent(TreeNode<Type>*q,*p))!=0) return i;
q=q->nextSibling;
}
if(q!=NULL&&q==p){current=t;return 1;}
else return 0;

}
template<class Type>int Tree<Type>::Find(TreeNode<Type> *p,Type target)
{int result=o;
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>int Tree<Type>::Find(Type target){
  if(IsEmpty()) return 0;
  return Find(root,target);
}



template<class Type>void Tree<Type>::InsertChild(Type value)
{TreeNode<Type> * newNode=new TreeNode <Type>(value);
if(current->firstChild==NULL) current->firstChild=newChild=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){
	   current->firstChild;
      if(s!=NULL) current->firstChild=s->nextSibling;
   else return 0;}
   else {TreeNode<Type> *q=current->firstChild; int k=l;
   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->nextSibling,*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>::NorecPreOrder(){
 Stack<TreeNode<Type>*>st(20);
  TreeNode<Type>*p=current;
  do{while(current!=NULL){visit();st.Push(current);
  FirstChild();}
  while(current==NULL&&!st.IsEmpty()){current=st.Pop();NextSibling();}
  
  }while(current!=NULL);
   current=p;}

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


int main(int argc, char* argv[])
{
	return 0;
}