// Дерево.

#include <iostream.h>
#include <stdlib.h>
#include <conio.h>

template <class TREE> class tree
{
        TREE info;
        tree *left;
        tree *right;
         public:
                tree(int ninfo)
                { left=NULL; right=NULL; info=ninfo;}
                void add(tree *r,TREE ninfo);
                void del(tree *r,TREE kinfo);
                void print(tree *r,int i,int n);
                tree* search(tree *r,TREE kinfo);
};

template <class TREE> void tree<TREE>::add(tree<TREE> *r,TREE ninfo)
{
int ok=0;
                while (ok==0) {
                        if (ninfo>r->info)
                                if (r->right!=NULL)
                                  r=r->right;
                                  else {
                                  r->right=new tree<TREE>(ninfo); ok=1;
                                  }
                                  else if (r->left!=NULL) r=r->left;
                                  else
                                  { r->left=new tree<TREE>(ninfo); ok=1; }
                }
}

template <class TREE> void tree<TREE>::print(tree<TREE> *r,int i,int n)
{
int k,j;
if (r!=NULL) { gotoxy(n,i);
                 cout<<r->info<<' ';
                   k=40; j=1; while (j!=i) { j=j+2; k=k/2; };
                   if ((r->left)!=NULL) {gotoxy(n-(k/2),i+1); cout<<'/';}
           print(r->left,i+2,n-(k/2));
                   if ((r->right)!=NULL){ gotoxy(n+(k/2),i+1); cout<<'\\';}
                   print(r->right,i+2,n+(k/2));
                   }
}
template <class TREE> tree<TREE>* tree<TREE>::search(tree<TREE> *r,TREE kinfo)
{
if (r==NULL)
           return NULL;
           else if (r->info==kinfo) return r;
                   else {
                                          if (search(r->left,kinfo)==NULL)
                                          return search(r->right,kinfo); else
                                          return search(r->left,kinfo);
                   }
}
template <class TREE> void tree<TREE>::del(tree<TREE> *r,TREE kinfo)
{ if (r!=NULL) if (kinfo<r->info) del(r->left,kinfo); else
        if (kinfo>r->info) del(r->right,kinfo);
        else {
  tree<TREE> *g;
  g=r;
        if (g->right==NULL) r=g->left; else
                if (g->left==NULL) r=g->right; else
                        {
                                while (r->right!=NULL) r=r->right;
                                g->info=r->info;
                                g=r; r=r->left;
                        }
        delete g;
  }
}
void main()
{   clrscr();
        char c;
        tree <char> *root=new tree<char>('d');
        tree<char> Tree('a');
        for (int i=0;i<5;i++)
        {   cout<<"Введите символ :";
                cin>>c;
                Tree.add(root,c);
        }
        clrscr();
        Tree.print(root,1,40);
        cout<<endl<<"Какой элемент найти? "; cin>>c;
        if (Tree.search(root,c)!=NULL) cout<<"Элемент найден!!!";
		else cout<<"Элемент не найден.";
	   }