htree.cpp

异质链表 的实现 实现异质链表的查找、插入、删除和遍历

  #include <iostream>  
  #include <stdlib.h>
  #include <string>
  #include <typeinfo>
  #include <iomanip>
  #include   "HTree.h" 

  using namespace std; 
  
  //构造BaseNode 
  BaseNode::BaseNode(void) : Lchild(0),Rchild(0)
  {   
  }   
  //析构BaseNode
  BaseNode::~BaseNode()   
  {   
    
  }   
  //打印节点数据 
  void   BaseNode::print()   
  {   
    
  } 
   void   BaseNode::set(){}
  //构造节点 
  template<class T> BTNode<T>::BTNode(T nodeValue,BaseNode* leftNode,BaseNode* rightNode):data(nodeValue),Lchild(leftNode),Rchild(rightNode)   
  {   
   cout   <<   "创建"<< typeid(T).name()<<"型节点"<<"值为"<<nodeValue<<endl ; 
  }   
 //析构节点 
  template<class T> BTNode<T>::~BTNode()   
  {   
  cout   <<   "释放"<< typeid(T).name()<<"型节点" <<endl;   
  }   

  //打印节点内容 
  template<class T>  void   BTNode<T>::print()   
  {   
  cout   <<"节点数据:"<< data <<"\t节点类型:"<<typeid(T).name()<<"\tSizeOf(节点"<<typeid(T).name()<<")："<< sizeof(T)<<  endl;   
  }  
    template<class T>  void   BTNode<T>::set(T value)   
  {   
      data=value;   
  }  
  //构造二叉树
  HTree::HTree()   
  {   
//  HTree::PCurrent   =   NULL;//当前指针   
  HTree::PRoot  =   NULL;//头指针   
  }   
  //析构二叉树
  HTree::~HTree()   
  {   
  cout   <<   "释放二叉树"   <<endl;   
  }   
 /*
//二叉树的建立
void HTree::createBinTree(BaseNode*  root )
{
    if(root) 
    { 
        if(PRoot)
        {
             cout<<"根节点已存在"<<endl;       
        } 
        else
        {
            PRoot  =   root;   
            root->Lchild   =   NULL;  
            root->Rchild   =   NULL;           
        } 
    }
    else
    {
          cout<<"节点又误"<<endl;  
    } 
   
    
}  
  */
//二叉树的先序遍历

void HTree::preOrder(BaseNode* p)
{
    if(p)
    {
		p->print();
        cout<<"  ";
        preOrder(p->Lchild);
        preOrder(p->Rchild);
    }
}

//二叉树的中序遍历
void HTree::inOrder(BaseNode*  p)
{
    
    if(p)
    {
        HTree::inOrder(p->Lchild);
        //cout<<"1"<<"  ";;
		p->print();
		cout << " ";
        HTree::inOrder(p->Rchild);
    }
}
//二叉树的后序遍历
void HTree::levelOrder(BaseNode* p)
{
    if(p)
    {
        HTree::levelOrder(p->Lchild);
        HTree::levelOrder(p->Rchild);
        //cout<<"1"<<"  ";;
		p->print();
		cout << " ";
    }
}
//二叉树的建立

