fork(8) download
copy 
  1. #include <iostream>
  2. #include <utility>
  3. #include <algorithm>
  4. #include <list>
  5.  
  6. namespace tree {
  7.  
  8. template<typename T>
  9. struct node
  10. {
  11.   T data;
  12.   node* l;
  13.   node* r;
  14.   node(T&& data_ = T()) : data(std::move(data_)), l(0), r(0) {}
  15. };
  16.  
  17. template<typename T>
  18. int max_depth(node<T>* n)
  19. {
  20.   if (!n) return 0;
  21.   return 1 + std::max(max_depth(n->l), max_depth(n->r));
  22. }
  23.  
  24. template<typename T>
  25. void prt(node<T>* n)
  26. {
  27.   struct node_depth
  28.   {
  29.     node<T>* n;
  30.     int lvl;
  31.     node_depth(node<T>* n_, int lvl_) : n(n_), lvl(lvl_) {}
  32.   };
  33.  
  34.   int depth = max_depth(n);
  35.  
  36.   char buf[1024];
  37.   int last_lvl = 0;
  38.   int offset = (1 << depth) - 1;
  39.  
  40.   // using a queue means we perform a breadth first iteration through the tree
  41.   std::list<node_depth> q;
  42.  
  43.   q.push_back(node_depth(n, last_lvl));
  44.   while (q.size())
  45.   {
  46.     const node_depth& nd = *q.begin();
  47.  
  48.     // moving to a new level in the tree, output a new line and calculate new offset
  49.     if (last_lvl != nd.lvl)
  50.     {
  51.       std::cout << "\n";
  52.  
  53.       last_lvl = nd.lvl;
  54.       offset = (1 << (depth - nd.lvl)) - 1;
  55.     }
  56.  
  57.     // output <offset><data><offset>
  58.     if (nd.n)
  59.       sprintf(buf, " %*s%d%*s", offset, " ", nd.n->data, offset, " ");
  60.     else
  61.       sprintf(buf, " %*s", offset << 1, " ");
  62.     std::cout << buf;
  63.  
  64.     if (nd.n)
  65.     {
  66.       q.push_back(node_depth(nd.n->l, last_lvl + 1));
  67.       q.push_back(node_depth(nd.n->r, last_lvl + 1));
  68.     }
  69.  
  70.     q.pop_front();
  71.   }
  72.   std::cout << "\n";
  73. }
  74.  
  75. }
  76.  
  77. int main()
  78. {
  79.   typedef tree::node<int> node;
  80.   node* head = new node();
  81.   head->l    = new node(1);
  82.   head->r    = new node(2);
  83.   head->l->l = new node(3);
  84.   head->l->r = new node(4);
  85.   head->r->l = new node(5);
  86.   head->r->r = new node(6);
  87.  
  88.   tree::prt(head);
  89.  
  90.   return 0;
  91. }
Success #stdin #stdout 0s 3060KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
        0       
    1       2   
  3   4   5   6
https://ideone.com/wrY8Vo
language:
C++14 (gcc 8.3)
created:
11 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!