#include <iostream>
#include <cstdlib>
#include <time.h>
#include <string.h>

using namespace std;
int counter = 0;
class Node
{
        char d;
        Node *lft;
        Node *mdl;
        Node *rgt;
       
public:
        //static int counter;
        Node()
        {
                lft = 0;
                mdl = 0;
                rgt = 0;       
               
                cout << "M" << endl;
        }
        ~Node()
        {
                if (lft) delete lft;
                if (mdl) delete mdl;
                if (rgt) delete rgt;
        }
        friend class Tree;
};
 
class Tree
{
        Node *root;
       
        char num, maxnum;
        int maxrow, offset;
        char **SCREEN;
        void clrscr();
        Node *MakeNode(int depth);
        void OutNodes(Node *v, int r, int c);
        Tree(const Tree &);
        Tree(Tree &&);
        Tree operator = (const Tree&) const;
        Tree operator = (Tree &&) const;
public:
       
        Tree(char nm, char mnm, int mxr) :
                num(nm), maxnum(mnm), maxrow(mxr), offset(40), root(NULL)
        {
                SCREEN = new char *[maxrow];
                for (int i = 0; i < maxrow; i++)
                        SCREEN[i] = new char[80];
        }
 
        ~Tree()
        {
                for (int i = 0; i < maxrow; i++)
                        delete[]SCREEN[i];
                delete[]SCREEN;
                delete root;
        }
        void MakeTree()
        {
                root = MakeNode(0);
        }
        bool exist()
        {
                return root != NULL;
        }
        int DFS();
        int BFS();
        void OutTree();
};
 
Node * Tree::MakeNode(int depth)
{
        Node * v = NULL;
        int Y = (depth < rand() % 6 + 1) && (num >= 'a') && (num <= 'z');
        if (Y)
        {
                v = new Node;
                v->d = num++;
                v->lft = MakeNode(depth + 1);
                v->mdl = MakeNode(depth + 1);
                v->rgt = MakeNode(depth + 1);
               
               
                if (v->lft || v->mdl || v->rgt)
                        counter++;
        }
        return v;
}
 
void Tree::OutTree()
{
        clrscr();
        OutNodes(root, 1, offset);
        for (int i = 0; i < maxrow; i++)
        {
                SCREEN[i][79] = 0;
                cout << '\n' << SCREEN[i];
        }
        cout << '\n';
}
 
void Tree::clrscr()
{
        for (int i = 0; i < maxrow; i++)
                memset(SCREEN[i], '.', 80);
}
 
void Tree::OutNodes(Node * v, int r, int c)
{
        if (r && c && (c < 80)) SCREEN[r - 1][c - 1] = v->d;
        if (r < maxrow)
        {
                if (v->lft) OutNodes(v->lft, r + 1, c - (offset >> r));
                if (v->mdl) OutNodes(v->mdl, r + 1, c);
                if (v->rgt) OutNodes(v->rgt, r + 1, c + (offset >> r));
        }
}
 
template <class Item> class QUEUE
{
        Item * Q;
        int h, t, N;
public:
        QUEUE(int maxQ) : h(0), t(0), N(maxQ) { Q = new Item[maxQ + 1]; }
        int empty() const { return (h % N) == t; }
        void put(Item item) { Q[t++] = item; t %= N; }
        Item get() { h %= N; return Q[h++]; }
};
 
int Tree::BFS()
{
        const int MaxQ = 20;
        int count = 0;
        QUEUE < Node * > Q(MaxQ);
        Q.put(root);
        while (!Q.empty())
        {
                Node * v = Q.get();
                cout << v->d << '_';
                count++;
                if (v->lft) Q.put(v->lft);
                if (v->mdl) Q.put(v->mdl);
                if (v->rgt) Q.put(v->rgt);
        }
        return count;
}
 
int main()
{
        setlocale(0, "");
        int n = 0;
        Tree Tr('a', 'z', 4);
        srand(time(nullptr));
        Tr.MakeTree();
        if (Tr.exist())
        {
                Tr.OutTree();
                cout << endl << "Обход в ширину: ";
                n = Tr.BFS();
                cout << endl << "Пройдено узлов: " << n << endl;
                cout << "Количество узлов с хотя бы 1 потомком: " << counter << endl;
        }
        else cout << "Дерево пусто.";
        cout << endl << "Конец." << endl;
        system("pause");
        return 0;
}