fork download
copy 
  1. #include <initializer_list>
  2. #include <iostream>
  3. #include <unordered_map>
  4. #include <vector>
  5.  
  6. struct Node {
  7.     int x, y;
  8.     std::vector<Node *> children;
  9.  
  10.     Node() : x(0), y(0), children()
  11.     {
  12.     }
  13.     Node(const std::initializer_list<Node *> &nodes)
  14.         : x(0), y(0), children(nodes)
  15.     {
  16.     }
  17. };
  18.  
  19. void
  20. place(Node *n, int y, int x, std::unordered_map<int, int> &leftFront)
  21. {
  22.     if (x < 0) {
  23.         x = 0;
  24.     }
  25.     if (leftFront.find(y) != leftFront.cend() && x <= leftFront[y]) {
  26.         x = leftFront[y] + 1;
  27.     }
  28.  
  29.     n->y = y;
  30.  
  31.     const int nchildren = n->children.size();
  32.     const int width = nchildren + (1 - nchildren%2);
  33.     int childX = x - width/2;
  34.     int i = 0;
  35.     Node *p; // previous child
  36.     for (Node *c : n->children) {
  37.         place(c, y + 1, childX, leftFront);
  38.  
  39.         childX = c->x;
  40.         if (nchildren%2 == 0) {
  41.             if (i == nchildren/2) {
  42.                 x = (c->x + p->x + 1)/2; // or (c->x + p->x)/2 to place root
  43.                                          // closer to previous child
  44.             }
  45.             if (i == nchildren/2 - 1) {
  46.                 ++childX;
  47.             }
  48.         } else {
  49.             if (i == nchildren/2) {
  50.                 x = childX;
  51.             }
  52.         }
  53.         ++childX;
  54.         ++i;
  55.  
  56.         p = c;
  57.     }
  58.  
  59.     n->x = x;
  60.     leftFront[y] = x;
  61. }
  62.  
  63. void draw(Node *n, std::vector<std::string> &screen)
  64. {
  65.     screen[n->y].resize(n->x + 1, ' ');
  66.     screen[n->y][n->x] = '*';
  67.     for (Node *c : n->children) {
  68.         draw(c, screen);
  69.     }
  70. }
  71.  
  72. void
  73. doIt(const std::string &title, Node *root)
  74. {
  75.     std::cout << title << ':' << std::endl;
  76.  
  77.     std::unordered_map<int, int> leftFront;
  78.     place(root, 0, 0, leftFront);
  79.  
  80.     std::vector<std::string> screen(5); // XXX: hardcoded
  81.     draw(root, screen);
  82.  
  83.     for (const std::string &l : screen) {
  84.         std::cout << l << std::endl;
  85.     }
  86. }
  87.  
  88. int
  89. main(void)
  90. {
  91.     {
  92.         Node n40;
  93.         Node n30;
  94.         Node n31 = { &n40 };
  95.         Node n21 = { &n30, &n31 };
  96.         Node n20;
  97.         Node n12 = { &n21 };
  98.         Node n11 = { &n20 };
  99.         Node n10;
  100.         Node n00 = { &n10, &n11, &n12 };
  101.         doIt("original tree", &n00);
  102.     }
  103.  
  104.     {
  105.         Node n40;
  106.         Node n30;
  107.         Node n31 = { &n40 };
  108.         Node n24 = { &n30, &n31 };
  109.         Node n23;
  110.         Node n22;
  111.         Node n21;
  112.         Node n20;
  113.         Node n12 = { &n24 };
  114.         Node n11 = { &n22, &n23 };
  115.         Node n10 = { &n20, &n21 };
  116.         Node n00 = { &n10, &n11, &n12 };
  117.         doIt("more complicated tree", &n00);
  118.     }
  119.  
  120.     {
  121.         Node n40;
  122.         Node n30;
  123.         Node n31 = { &n40 };
  124.         Node n24 = { &n30, &n31 };
  125.         Node n23;
  126.         Node n22;
  127.         Node n21;
  128.         Node n20;
  129.         Node n12 = { &n24 };
  130.         Node n11 = { &n22, &n23 };
  131.         Node n10 = { &n20, &n21 };
  132.         Node n00 = { &n10, &n11 };
  133.         doIt("perfect binary tree", &n00);
  134.     }
  135.  
  136.     return 0;
  137. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
original tree:
 *
***
 **
 * *
   *
more complicated tree:
    *
 *  * *
* ** **
     * *
       *
perfect binary tree:
   *
 *  *
* ** *
https://ideone.com/byATOR
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!