#include 
     
      #include"queue.h"//之前写的类 #include"stack.h" //之前写的类 using namespace std;/*	用二叉树的方式实现	root指针指向第一棵树的根节点 */  template 
      
       class Forest;//========================================// 森林节点类声明template 
       
        class ForestNode{ private:    ForestNode
        
           *firstChild,*nextBrother;	//指向大孩子结点的指针和指向大兄弟结点的指针     T data;//数据public:	friend class Forest
         
          ;      //构造函数    ForestNode(const T& item,ForestNode *lptr=NULL,ForestNode *rptr=NULL):        data(item),firstChild(lptr),nextBrother(rptr){}            ForestNode(){}    ForestNode
          
            * GetFirstChild()const{return firstChild;}//返回大儿子节点 void SetFirstChild(ForestNode
           
             * L){firstChild=L;}//设置大儿子结点 ForestNode
            
              * GetNextBrother()const{return nextBrother;}//返回大兄弟节点 void SetNextBrother(ForestNode
             
               * R){nextBrother=R;}//设置大兄弟节点 T GetData(){return data;} void SetData(T item){data=item;}};//===============================================================// 森林类的声明template 
              
               class Forest{private: ForestNode
               
                 *root;//虚根结点的声明 int number;//树数 public: Forest(ForestNode
                
                 *t=NULL):root(t){}//构造函数 virtual ~Forest(){Del(root);}//析构函数 删除整个森林 //在以节点t为根节点的森林中查找data域为item的结点 ForestNode
                 
                   *Find(ForestNode
                  
                    *t,const T&item)const; ForestNode
                   
                    * CreateNewTree(); //森林中增加一棵树 ForestNode
                    
                     * CreateTree(); //创建树 ForestNode
                     
                      * GetTree(int n);//获得森林中的第n棵数 //删除节点t及其子森林 void Del(ForestNode
                      
                        *t); //先根遍历并输出以节点t为根节点的子森林 void PreOrder( ForestNode
                       
                         *t)const; //后根遍历并输出以节点t为根节点的子森林 void PostOrder(ForestNode
                        
                          *t)const; //非递归先根遍历并输出以节点t为根节点的子森林 void NorePreOrder(ForestNode
                         
                           *t)const; //非递归后根遍历并输出以节点t为根节点的子森林 void NorePostOrder(ForestNode
                          
                            *t)const; //递归层次遍历并输出以节点t为根节点的子森林 void LevelOrder(ForestNode
                           
                             *t)const; //创建森林 ForestNode
                            
                             * CreateForest(); //其它操作 ForestNode
                             
                              * GetRoot(){return root;} void SetRoot(ForestNode
                              
                                * t){root=t;} bool IsEmpty(){return root==NULL;} void output();};template 
                               
                                void Forest
                                
                                 ::output(){ cout<<" 森林的先根遍历的序列为："; PreOrder(GetRoot()); cout<
                                 
                                  
                                   ForestNode
                                   
                                    * Forest
                                    
                                     ::Find(ForestNode
                                     
                                       *t,const T&item)const{ ForestNode
                                      
                                        * p; //递归出口 if(t==NULL)return NULL; if(t->GetData()==item) return t; //递归 p=Find(t->GetFirstChild(),item); if(p!=NULL) return p; p=Find(t->GetNextBrother(),item); if(p!=NULL) return p; return NULL;}//======================================//创建森林 template 
                                       
                                        ForestNode
                                        
                                         * Forest
                                         
                                          ::CreateForest() { ForestNode
                                          
                                           *p,*t; cout<<"森林中树的数量:"; cin>>number; int i=1; if(number!=0) { cout<<"创建第"<
                                           <<"棵树"<
                                            
                                             SetNextBrother(p); t=p; i++; } } return root;}template 
                                             
                                              ForestNode
                                              
                                               * Forest
                                               
                                                ::CreateTree() { cout<<"输入节点的值"; ForestNode
                                                
                                                 * currptr; T data; cin>>data; currptr=new ForestNode
                                                 
                                                  (data,NULL,NULL); cout<<"输入该结点的子树数"; int n; cin>>n; int i=1; if(n!=0) { cout<<"创建"<
                                                  <<"的第1棵子树"<
                                                   
                                                    * temp1 = CreateTree(); currptr->SetFirstChild(temp1); i++; while(i<=n) { cout<<"创建"<
                                                    <<"的第"<<<"棵子树"<
                                                      
                                                       * temp2=CreateTree(); temp1->SetNextBrother(temp2); temp1=temp2; temp2=NULL; i++; } } return currptr;}template 
                                                       
                                                        ForestNode
                                                        
                                                         * Forest
                                                         
                                                          ::CreateNewTree()//在森林中增加一棵树 { ForestNode
                                                          
                                                           * p=CreateTree(); ForestNode
                                                           
                                                            * t=root; while(t->GetNextBrother()!=NULL) t=t->GetNextBrother(); t->SetNextBrother(p); return p;} template 
                                                            
                                                             ForestNode
                                                             
                                                              * Forest
                                                              
                                                               ::GetTree(int k)//返回第k棵树 { if(k>number&&k<1) return NULL;//越界 int i=1; ForestNode
                                                               
                                                                *t=root; while(i!=k) { t=t->GetNextBrother(); i++; } return t; }//=============================================================//先序遍历森林 template 
                                                                
                                                                 void Forest
                                                                 
                                                                  ::PreOrder( ForestNode
                                                                  
                                                                   * t) const { if(t == NULL) { return; } cout<
                                                                   
                                                                    GetData()<<" "; PreOrder(t->GetFirstChild()); PreOrder(t->GetNextBrother());}template 
                                                                    
                                                                     void Forest
                                                                     
                                                                      ::NorePreOrder(ForestNode
                                                                      
                                                                       * t) const{ LStack
                                                                       
                                                                        
                                                                         *> q; if(t!=NULL) { q.Push(t); } ForestNode
                                                                         
                                                                           *node; while(!q.IsEmpty()) { q.Pop(node); cout<
                                                                          
                                                                           GetData()<<" "; if(node->GetFirstChild() != NULL) { q.Push(node->GetFirstChild()); } if(node->GetNextBrother() != NULL) { q.Push(node->GetNextBrother()); } }}//=========================================//后序遍历森林 template 
                                                                           
                                                                            void Forest
                                                                            
                                                                             ::PostOrder( ForestNode
                                                                             
                                                                              * t) const { if(t == NULL) { return; } PostOrder(t->GetFirstChild()); cout<
                                                                              
                                                                               GetData()<<" "; PostOrder(t->GetNextBrother());}template 
                                                                               
                                                                                void Forest
                                                                                
                                                                                 ::NorePostOrder(ForestNode
                                                                                 
                                                                                  * t) const{ LStack
                                                                                  
                                                                                   
                                                                                    *> q; if(t!=NULL) { q.Push(t); } ForestNode
                                                                                    
                                                                                      *node; while(!q.IsEmpty()) { q.Pop(node); if(node->GetFirstChild() != NULL) { q.Push(node->GetFirstChild()); } cout<
                                                                                     
                                                                                      GetData()<<" "; if(node->GetNextBrother() != NULL) { q.Push(node->GetNextBrother()); } }}//======================================//层次遍历 template 
                                                                                      
                                                                                       void Forest
                                                                                       
                                                                                        ::LevelOrder(ForestNode
                                                                                        
                                                                                         * t) const{ LQueue
                                                                                         
                                                                                          
                                                                                           *> q; ForestNode
                                                                                           
                                                                                            *s=NULL; //所有firstchild都入队，brother立即访问 if(t!=NULL) { q.QInsert(t); } ForestNode
                                                                                            
                                                                                              *node; while(s!=NULL||!q.IsEmpty()) { while(s!=NULL) { node=s; s=NULL; cout<
                                                                                             
                                                                                              GetData()<<" "; if(node->GetFirstChild() != NULL) { q.QInsert(node->GetFirstChild()); } if(node->GetNextBrother() != NULL) { s=node->GetNextBrother(); } } if(!q.IsEmpty()) { q.QDelete(node); cout<
                                                                                              
                                                                                               GetData()<<" "; if(node->GetFirstChild() != NULL) { q.QInsert(node->GetFirstChild()); } if(node->GetNextBrother() != NULL) { s=node->GetNextBrother(); } } }} //========================================//删除森林 template 
                                                                                               
                                                                                                void Forest
                                                                                                
                                                                                                 ::Del(ForestNode
                                                                                                 
                                                                                                   *t){ if(t != NULL) { Del(t->GetFirstChild()); Del(t->GetNextBrother()); delete t; }}
                                                                                                 
                                                                                                
                                                                                               
                                                                                              
                                                                                             
                                                                                            
                                                                                           
                                                                                          
                                                                                         
                                                                                        
                                                                                       
                                                                                      
                                                                                     
                                                                                    
                                                                                   
                                                                                  
                                                                                 
                                                                                
                                                                               
                                                                              
                                                                             
                                                                            
                                                                           
                                                                          
                                                                         
                                                                        
                                                                       
                                                                      
                                                                     
                                                                    
                                                                   
                                                                  
                                                                 
                                                                
                                                               
                                                              
                                                             
                                                            
                                                           
                                                          
                                                         
                                                        
                                                       
                                                      
                                                   
                                                 
                                                
                                               
                                              
                                             
                                            
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

　

