CODEWITHSUNDEEP
c++b-tree
user12810172
user12810172

Reputation:

How do I count nodes in a B-tree?

I am struggling to count nodes in a B-tree. Here keys refer to an array of values and num_keys refers to the valid number of keys currently. How do I approach this to make it work?

int BTree::count_nodes(shared_ptr<btree> root){
  int count = 0;
  int i =0;
  if (root == NULL) {
    return 0;
  } 
  for (i = 0; i < root->num_keys; i++) {
    count +=root->keys[i];
  }
  return count;
}

Upvotes: 0

Views: 1147

Answers (1)

Anonymous1847
Anonymous1847

Reputation: 2598

Here, you can iterate over all nodes in the tree, incrementing the counter each time.

int BTree::count_nodes(shared_ptr<btree> root) {
  int count = 0;
  std::stack<shared_ptr<btree> > traversal_stack;
  traversal_stack.push(root);

  while (!traversal_stack.empty()) {
    shared_ptr<btree> top = traversal_stack.top();
    traversal_stack.pop();

    ++count;

    for (shared_ptr<btree> child : top->children) {
      traversal_stack.push(child);
    }
  }

  return count;
}

This uses depth-first search. To do breadth-first search, change the std::stack into an std::queue and use .peek() instead of .top().

Note that it may be more efficient to have each node keep track of its subtree's number of nodes, and for the counts to be updated whenever nodes move around, instead of having a function like this.

Upvotes: 1

Related Questions