program.cpp

#include<iostream>
using namespace std;

struct  node
{
  int Key;
  int Count;
  node *Left;
  node *Right;
};

class TREE
{
  private:
    node *Tree;//Óêàçàòåëü íà êîðåíü äåðåâà.
    node  *Res;//Óêàçàòåëü íà íàéäåííóþ âåðøèíó.
    //Ïîèñê âåðøèíû â äåðåâå (ðåêóðñèâíûé àëãîðèòì).
    void Search (int, node**);
    void Delete_1 (node**,node**);
  public:
    TREE() { Tree = NULL;}
    node** GetTree() {return &Tree;}
    node** GetDel() {return &Res;}
    void  BuildTree ();
    void Vyvod (node**,int);
    bool Delete (node**, node**);
    void Poisk (int);
};

int main ()
{
  setlocale(LC_ALL,"Russian"); 
  TREE A;
  int el,x1,x2=0;
  bool fl=1;
  cout<<"Ñîçäàíèå áèíàðíîãî äåðåâà ïîèñêà(ââîäèòü ýë-òû äî 0):"<<endl;
  A.BuildTree ();  
  A.Vyvod(A.GetTree(),0);
  while(x2!=1 && fl)
  {
   cout<<"Ââåäèòå êëþ÷ óäàëÿåìîé âåðøèíû:"; 
   cin>>el;
   A.Poisk(el);
   fl=A.Delete(A.GetTree(),A.GetDel());  
   if(fl)
   {
    A.Vyvod (A.GetTree(),0);
   cout<<"1.Âûõîä 2.Ïðîäîëæèòü óäàëåíèå:";
   cin>>x2;
   }
  }
}



void TREE::BuildTree ()   //Ïîñòðîåíèå áèíàðíîãî äåðåâà ïîèñêà.
{
 int el;
 cout<<"Ââîäèòå êëþ÷è âåðøèí äåðåâà: \n";
 cin>>el;
 while  (el!=0)
 { 
  Search (el,&Tree);
  cin>>el;
 }
}

void TREE::Search (int x,node **p)
//Ïîèñê çâåíà x â áèíàðíîì äåðåâå ñî âñòàâêîé
//            (ðåêóðñèâíûé àëãîðèòì).
//*p - óêàçàòåëü íà âåðøèíó äåðåâà.
{
  if  (*p==NULL)
  { // Âåðøèíû â äåðåâå íåò; âêëþ÷èòü åå.
    *p = new(node);
    (**p).Key = x;
    (**p).Count = 1;
    (**p).Left = (**p).Right = NULL;
  }
  else
  if  (x<(**p).Key) Search (x,&((**p).Left));
  else
    if  (x>(**p).Key) Search (x,&((**p).Right));
    else  (**p).Count += 1;
}

void TREE::Vyvod (node **w,int l)
//Èçîáðàæåíèå äåðåâà w íà ýêðàíå äèñïëåÿ
//         (ðåêóðñèâíûé àëãîðèòì).
//*w - óêàçàòåëü íà êîðåíü äåðåâà.
{
  int i;
  if  (*w!=NULL)
  {
    Vyvod (&((**w).Right),l+1);
    for  (i=1; i<=l; i++) cout<<"   ";
    cout<<(**w).Key<<endl;
    Vyvod (&((**w).Left),l+1);
  }
}

void TREE::Poisk (int k)
// Ïîèñê âåðøèíû ñ êëþ÷îì k â äåðåâå
//      (íåðåêóðñèâíûé àëãîðèòì).
// Tree - óêàçàòåëü íà áèíàðíîå äåðåâî.
// Res  - óêàçàòåëü íà íàéäåííóþ âåðøèíó
{
  node *p=Tree;
  if  (Tree!=NULL)
  do
  {
    if  (p->Key==k) {Res=p;return;}
    else
      {
       if  (k<p->Key) p=p->Left;
       else  p=p->Right;
      }
  }while  (p!=NULL);
  Res=p;
  return;
}

bool TREE::Delete (node **p1,node **p2)
// Óäàëåíèå âåðøèíû k èç áèíàðíîãî äåðåâà.
// *p1 - óêàçàòåëü íà êîðåíü äåðåâà.
// *p2 - óêàçàòåëü íà óäàëÿåìóþ âåðøèíó.
{
  if  (*p1==NULL) 
  {
   cout<<"\nÎøèáêà íåò äåðåâà.";
   return 0;
  }
  else
  if (*p2==NULL) 
  {
   cout<<"\nÎøèáêà íåò óäàëÿåìîé âåðøèíû.";
   return 0;
  }
  else
  {
  if  ((**p2).Right==NULL || (**p2).Left==NULL) 
  {
   cout<<"Îøèáêà. Äî÷åðíÿÿ âåðøèíà òîëüêî îäíà."; 
   return 0;
  }
  else  Delete_1 (&((**p2).Left),&(*p2));
  return 1;
  }
}

void TREE::Delete_1 (node **r,node **q)
{
  node *s;
  if  ((**r).Right==NULL)
  {
    (**q).Key = (**r).Key;
    (**q).Count = (**r).Count;
    *q=*r;
    s=*r;
	*r=(**r).Left;
	delete s;
  }
  else  Delete_1 (&((**r).Right),q);
}