fork download
copy 
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <iostream>
  4. #include <iterator>
  5. #include <memory>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. typedef vector<int>::const_iterator elements_iterator;
  11.  
  12. struct Tree {
  13.   const unique_ptr<Tree> left;
  14.   const int value;
  15.   const unique_ptr<Tree> right;
  16.  
  17.   Tree(unique_ptr<Tree> left, int value, unique_ptr<Tree> right)
  18.       : left(move(left)), value(value), right(move(right)) {}
  19. };
  20.  
  21. vector<int> g_height_to_size = {0, 1};
  22.  
  23. unique_ptr<Tree> Build(int height_advise, elements_iterator begin,
  24.                        elements_iterator end) {
  25.   assert(distance(begin, end) == g_height_to_size.at(height_advise));
  26.   if (height_advise == 0) {
  27.     return nullptr;
  28.   }
  29.   if (height_advise == 1) {
  30.     return make_unique<Tree>(nullptr, *begin, nullptr);
  31.   }
  32.   int left_size = g_height_to_size[height_advise - 2];
  33.   return make_unique<Tree>(
  34.       Build(height_advise - 2, begin, begin + left_size), *(begin + left_size),
  35.       Build(height_advise - 1, begin + left_size + 1, end));
  36. }
  37.  
  38. void PrintTree(const unique_ptr<Tree> &root) {
  39.   static int counter = 0;
  40.   auto handle_child = [&root](const unique_ptr<Tree> &child) {
  41.     if (child) {
  42.       cout << "  " << root->value << " -> " << child->value << ";" << endl;
  43.       PrintTree(child);
  44.     } else {
  45.       cout << "  null" << counter << " [shape=point];" << endl;
  46.       cout << "  " << root->value << " -> "
  47.            << "null" << counter << ";" << endl;
  48.       ++counter;
  49.     }
  50.   };
  51.   if (root->left || root->right) {
  52.     handle_child(root->left);
  53.     handle_child(root->right);
  54.   }
  55. }
  56.  
  57. int main() {
  58.   int n;
  59.   cin >> n;
  60.  
  61.   while (g_height_to_size.back() < n) {
  62.     g_height_to_size.push_back(g_height_to_size.back() +
  63.                                *prev(g_height_to_size.end(), 2) + 1);
  64.   }
  65.   if (g_height_to_size.back() != n) {
  66.     cerr << "Invalid N: " << n << endl;
  67.     return 1;
  68.   }
  69.   vector<int> elements(n);
  70. #if 1
  71.   for (int i = 0; i < n; ++i) {
  72.     elements[i] = i + 1;
  73.   }
  74. #else
  75.   copy_n(istream_iterator<int>(cin), n, elements.begin());
  76.   sort(elements.begin(), elements.end());
  77.   if (adjacent_find(elements.begin(), elements.end()) != elements.end()) {
  78.     cerr << "Elements must be unique" << endl;
  79.     return 1;
  80.   }
  81. #endif
  82.  
  83.   cout << "digraph fib_tree { " << endl;
  84.   PrintTree(
  85.       Build(g_height_to_size.size() - 1, elements.begin(), elements.end()));
  86.   cout << "}" << endl;
  87.  
  88.   return 0;
  89. }
  90.  
Success #stdin #stdout 0s 16080KB
comments (?)
stdin
copy 
12
stdout
copy 
digraph fib_tree { 
  5 -> 2;
  2 -> 1;
  2 -> 3;
  null0 [shape=point];
  3 -> null0;
  3 -> 4;
  5 -> 8;
  8 -> 6;
  null1 [shape=point];
  6 -> null1;
  6 -> 7;
  8 -> 10;
  10 -> 9;
  10 -> 11;
  null2 [shape=point];
  11 -> null2;
  11 -> 12;
}
https://ideone.com/sz4cRo
language:
C++14 (gcc 8.3)
created:
6 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!