вторник, 4 августа 2015 г.

Create binary search tree from sorted array (asc order)


/* call example */
std::vector v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
treenode * root = generate_bst_tree(v);

/* implementation */
template<typename T>
treenode<T> * generate_bst_tree(const std::vector<T>& v, 
treenode<T> * node = nullptr, 
size_t from = 0, 
size_t to = 0) {
 
 treenode<T> * root = nullptr;

 if (!node) {
  if (v.size() == 0)
   return nullptr;

  root = node = new treenode();
  if (v.size() == 1) {
   root->data = v[0];
   return root;
  }
  to = v.size() - 1;
 }

 const size_t mid = (to - from) / 2 + from;
 node->data = v[mid];
 
 if ((mid - from) > 1) {
  node->left = new treenode<T>();
  generate_bst_tree(v, node->left, from, mid);
 }
 else {
  if ( from == 0 )
   node->left = new treenode<T>(v[from]);
 }

 if ((to - mid) > 1 ) {
  node->right = new treenode<T>();
  generate_bst_tree(v, node->right, mid, to);
 }
 else {
  if (to == v.size() - 1)
   node->right = new treenode<T>(v[to]);
 }

 return root;
}

Комментариев нет:

Отправить комментарий