#include 
     
      #include"queue.h" #include"stack.h"  using namespace std;template 
      
       class Tree;//========================================// 树节点类声明template 
       
        class TreeNode{ private:    TreeNode
        
           *firstChild,*nextBrother;	//指向大孩子结点的指针和指向大兄弟结点的指针     T data;//数据public:	friend class Tree
         
          ;      //构造函数    TreeNode(const T& item,TreeNode *lptr=NULL,TreeNode *rptr=NULL):        data(item),firstChild(lptr),nextBrother(rptr){}    TreeNode
          
            * GetFirstChild()const{return firstChild;}//返回大儿子节点 void SetFirstChild(TreeNode
           
             * L){firstChild=L;}//设置大儿子结点 TreeNode
            
              * GetNextBrother()const{return nextBrother;}//返回大兄弟节点 void SetNextBrother(TreeNode
             
               * R){nextBrother=R;}//设置大兄弟节点 T GetData(){return data;} void SetData(T item){data=item;}};//===============================================================// 树类的声明template 
              
               class Tree{private: TreeNode
               
                 *root;//根结点的声明 T stop; public: Tree(TreeNode
                
                 *t=NULL):root(t),stop('*'){}//构造函数 virtual ~Tree(){Del(root);}//析构函数 删除整棵 树 //在以节点t为根节点的子树中查找data域为item的结点 TreeNode
                 
                   *Find(TreeNode
                  
                    *t,const T&item)const; //在以节点t为根节点的子树中搜索节点p的父节点 TreeNode
                   
                     * Father(TreeNode
                    
                      *t,TreeNode
                     
                       *p)const; //在以节点t为根节点的子树中删除节点t及其子树 void DelSubTree(TreeNode
                      
                       * t,TreeNode
                       
                         *p); //删除节点t及其子树 void Del(TreeNode
                        
                          *t); //先根遍历并输出以节点t为根节点的子树 void PreOrder( TreeNode
                         
                           *t)const; //后根遍历并输出以节点t为根节点的子树 void PostOrder(TreeNode
                          
                            *t)const; //非递归先根遍历并输出以节点t为根节点的子树 void NorePreOrder(TreeNode
                           
                             *t)const; //非递归后根遍历并输出以节点t为根节点的子树 void NorePostOrder(TreeNode
                            
                              *t)const; //非递归层次遍历并输出以节点t为根节点的子树 void NoreLevelOrder(TreeNode
                             
                               *t)const; //创建树 TreeNode
                              
                               * CreateTree(); //其它操作 TreeNode
                               
                                * GetRoot(){return root;} void SetRoot(TreeNode
                                
                                  * t){root=t;} bool IsEmpty(){return root==NULL;} void output();};template 
                                 
                                  void Tree
                                  
                                   ::output(){ cout<<" 树的先根遍历的序列为："; PreOrder(GetRoot()); cout<
                                   
                                    
                                     TreeNode
                                     
                                      * Tree
                                      
                                       ::Find(TreeNode
                                       
                                         *t,const T&item)const{ TreeNode
                                        
                                          * p; //递归出口 if(t==NULL)return NULL; if(t->GetData()==item) return t; //递归 p=Find(t->GetFirstChild(),item); if(p!=NULL) return p; p=Find(t->GetNextBrother(),item); if(p!=NULL) return p; return NULL;}//在以节点t为根节点的子树中搜索节点p的父结点template 
                                         
                                          TreeNode
                                          
                                           * Tree
                                           
                                            ::Father(TreeNode
                                            
                                             * t,TreeNode
                                             
                                              *p)const{ if(t==NULL||p==NULL)//若t，p中有一个为空 return NULL; if(p==root) return NULL; //若t是根结点则没有父节点 TreeNode
                                              
                                               *result=NULL; TreeNode
                                               
                                                *q=t->GetFirstChild();//从第一棵子树开始搜索 while(q!=NULL&&q!=p) { result=Father(q,p); if(!result) q=q->GetNextBrother(); else return result; } if(q==p) return t; return NULL;}//======================================//非递归创建树 template 
                                                
                                                 TreeNode
                                                 
                                                  * Tree
                                                  
                                                   ::CreateTree() { LQueue
                                                   
                                                    
                                                     *> Q; //处理根结点 //cout<<"输入根结点，并回车\n"; cout<<"输入根结点\n" ; T item; //item=getchar(); cin>>item; if(item==stop) return NULL; root=new TreeNode
                                                     
                                                      (item); Q.QInsert(root); TreeNode
                                                      
                                                       * node; TreeNode
                                                       
                                                        * child; while(!Q.IsEmpty()) { Q.QDelete(node); //getchar();//过滤回车 //cout<<"输入"<
                                                        
                                                         GetData()<<"的子节点( 用*结尾)，并回车\n"; //item=getchar(); cout<<"输入"<
                                                         
                                                          GetData()<<"的子节点\n"; cin>>item; while(item!=stop) { if(node->GetFirstChild()==NULL) { child=new TreeNode
                                                          
                                                           (item); node->SetFirstChild(child); Q.QInsert(child); //item=getchar(); } else { TreeNode
                                                           
                                                            *nextchild=new TreeNode
                                                            
                                                             (item); child->SetNextBrother(nextchild); Q.QInsert(nextchild); child=nextchild; //item=getchar(); } cin>>item; } } output(); return root;}//=============================================================//先序遍历树 template 
                                                             
                                                              void Tree
                                                              
                                                               ::PreOrder( TreeNode
                                                               
                                                                * t) const { if(t == NULL) { return; } cout<
                                                                
                                                                 GetData()<<" "; PreOrder(t->GetFirstChild()); PreOrder(t->GetNextBrother());}template 
                                                                 
                                                                  void Tree
                                                                  
                                                                   ::NorePreOrder(TreeNode
                                                                   
                                                                    * t) const{ LStack
                                                                    
                                                                     
                                                                      *> q; if(t!=NULL) { q.Push(t); } TreeNode
                                                                      
                                                                        *node; while(!q.IsEmpty()) { q.Pop(node); cout<
                                                                       
                                                                        GetData()<<" "; if(node->GetFirstChild() != NULL) { q.Push(node->GetFirstChild()); } if(node->GetNextBrother() != NULL) { q.Push(node->GetNextBrother()); } }}//=========================================//后序遍历树 template 
                                                                        
                                                                         void Tree
                                                                         
                                                                          ::PostOrder( TreeNode
                                                                          
                                                                           * t) const { if(t == NULL) { return; } PostOrder(t->GetFirstChild()); cout<
                                                                           
                                                                            GetData()<<" "; PostOrder(t->GetNextBrother());}template 
                                                                            
                                                                             void Tree
                                                                             
                                                                              ::NorePostOrder(TreeNode
                                                                              
                                                                               * t) const{ LStack
                                                                               
                                                                                
                                                                                 *> s; if(t!=NULL) s.Push(t); TreeNode
                                                                                 
                                                                                   *node; while(!s.IsEmpty()) { s.Pop(node); if(node->GetFirstChild() != NULL) { s.Push(node->GetFirstChild()); } cout<
                                                                                  
                                                                                   GetData()<<" "; if(node->GetNextBrother() != NULL) { s.Push(node->GetNextBrother()); } }}//======================================//层次遍历，非递归 template 
                                                                                   
                                                                                    void Tree
                                                                                    
                                                                                     ::NoreLevelOrder(TreeNode
                                                                                     
                                                                                      * t) const{ LQueue
                                                                                      
                                                                                       
                                                                                        *> q; TreeNode
                                                                                        
                                                                                         *s=NULL; //所有firstchild都入队，brother立即访问 if(t!=NULL) { q.QInsert(t); } TreeNode
                                                                                         
                                                                                           *node; while(s!=NULL||!q.IsEmpty()) { while(s!=NULL) { node=s; s=NULL; cout<
                                                                                          
                                                                                           data<<" "; if(node->GetFirstChild() != NULL) { q.QInsert(node->GetFirstChild()); } if(node->GetNextBrother() != NULL) { s=node->GetNextBrother(); } } if(!q.IsEmpty()) { q.QDelete(node); cout<
                                                                                           
                                                                                            GetData()<<" "; if(node->GetFirstChild() != NULL) { q.QInsert(node->GetFirstChild()); } if(node->GetNextBrother() != NULL) { s=node->GetNextBrother(); } } }} //========================================//删除结点及其左右子树template 
                                                                                            
                                                                                             void Tree
                                                                                             
                                                                                              ::Del(TreeNode
                                                                                              
                                                                                                *t){ if(t != NULL) { Del(t->GetFirstChild()); Del(t->GetNextBrother()); delete t; }} template 
                                                                                               
                                                                                                void Tree
                                                                                                
                                                                                                 ::DelSubTree(TreeNode
                                                                                                 
                                                                                                  * t,TreeNode
                                                                                                  
                                                                                                    *p){ if(t != NULL&&p!=NULL) { TreeNode
                                                                                                   
                                                                                                    *q=NULL,*result=NULL; result=FindFather(t,p); if(result)//如果p父节点存在 { if(result->GetFirstChild()==p)//如果p是f的大孩子节点 { result->SetFirstChild(p->GetNextBrother()); Del(p); return; } else//如果不是大孩子结点 { q=result->GetFirstChild(); while(q->GetNextBrother()!=p) q=q->GetNextBrother(); q->SetNextBrother(p->GetNextBrother()); Del(p); return; } } else { Del(p); root=NULL; } }}
                                                                                                   
                                                                                                  
                                                                                                 
                                                                                                
                                                                                               
                                                                                              
                                                                                             
                                                                                            
                                                                                           
                                                                                          
                                                                                         
                                                                                        
                                                                                       
                                                                                      
                                                                                     
                                                                                    
                                                                                   
                                                                                  
                                                                                 
                                                                                
                                                                               
                                                                              
                                                                             
                                                                            
                                                                           
                                                                          
                                                                         
                                                                        
                                                                       
                                                                      
                                                                     
                                                                    
                                                                   
                                                                  
                                                                 
                                                                
                                                               
                                                              
                                                             
                                                            
                                                           
                                                          
                                                         
                                                        
                                                       
                                                      
                                                     
                                                    
                                                   
                                                  
                                                 
                                                
                                               
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

　如题，没什么好说的。。