18.12.2018

#include <iostream>
#include <string>
#include <iomanip>
using namespace std;




template <typename T>
class BTNode
{
    T data;
    BTNode*pLeft;
    BTNode*pRigt;

public:
    BTNode(const T& _data = T(), BTNode *_pLeft = nullptr, BTNode *_pRigt = nullptr) : data(_data), pLeft(_pLeft), pRigt(_pRigt) {}


    void setData(const T&_data)
    {
        T data = _data;
    }


    T getData()
    {
        return data;
    }

    void setpRight(BTNode*_pRigt)
    {
        pRigt = _pRigt;
    }
    void setpLeft(BTNode*_pLeft)
    {
        pLeft = _pLeft;
    }

    const BTNode *getpRight()const
    {
        return pRigt;
    }

    BTNode *getpRight()
    {
        return pRigt;
    }


    const BTNode *getpLeft()const
    {
        return pLeft;
    }
    BTNode *getpLeft()
    {
        return pLeft;
    }

    bool isLeaf()const
    {
        if (pLeft == nullptr&&pRigt == nullptr)
        {
            return true;
        }
    }
};



template<typename T>
 void Add(const T & data, BTNode <T> *&root)
{
    if (root == nullptr)
    {
        root = new BTNode<T>(data);
            return;
    }
    BTNode<T> *pCurrent = root;
    while (true)
    {
        if (pCurrent->getData() == data)
            return;
        if (pCurrent->getData()<data)
        {


            if (pCurrent->getpRight()==nullptr)
            {
                pCurrent->setpRight(new BTNode<T>(data));
                return;
            }
            else
            {
                pCurrent = pCurrent->getpRight();
            }

        }
        else
        {
            if (pCurrent->getpLeft() == nullptr)
            {
                pCurrent->setpLeft(new BTNode<T>(data));
                return;
            }
            else
            {
                pCurrent = pCurrent->getpLeft();
            }
        }
    }

}
template<typename T>
BTNode <T> find (const T& data, BTNode <T>*root)
{
       if (root==nullptr)
          return nullptr;
 auto pCurrent=root;
 while(true)
{
    if (pCurrent->getData() == data)
         return pCurren;
      else if(data>pCurren->getData())
           {
             if (pCurrent ->getRight()!=nullptr)
           { pCurrent=pCurrent->getRight();}
             else
              {
               return nullptr;
              }

    else
{
 if (pCurrent->getData() == data)
         return pCurren;
      else if(data<pCurren->getData())
           {
             if (pCurrent ->getLeft()!=nullptr)
           { pCurrent=pCurrent->getLeft();}
             else
              {
               return nullptr;
              }


}





//void fillTree(BTNode<string>*&root)
//{
//  root = new BTNode<string>("Оно Живет в воде?");
//  BTNode<string>*temp = new BTNode <string>("У него есть жабры?");
//  temp->setpLeft(new BTNode<string>("Щука"));
//  temp->setpRight(new BTNode<string>("Лягушка"));
//  root->setpLeft(temp);
//  temp = new BTNode <string>("у него 4 лапы?");
//  temp->setpLeft(new BTNode<string>("Кот"));
//  temp->setpRight(new BTNode<string>("Змея"));
//  root->setpRight(temp);
//}
template <typename T>
void printTree(BTNode <T>*root,int indent=0)
{
    if (root != nullptr)
    {
        printTree(root->getpRight(), indent + 8);

        cout << setw(indent) << root->getData() << endl;


        printTree(root->getpLeft(), indent + 8);

        //cout << root->getData() << endl;

    }
}


void main()
{
    BTNode <int>*root = nullptr;

    //printTree(root);

    for (int i = 0; i < 100; i++)
    {
        Add(rand() % 100, root);

    }
    printTree(root);
    system("Pause");


}