bst5.h

用c实现的二叉树的中序遍历的读取与存储

#ifndef BST5_H
#define BST5_H
#include"binnodeptr1.h"
#include<iostream.h>
#include"lqueue.h"
class BST5
{
   private:
      BinNodePtr1* root;
      int nodecount,temp2;
      LQueue<BinNodePtr1*>queue;
      void clearhelp(BinNodePtr1*);
      BinNodePtr1* deletemin(BinNodePtr1*,BinNodePtr1*&);
      BinNodePtr1* removehelp(BinNodePtr1*&,const int&,BinNodePtr1*&);
      bool findhelp(BinNodePtr1*,const int&,int&) const;
      void printhelp(BinNodePtr1*,int) const;

   public:
      BST5()
      {
          count=0;nodecount=0;
          for(int i=0;i<200;i++)
           a[i]=0;
      }
      int a[200],count;
      void shuzhu(int b[])
      {
        for(int i=0;i<200;i++)
          if(a[i]!=0)
          {b[i]=a[i];
          }
      }
      void ccbl(BinNodePtr1* &root)
      {
          BinNodePtr1* temp=new BinNodePtr1;
          queue.enqueue(root);
          while(queue.dequeue(temp)!=false)
          {     if(temp!=NULL)
              { a[count]=temp->val();
                //cout<<count<<"nodecount"<<a[count]<<" ";
                //cout<<temp->val();
                queue.enqueue(temp->left());
                queue.enqueue(temp->right());
                count++;
              }
         }
     }

      void insert(BinNodePtr1* &root,int e)
      {
         BinNodePtr1* temp1;
         BinNodePtr1* temp2;
         if(root==NULL)
         {
           root=new BinNodePtr1;
           root->setval(e);
           root->setLeft(NULL);
           root->setRight(NULL);
         }
         else
         {
            temp1=root;
            while(temp1!=NULL)
            {
              temp2=temp1;
              if((temp1->val())>e)
                 temp1=temp1->left();
              else
                 temp1=temp1->right();
            }

         BinNodePtr1* temp3=new BinNodePtr1;//();
            temp3->setval(e);
            temp3->setLeft(NULL);
            temp3->setRight(NULL);
            if((temp2->val())>e)
              temp2->setLeft(temp3);
            else
              temp2->setRight(temp3);
      }
      nodecount++;
    }
void print(BinNodePtr1* subroot,int level)
      {
         if(subroot==NULL) return;
         print(subroot->left(),level+1);
         for(int i=0;i<level;i++)
           cout<<"  ";
         cout<<subroot->val()<<"\n";
         print(subroot->right(),level+1);
      }
bool find(BinNodePtr1*&root,const int&k,int&e)const
{return findhelp(root,k,e);}
int size(){return nodecount;}
bool remove(BinNodePtr1* &root,const int&k,int&e)
{
   BinNodePtr1*t=NULL;
   root=removehelp(root,k,t);
   if(t==NULL)return false;
   e=t->val();
   nodecount--;
   delete t;
   return true;
}
bool removeAny(BinNodePtr1*&root,int&e)
{
  if(root==NULL)return false;
  BinNodePtr1* t;
  root=deletemin(root,t);
  e=t->val();
  nodecount--;
  delete t;
  return true;
}
void clear(BinNodePtr1*&root)
{clearhelp(root);root=NULL;nodecount=0;}
};
void BST5::clearhelp(BinNodePtr1* subroot)
{
    if(subroot==NULL)return;
    clearhelp(subroot->left());
    clearhelp(subroot->right());
    delete subroot;
}
bool BST5::findhelp(BinNodePtr1* subroot,const int& k,int& e)const
{
  if(subroot==NULL)return false;
  else if(k<subroot->val())
    return findhelp(subroot->left(),k,e);
  else if(k>subroot->val())
    return findhelp(subroot->right(),k,e);
  else { e=subroot->val();return true;}
}
BinNodePtr1* BST5::deletemin(BinNodePtr1* subroot,BinNodePtr1*& min)
{
  if(subroot->left()==NULL)
  {
    min=subroot;
    return subroot->right();
  }
  else{
    subroot->setLeft(deletemin(subroot->left(),min));
    return subroot;
  }
}
BinNodePtr1*BST5:: removehelp(BinNodePtr1* &subroot,const int&k,BinNodePtr1*& t)
{
   if(subroot==NULL)return NULL;

   else if(k<(subroot->val()))
   {
     subroot->setLeft(removehelp(subroot->left(),k,t));
     }
   else if(k>subroot->val()) {
     subroot->setRight(removehelp(subroot->right(),k,t));
     }
   else {
      BinNodePtr1* temp;
      t=subroot;
      if(subroot->left()==NULL)
         subroot=subroot->right();
      else if(subroot->right()==NULL)
         subroot=subroot->left();
      else{
        subroot->setRight(deletemin(subroot->right(),temp));
        int te=subroot->val();
        subroot->setval(temp->val());
        temp->setval(te);
        t=temp;
        }
      }

      return subroot;
}
#endif