void HTree::createBinTree()
{
	PRoot = new BTNode<int>(10);
	PRoot->Lchild = new BTNode<short>(1);
	PRoot->Rchild = new BTNode<char>('a');
	PRoot->Lchild->Lchild = new BTNode<double>(1.0);
	PRoot->Lchild->Rchild = new BTNode<float>((float)1.1);
/*       cout<<setw(20)<<"==============="<<endl; 
       cout<<setw(20)<<"| [1]int      |"<<endl;  
       cout<<setw(20)<<"| [2]short    |"<<endl; 
       cout<<setw(20)<<"| [3]char     |"<<endl;  
       cout<<setw(20)<<"| [4]double   |"<<endl; 
       cout<<setw(20)<<"| [5]float    |"<<endl;  
       cout<<setw(20)<<"| .........   |"<<endl; 
       cout<<setw(20)<<"==============="<<endl;  
       cout<<"请选择您要添加的节点类型："<<endl; 
       
       char datatype='1';
       cin>>datatype;    
  

       if(datatype=='1')
       {
                  int temp; 
                  cout<< "请输入您要输入的数据："; 
                  cin>> temp;
                  BaseNode   *   root   =   new   BTNode<int>(temp); 
                  createBinTree(root->Lchild);
                  createBinTree(root->Rchild);
       } 
       else if(datatype=='2')
       {
                  short temp; 
                  cout<< "请输入您要输入的数据："; 
                  cin>> temp;
                  BaseNode   *   root   =   new   BTNode<short>(temp); 
                  createBinTree(root->Lchild);
                  createBinTree(root->Rchild);
       } 
              else if(datatype=='3')
       {
                  char temp; 
                  cout<< "请输入您要输入的数据："; 
                  cin>> temp;
                  BaseNode   *   root   =   new   BTNode<char>(temp); 
                  createBinTree(root->Lchild);
                  createBinTree(root->Rchild);
       } 
              else if(datatype=='4')
       {
                  double temp; 
                  cout<< "请输入您要输入的数据："; 
                  cin>> temp;
                  BaseNode   *   root   =   new   BTNode<double>(temp); 
                  createBinTree(root->Lchild);
                  createBinTree(root->Rchild);
       } 
              else if(datatype=='5')
       {
                  float temp; 
                  cout<< "请输入您要输入的数据："; 
                  cin>> temp;
                  BaseNode   *   root   =   new   BTNode<float>(temp); 
                  createBinTree(root->Lchild);
                  createBinTree(root->Rchild);
       } 
       else if( datatype=='0')
           {
                  char temp='x'; 

                  BaseNode   *   root   =   new   BTNode<char>(temp); 

    } 

*/
}
//统计二叉树中结点的个数
int HTree::countNode(BaseNode* p)
{
    if(p == NULL) return 0;
    return 1+HTree::countNode(p->Lchild)+HTree::countNode(p->Rchild);
}
//***********************************************************************************
//求二叉树的深度
int HTree::depth(BaseNode* p)
{
    if(p == NULL)
        return 0;
    int h1 = HTree::depth(p->Lchild);
    int h2 = HTree::depth(p->Rchild);
    if(h1>h2)return (h1+1);
    return h2+1;
}
//***********************************************************************************
//二叉树的消毁操作
void HTree::destroy(BaseNode* p)                         //消毁函数，用来消毁二叉树中的各个结点
    {
        if(p)
        {
            HTree::destroy(p->Lchild);
            HTree::destroy(p->Rchild);
            delete p;
        }
    }
//********************************************************************************
//主函数的设计 
int main ()
{

    HTree htree; 
BaseNode* rootNode=NULL; 


    int choiced = 0;
    while(1)
    {
        system("cls");
        cout<<"\n\n\n                              ---主界面---\n\n\n";
        cout<<"                     1、创建二叉树                2、先序遍历二叉树\n";
        cout<<"                     3、中序遍历二叉树            4、后序遍历二叉树\n";
        cout<<"                     5、统计结点总数              6、查看树深度    \n";
        cout<<"                     7、消毁二叉树                0、退出\n\n";
        cout<<"                     请选择操作：";
        cin>>choiced;
        if(choiced == 0)
            return 0;
        else if(choiced == 1)
        {
            system("cls");
			htree.createBinTree();
			rootNode = htree.GetRoot();
        }
        else if(choiced == 2)
        {
            system("cls");
            cout<<"先序遍历二叉树结果：\n";
            htree.preOrder(rootNode);
            cout<<endl;
			system("pause");
        }
        else if(choiced == 3)
        {
            system("cls");
            cout<<"中序遍历二叉树结果：\n";
            htree.inOrder(rootNode);
            cout<<endl;
            system("pause");
        }
        else if(choiced == 4)
        {
            system("cls");
            cout<<"后序遍历二叉树结果：\n";
            htree.levelOrder(rootNode);
            cout<<endl;
            system("pause");
        }
        else if(choiced == 5)
        {
            system("cls");
            int count = htree.countNode(rootNode);
            cout<<"二叉树中结点总数为"<<count<<endl;
            system("pause");
        }
        else if(choiced == 6)
        {
            system("cls");
            int dep = htree.depth(rootNode);
            cout<<"此二叉树的深度为"<<dep<<endl;
            system("pause");
        }
        else if(choiced == 7)
        {
            system("cls");
            cout<<"二叉树已被消毁！\n";
            htree.destroy(rootNode);
            cout<<endl;
            system("pause");
        }
        else 
        {
            system("cls");
            cout<<"\n\n\n\n\n\t错误选择！\n";
        }
        
    }
}