tree.cpp

linux编程

#include <iostream> 
#include "thead.h"
Tree *head = NULL;
Tree *now = NULL;
Tree *p=NULL;
int s[100];
int i; 

void preprint(Tree *ptr)
   {
      if (ptr!=0) 
      {
          ptr->print();
          std::cout<<"\t";
          preprint(ptr->lchild);
          preprint(ptr->rchild);
      }    
      
	
   }
 void inprint(Tree *ptr)
   {
      if (ptr!=0) 
      {
          inprint(ptr->lchild);
          ptr->print();
          std::cout<<"\t";
          inprint(ptr->rchild);
      }    
      
	
   }
 void postprint(Tree *ptr)
   {
      if (ptr!=0) 
      {
          postprint(ptr->lchild);
          postprint(ptr->rchild);
          ptr->print();
          std::cout<<"\t";
      }    
      
	
   }
 
 void find(int high,int num)
 {
    p=head; 
    
    int t=num-1; 
    for (i=0;i<high-1;i++)
      {
         s[i]=t%2;
         t=t/2; 
      } 
    for(i=high-2;i>=0;i--)
      {
          now=p; 
          if (s[i]==0)
             p=p->lchild;
          else
             p=p->rchild;  
                 
      }
         
 }
  
   
int main()
{
    int choice;char key='y';
    
    std::cout<<"下面将开始创建一个异质树..."<<std::endl;
    while ((key=='y')||(key=='Y'))
    { 
    
    std::cout<<" 1: 现有节点的左孩子节点加入一个整型节点"<<std::endl;
    std::cout<<" 2: 现有节点的右孩子节点加入一个整型节点"<<std::endl;
	std::cout<<" 3: 现有节点的左孩子节点加入一个字符型节点"<<std::endl;
	std::cout<<" 4: 现有节点的右孩子节点加入一个字符型节点"<<std::endl;
	std::cout<<" 5: 指定位置加入一个整型节点"<<std::endl;
	std::cout<<" 6: 指定位置加入一个字符型节点"<<std::endl;
	std::cout<<" 7: 删除指定位置节点"<<std::endl;
    std::cout<<" 8: 前序遍历"<<std::endl;
	std::cout<<" 9: 中序遍历"<<std::endl;
	std::cout<<"10: 后序遍历"<<std::endl;
	std::cout<<"11: 打印指定位置节点"<<std::endl;
	std::cout<<"12: 退出"<<std::endl;
	std::cout<<"注意：第一次创建异质树请选择前四个选项"<<std::endl;
	std::cout<<"请选择...."<<std::endl;
	
    std::cin>>choice; 
    
    
   
               switch(choice)
               {
               case 1:
                    {   
                       int int_value;
                       std::cout<<"请输入整型值: ";
				       std::cin>>int_value;
				       
                       Int_node *pInt = new Int_node();
			           pInt->add(int_value);
                       if (head==NULL) 
                       {
                           head = (Tree *)pInt;
                           now = (Tree *)pInt;
                       }
                       else
                       {
                         now->lchild = (Tree *) pInt;
		                 now = (Tree *)pInt;      
                       }    
                       
				       break; 
                     }
               case 2:
                    {   
                       int int_value;
                       std::cout<<"请输入整型值: ";
				       std::cin>>int_value;
				       
                       Int_node *pInt = new Int_node();
			           pInt->add(int_value);
                       if (head==NULL) 
                       {
                           head = (Tree *)pInt;
                           now = (Tree *)pInt;
                       }
                       else
                       {
                         now->rchild = (Tree *) pInt;
		                 now = (Tree *)pInt;      
                       }    
                       
				       break; 
                     }
                 case 3:
                    {   
                       char char_value;
                       std::cout<<"请输入字符型值: ";
				       std::cin>>char_value;
				       
                       Char_node *pChar = new Char_node();
			           pChar->add(char_value);
                       if (head==NULL) 
                       {
                           head = (Tree *)pChar;
                           now = (Tree *)pChar;
                       }
                       else
                       {
                         now->lchild = (Tree *) pChar;
		                 now = (Tree *)pChar;      
                       }    
                       
				       break; 
                     }
                 case 4:
                    {   
                       char char_value;
                       std::cout<<"请输入字符型值: ";
				       std::cin>>char_value;
				       
                       Char_node *pChar = new Char_node();
			           pChar->add(char_value);
                       if (head==NULL) 
                       {
                           head = (Tree *)pChar;
                           now = (Tree *)pChar;
                       }
                       else
                       {
                         now->rchild = (Tree *) pChar;
		                 now = (Tree *)pChar;      
                       }    
                       
				       break; 
                     }
                 case 8:
			       {
				      
                          std::cout<<"开始前序遍历"<<std::endl;
                          preprint(head);
                          break;
                      
	        	      
			       }
			       case 9:
			       {
				      
                          std::cout<<"开始中序遍历"<<std::endl;
                          inprint(head);
                          break;
                      
	        	      
			       }
			       case 10:
			       {
				      
                          std::cout<<"开始后序遍历"<<std::endl;
                          postprint(head);
                          break;
                      
	        	      
			       } 
			       case 5:
                   {
                       int high,num;
                       std::cout<<"请输入插入节点树的层次: ";
				       std::cin>>high;
                       std::cout<<"请输入插入节点树的位置: ";
				       std::cin>>num; 
                       int int_value;
                       std::cout<<"请输入整型值: ";
				       std::cin>>int_value;
            
                       find(high,num);
                       
                       Int_node *pInt = new Int_node();
			           pInt->add(int_value);
                       
                       if(s[0]==0)
                       {
                         now->lchild = (Tree *) pInt;
		                 now = (Tree *)pInt;      
                       }   
                       else
                       {
                         now->rchild = (Tree *) pInt;
		                 now = (Tree *)pInt;      
                       }  
                       break;
                    } 
                    case 6:
                   {
                       int high,num;
                       std::cout<<"请输入插入节点树的层次: ";
				       std::cin>>high;
                       std::cout<<"请输入插入节点树的位置: ";
				       std::cin>>num; 
                       char char_value;
                       std::cout<<"请输入字符型值: ";
				       std::cin>>char_value;
            
                       find(high,num);
                       
                       Char_node *pChar = new Char_node();
			           pChar->add(char_value);
                       
                       if(s[0]==0)
                       {
                         now->lchild = (Tree *) pChar;
		                 now = (Tree *)pChar;      
                       }   
                       else
                       {
                         now->rchild = (Tree *) pChar;
		                 now = (Tree *)pChar;      
                       }  
                       break;
                    } 
                    case 11:
                    {
                       int high,num;
                       std::cout<<"请输入插入节点树的层次: ";
				       std::cin>>high;
                       std::cout<<"请输入插入节点树的位置: ";
				       std::cin>>num;   
           
                       find(high,num);   
                       
                       std::cout<<"打印节点:"; 
                       p->print();
                       std::cout<<std::endl;
                       break; 
                    } 
                    case 7:
                    {
                       int high,num;
                       Tree *q;
                       std::cout<<"请输入删除节点树的层次: ";
				       std::cin>>high;
                       std::cout<<"请输入删除节点树的位置: ";
				       std::cin>>num;   
           
                       find(high,num);   
                       
                      if(s[0]==0)
                       {
                         q = p->rchild;
		                 if (p->lchild!=0)
                         { 
                             now->lchild=p->lchild;    
                             now=now->lchild;
                             if (q!=0) now->rchild=q;
                          }
                          else   if (q!=0) now->lchild=q;  
                       }   
                       else
                       {
                         q = p->rchild;
		                 if (p->lchild!=0)
                         {
                             now->rchild=p->lchild;    
                             now=now->rchild;
                             if (q!=0) now->rchild=q;      
                          }    
                          else if (q!=0) now->rchild=q;
                       }  
                       
                       std::cout<<std::endl;
                       break; 
                    } 
                    case 12:
                    {
                        key='0';
                        break;
                    }     
       }
         std::cout<<std::endl;
         std::cout<<std::endl;
         if ((key=='y')||(key=='Y')) 
         {
             std::cout<<"是否继续（Y/N）"<<std::endl;
             std::cin>>key;   
          }    
         std::cout<<std::endl;                  
}    
    

    return 1; 
}