fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <time.h>
  4. #include <string.h>
  5.  
  6. using namespace std;
  7. int counter = 0;
  8. class Node
  9. {
  10.         char d;
  11.         Node *lft;
  12.         Node *mdl;
  13.         Node *rgt;
  14.  
  15. public:
  16.         //static int counter;
  17.         Node()
  18.         {
  19.                 lft = 0;
  20.                 mdl = 0;
  21.                 rgt = 0;       
  22.  
  23.                 cout << "M" << endl;
  24.         }
  25.         ~Node()
  26.         {
  27.                 if (lft) delete lft;
  28.                 if (mdl) delete mdl;
  29.                 if (rgt) delete rgt;
  30.         }
  31.         friend class Tree;
  32. };
  33.  
  34. class Tree
  35. {
  36.         Node *root;
  37.  
  38.         char num, maxnum;
  39.         int maxrow, offset;
  40.         char **SCREEN;
  41.         void clrscr();
  42.         Node *MakeNode(int depth);
  43.         void OutNodes(Node *v, int r, int c);
  44.         Tree(const Tree &);
  45.         Tree(Tree &&);
  46.         Tree operator = (const Tree&) const;
  47.         Tree operator = (Tree &&) const;
  48. public:
  49.  
  50.         Tree(char nm, char mnm, int mxr) :
  51.                 num(nm), maxnum(mnm), maxrow(mxr), offset(40), root(NULL)
  52.         {
  53.                 SCREEN = new char *[maxrow];
  54.                 for (int i = 0; i < maxrow; i++)
  55.                         SCREEN[i] = new char[80];
  56.         }
  57.  
  58.         ~Tree()
  59.         {
  60.                 for (int i = 0; i < maxrow; i++)
  61.                         delete[]SCREEN[i];
  62.                 delete[]SCREEN;
  63.                 delete root;
  64.         }
  65.         void MakeTree()
  66.         {
  67.                 root = MakeNode(0);
  68.         }
  69.         bool exist()
  70.         {
  71.                 return root != NULL;
  72.         }
  73.         int DFS();
  74.         int BFS();
  75.         void OutTree();
  76. };
  77.  
  78. Node * Tree::MakeNode(int depth)
  79. {
  80.         Node * v = NULL;
  81.         int Y = (depth < rand() % 6 + 1) && (num >= 'a') && (num <= 'z');
  82.         if (Y)
  83.         {
  84.                 v = new Node;
  85.                 v->d = num++;
  86.                 v->lft = MakeNode(depth + 1);
  87.                 v->mdl = MakeNode(depth + 1);
  88.                 v->rgt = MakeNode(depth + 1);
  89.  
  90.  
  91.                 if (v->lft || v->mdl || v->rgt)
  92.                         counter++;
  93.         }
  94.         return v;
  95. }
  96.  
  97. void Tree::OutTree()
  98. {
  99.         clrscr();
  100.         OutNodes(root, 1, offset);
  101.         for (int i = 0; i < maxrow; i++)
  102.         {
  103.                 SCREEN[i][79] = 0;
  104.                 cout << '\n' << SCREEN[i];
  105.         }
  106.         cout << '\n';
  107. }
  108.  
  109. void Tree::clrscr()
  110. {
  111.         for (int i = 0; i < maxrow; i++)
  112.                 memset(SCREEN[i], '.', 80);
  113. }
  114.  
  115. void Tree::OutNodes(Node * v, int r, int c)
  116. {
  117.         if (r && c && (c < 80)) SCREEN[r - 1][c - 1] = v->d;
  118.         if (r < maxrow)
  119.         {
  120.                 if (v->lft) OutNodes(v->lft, r + 1, c - (offset >> r));
  121.                 if (v->mdl) OutNodes(v->mdl, r + 1, c);
  122.                 if (v->rgt) OutNodes(v->rgt, r + 1, c + (offset >> r));
  123.         }
  124. }
  125.  
  126. template <class Item> class QUEUE
  127. {
  128.         Item * Q;
  129.         int h, t, N;
  130. public:
  131.         QUEUE(int maxQ) : h(0), t(0), N(maxQ) { Q = new Item[maxQ + 1]; }
  132.         int empty() const { return (h % N) == t; }
  133.         void put(Item item) { Q[t++] = item; t %= N; }
  134.         Item get() { h %= N; return Q[h++]; }
  135. };
  136.  
  137. int Tree::BFS()
  138. {
  139.         const int MaxQ = 20;
  140.         int count = 0;
  141.         QUEUE < Node * > Q(MaxQ);
  142.         Q.put(root);
  143.         while (!Q.empty())
  144.         {
  145.                 Node * v = Q.get();
  146.                 cout << v->d << '_';
  147.                 count++;
  148.                 if (v->lft) Q.put(v->lft);
  149.                 if (v->mdl) Q.put(v->mdl);
  150.                 if (v->rgt) Q.put(v->rgt);
  151.         }
  152.         return count;
  153. }
  154.  
  155. int main()
  156. {
  157.         setlocale(0, "");
  158.         int n = 0;
  159.         Tree Tr('a', 'z', 4);
  160.         srand(time(nullptr));
  161.         Tr.MakeTree();
  162.         if (Tr.exist())
  163.         {
  164.                 Tr.OutTree();
  165.                 cout << endl << "Обход в ширину: ";
  166.                 n = Tr.BFS();
  167.                 cout << endl << "Пройдено узлов: " << n << endl;
  168.                 cout << "Количество узлов с хотя бы 1 потомком: " << counter << endl;
  169.         }
  170.         else cout << "Дерево пусто.";
  171.         cout << endl << "Конец." << endl;
  172.         system("pause");
  173.         return 0;
  174. }
Success #stdin #stdout #stderr 0s 3236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M

.......................................a.......................................
...................b.......................................g...................
...................c.........f.............................h.........m.........
...................d....e..................................i....n..............

Обход в ширину: a_b_g_c_f_h_m_d_e_i_n_j_o_k_l_
Пройдено узлов: 15
Количество узлов с хотя бы 1 потомком: 9

Конец.
stderr
copy 
sh: 1: pause: not found
https://ideone.com/vjJRBF
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!