Бинарное Дерево - C++ - Ответ 284954

#pragma once
 
template <class T>
struct TreeEl{
  T data; 
  TreeEl<T> *pLeft,*pRight,*pParent;
  TreeEl(T d):data(d),pLeft(0),pRight(0),pParent(0)
  {}
};
template <class T>
class Tree{
  int N;
  TreeEl<T>*pRoot;
  void insertdata(TreeEl<T>*rt,T d);
  void printBy(TreeEl<T>*rt);
  bool delBy(TreeEl<T>*rt);
  TreeEl<T>* FindBy(T d,TreeEl<T> *rt);
public:
  T*Find(T d);
  Tree(void);
  Tree(Tree<T>&ob);
  void insert(T d);
  void print();
  bool delRoot();
  ~Tree(void);
  bool del(T d);
};
template <class T>
Tree<T>::Tree(Tree<T>&ob):pRoot(0),N(0){
  (*this).Tree<T>::~Tree();
}
template <class T>
Tree<T>::Tree(void):pRoot(0),N(0)
  { }
template <class T>
Tree<T>::~Tree(void){
  while(delRoot());
}
template <class T>
//////////////////////||||||||insert|||||||||||||/////////////////
void Tree<T>::insert(T d){
  if(pRoot==NULL){
      TreeEl<T>*pNew=new TreeEl<T>(d);
      pRoot=pNew;
      pNew->pParent=NULL;
      N++;
      return;
  }else{
      insertdata(pRoot,d);
  }
}
/////////////////////////////////////////////////////////
template <class T>
void Tree<T>::insertdata(TreeEl<T>*rt,T d){
  if(rt->data>d){
    if(rt->pLeft==NULL){
      TreeEl<T>*pNew=new TreeEl<T>(d);
      rt->pLeft=pNew;
      pNew->pParent=rt;
      N++;
      return;
    }
    insertdata(rt->pLeft,d);
  }else{
    if(rt->pRight==NULL){
      TreeEl<T>*pNew=new TreeEl<T>(d);
      rt->pRight=pNew;
      pNew->pParent=rt;
      N++;
      return;
    }
    insertdata(rt->pRight,d);
  }
}
///////////|||||||||||||||||print||||||||||||||////////////////////
template <class T>
void Tree<T>::printBy(TreeEl<T>*rt){
  if (rt==NULL)return;
  printBy(rt->pLeft);
  cout<<rt->data<<"\t";
  printBy(rt->pRight);
}
template <class T>
void Tree<T>::print(){
  printBy(pRoot);
}
////////////////////////////////////////////////////////////////////
template <class T>
bool Tree<T>::delBy(TreeEl<T>*rt){
  TreeEl<T>*p=rt;
  if(rt->pLeft){
    rt=rt->pLeft;
    while(rt->pRight)
      rt=rt->pRight;
    p->data=rt->data;
    delBy(rt);
  }else{
    if(rt->pRight){
      rt=rt->pRight;
      while(rt->pLeft)
        rt=rt->pLeft;
      p->data=rt->data;
      delBy(rt);
    }else{
      if(rt->pParent){
        if(rt->pParent->pRight==rt){
          rt->pParent->pRight=0;
        }
        else{
          rt->pParent->pLeft=0;
        }
      }//if
      delete rt;
      N--;    
      return 1;
    }//else
  }//else
}//fn
template <class T>
bool Tree<T>::del(T d){
    TreeEl<T>*rt=Find(d,pRoot);
    if(rt==0)
        return false;   
    if(rt->pLeft==NULL&&rt->pRight==NULL){
        delete rt;
        rt=NULL;
        return true;
    }
    delBy(rt);
    return true;
}
 
template <class T>
bool Tree<T>::delRoot(){
    if(pRoot==NULL) return false;
    if(pRoot->pLeft==NULL&&pRoot->pRight==NULL){
    delete pRoot;
    pRoot=NULL;
        return true;
  }
    delBy(pRoot);
    return true;
}
/////////////////////////////////////////////////////////////////////
 
template <class T>
TreeEl<T>* Tree<T>::FindBy(T d,TreeEl<T> *rt){
  if(!rt)return 0;
  //if(rt->data==d)return rt;
  while(rt&&rt->data!=d){
    if(rt->data>d)rt=rt->pLeft;
    else if(rt->data<d)rt=rt->pRight;
  }
  return rt;
}
template <class T>
T*Tree<T>::Find(T d){
  TreeEl<T>*p;
  p=FindBy(d,pRoot);
  if(p==0)return 0;
  return &p->data;
}