/* call example */ std::vectorv = { 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; }
вторник, 4 августа 2015 г.
Create binary search tree from sorted array (asc order)
Подписаться на:
Комментарии к сообщению (Atom)
Комментариев нет:
Отправить комментарий