воскресенье, 23 августа 2015 г.

Find node in a binary search tree


template<typename T>
treenode<T> * find_node_by_data(treenode<T> * root, const T& value) {
 treenode<T> * node = root;
 while (node) {
  if (node->data == value)
   return node;
  if (value > node->data)
   node = node->right;
  else
   node = node->left;
 }
 return nullptr;
}

вторник, 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;
}

Print binary tree by levels (breadth first)


template<typename T>
struct treenode {
 treenode<T> * left, *right, *parent;
 T data;
 treenode() : left(nullptr), right(nullptr), parent(nullptr) {}
 treenode(const T& param) 
: left(nullptr), right(nullptr), parent(nullptr), data(param) {}
};

template<typename T>
void print_tree(const treenode * root) {
 if (!root) {
  std::cout << "EMPTY\r\n";
  return;
 }
 
 std::queue<const treenode<T> * > q;
 q.push(root);

 const treenode<T>* node;
 size_t sz = 0; 
 
 while ((sz = q.size()) > 0) {
  for (size_t i = 0; i < sz; ++i) {
   node = q.front();
   std::cout  << node->data  << " ";
   q.pop();
   if (node->left)
    q.push(node->left);
   if (node->right)
    q.push(node->right);
  }
  std::cout  << std::endl;
 }
}