ParentArrayBin3

#include <iostream>

using namespace std;

#define CAPACITY 100

template <class T = int>
struct node
{
    T inf;
    node<T> *left, *right;
};

template <class T = int>
class ParentBT
{
public:
    ParentBT();
    ~ParentBT();
    ParentBT(const ParentBT<T>&);
    ParentBT<T>& operator=(const ParentBT<T>&);

    bool empty() const;
    T getRoot() const;
    void create();
    void createTree(node<T>*&, T&);
    void print() const;
private:
    T *parent; //array of parents
    node<T> *root;
    int size;

    void deleteTree(node<T>* &);
    void copy(node<T> * &, node<T>* const&) const;
    void copyTree(ParentBT<T> const&);
    void pr(const node<T>*) const;
};
template <class T>
ParentBT<T>::ParentBT()
{
    root = NULL;
    parent = new T[CAPACITY];
    size = 0;
}
template <class T>
ParentBT<T>::~ParentBT()
{
    deleteTree(root);
}
template <class T>
ParentBT<T>::ParentBT(const ParentBT<T>& t)
{
    copyTree(t);
}
template <class T>
ParentBT<T>& ParentBT<T>::operator=(const ParentBT<T>& t)
{
    if (this != &t)
    {
        deleteTree(root);
        copyTree(t);
    }
    return *this;
}
template <class T>
void ParentBT<T>::deleteTree(node<T>* &p)
{
    delete parent;
    size = 0;
    if (p)
    {
        deleteTree(p->left);
        deleteTree(p->right);
        delete p;
        p = NULL;
    }
}
template <class T>
void ParentBT<T>::copyTree(ParentBT<T> const& t)
{
    copy(root, t.root);
    for (int i = 0; i < size; i++)
        parent[i] = t.parent[i];
}
template <class T>
void ParentBT<T>::copy(node<T> * & p, node<T>* const & r) const
{
    p = NULL;
    if (r)
    {
        p = new node<T>;
        p->inf = r->inf;
        copy(p->left, r->left);
        copy(p->right, r->right);
    }
}
template <class T>
bool ParentBT<T>::empty() const
{
    return root == NULL;
}
template <class T>
T ParentBT<T>::getRoot() const
{
    for (int i = 0; i < size; i++)
        if (parent[i] == -1) return i;
}
template <class T>
void ParentBT<T>::createTree(node<T>* & pos, T &x)
{
    pos = new node<T>;
    pos->inf = x;
    pos->left = NULL;
    pos->right = NULL;
    //cout << "root x: " << x << endl;
    for (int i = 0; i < size; i++)
    {
        if (parent[i] == pos->inf && pos->left == NULL)
        {
            x = i;
            //cout << "left x: " << x << endl;
            createTree(pos->left, x);
        }
        else if (parent[i] == pos->inf && pos->left != NULL)
        {
            x = i;
            //cout << "right x: " << x << endl;
            createTree(pos->right, x);
        }
    }
}
template <class T>
void ParentBT<T>::create()
{
    cout << "enter parents, max 2 equal parents (one parent can have only 2 children ): ";
    char flag;
    cout << "parent -> y/n"; cin >> flag;
    while (flag == 'y')
    {
        cout << "parent: ";
        cin >> parent[size];
        if (parent[size] == parent[size - 1] && parent[size] == parent[size - 2] && size > 1)
        {
            cout << "there are allready two children wiht same parent\nparent -> y/n";
            cin >> flag;
            cout << "parent: ";
            cin >> parent[size];
        }
        size++;
        cout << "parent -> y/n";
        cin >> flag;
        if (size == CAPACITY - 1) break;
    }
    T x;
    for (int i = 0; i < size; i++)
        if (parent[i] == -1) x = i;
    createTree(root,x);
}
template <class T>
void ParentBT<T>::pr(const node<T>*p) const
{
    if (p)
    {
        pr(p->left);
        cout << p->inf << " ";
        pr(p->right);
    }
}
template <class T>
void ParentBT<T>::print() const
{
    pr(root);
}



int main()
{
    ParentBT<int> binTree;
    binTree.create();
    cout << "root: " << binTree.getRoot() << endl;
    binTree.print();


    return 0;

    /*
    1) we create an array of parents:
        example:
        parent[] = {1, 5, 5, 2, 2, -1, 3}
          indexes-> #0,#1,#2,#3,#4,#5,#6
          -1 -> root
    2) create a tree(node) from the parent array:
           5
         /  \
        1    2
       /    / \
      0    3   4
          /
         6
    3) print tree(LRD): 0 1 5 6 3 2 4
    */
}