I'm trying to print a b tree in level order,but it keeps on crashing. Im not sure whats the real reason but i think its crashing because of the pointers. Im trying to use a function i found online that goes through each level and puts it in a queue and prints it, but ive run into this problem.If anyone has another way of doing it please let me know.
// C++ program for B-Tree insertion
#include<iostream>
#include <queue>
using namespace std;
int ComparisonCount = 0;
// A BTree node
class BTreeNode
{
int *keys; // An array of keys
int t; // Minimum degree (defines the range for number of keys)
BTreeNode **C; // An array of child pointers
int n; // Current number of keys
bool leaf; // Is true when node is leaf. Otherwise false
public:
BTreeNode(int _t, bool _leaf); // Constructor
// A utility function to insert a new key in the subtree rooted with
// this node. The assumption is, the node must be non-full when this
// function is called
void insertNonFull(int k);
// A utility function to split the child y of this node. i is index of y in
// child array C[]. The Child y must be full when this function is called
void splitChild(int i, BTreeNode *y);
// A function to traverse all nodes in a subtree rooted with this node
void traverse();
// A function to search a key in subtree rooted with this node.
BTreeNode *search(int k); // returns NULL if k is not present.
// Make BTree friend of this so that we can access private members of this
// class in BTree functions
friend class BTree;
};
// A BTree
class BTree
{
BTreeNode *root; // Pointer to root node
int t; // Minimum degree
public:
// Constructor (Initializes tree as empty)
BTree(int _t)
{
root = NULL; t = _t;
}
// function to traverse the tree
void traverse()
{
if (root != NULL) root->traverse();
}
// function to search a key in this tree
BTreeNode* search(int k)
{
return (root == NULL) ? NULL : root->search(k);
}
// The main function that inserts a new key in this B-Tree
void insert(int k);
};
// Constructor for BTreeNode class
BTreeNode::BTreeNode(int t1, bool leaf1)
{
// Copy the given minimum degree and leaf property
t = t1;
leaf = leaf1;
// Allocate memory for maximum number of possible keys
// and child pointers
keys = new int[2 * t - 1];
C = new BTreeNode *[2 * t];
// Initialize the number of keys as 0
n = 0;
}
// Function to traverse all nodes in a subtree rooted with this node
/*void BTreeNode::traverse()
{
// There are n keys and n+1 children, travers through n keys
// and first n children
int i;
for (i = 0; i < n; i++)
{
// If this is not leaf, then before printing key[i],
// traverse the subtree rooted with child C[i].
if (leaf == false)
{
ComparisonCount++;
C[i]->traverse();
}
cout << " " << keys[i];
}
// Print the subtree rooted with last child
if (leaf == false)
{
ComparisonCount++;
C[i]->traverse();
}
}*/
// Function to search key k in subtree rooted with this node
BTreeNode *BTreeNode::search(int k)
{
// Find the first key greater than or equal to k
int i = 0;
while (i < n && k > keys[i])
i++;
// If the found key is equal to k, return this node
if (keys[i] == k)
{
ComparisonCount++;
return this;
}
// If key is not found here and this is a leaf node
if (leaf == true)
{
ComparisonCount++;
return NULL;
}
// Go to the appropriate child
return C[i]->search(k);
}
// The main function that inserts a new key in this B-Tree
void BTree::insert(int k)
{
// If tree is empty
if (root == NULL)
{
ComparisonCount++;
// Allocate memory for root
root = new BTreeNode(t, true);
root->keys[0] = k; // Insert key
root->n = 1; // Update number of keys in root
}
else // If tree is not empty
{
// If root is full, then tree grows in height
if (root->n == 2 * t - 1)
{
ComparisonCount++;
// Allocate memory for new root
BTreeNode *s = new BTreeNode(t, false);
// Make old root as child of new root
s->C[0] = root;
// Split the old root and move 1 key to the new root
s->splitChild(0, root);
// New root has two children now. Decide which of the
// two children is going to have new key
int i = 0;
if (s->keys[0] < k)
{
ComparisonCount++;
i++;
}s->C[i]->insertNonFull(k);
// Change root
root = s;
}
else // If root is not full, call insertNonFull for root
root->insertNonFull(k);
}
}
// A utility function to insert a new key in this node
// The assumption is, the node must be non-full when this
// function is called
void BTreeNode::insertNonFull(int k)
{
// Initialize index as index of rightmost element
int i = n - 1;
// If this is a leaf node
if (leaf == true)
{
ComparisonCount++;
// The following loop does two things
// a) Finds the location of new key to be inserted
// b) Moves all greater keys to one place ahead
while (i >= 0 && keys[i] > k)
{
keys[i + 1] = keys[i];
i--;
}
// Insert the new key at found location
keys[i + 1] = k;
n = n + 1;
}
else // If this node is not leaf
{
// Find the child which is going to have the new key
while (i >= 0 && keys[i] > k)
i--;
// See if the found child is full
if (C[i + 1]->n == 2 * t - 1)
{
ComparisonCount++;
// If the child is full, then split it
splitChild(i + 1, C[i + 1]);
// After split, the middle key of C[i] goes up and
// C[i] is splitted into two. See which of the two
// is going to have the new key
if (keys[i + 1] < k)
i++;
}
C[i + 1]->insertNonFull(k);
}
}
// A utility function to split the child y of this node
// Note that y must be full when this function is called
void BTreeNode::splitChild(int i, BTreeNode *y)
{
// Create a new node which is going to store (t-1) keys
// of y
BTreeNode *z = new BTreeNode(y->t, y->leaf);
z->n = t - 1;
// Copy the last (t-1) keys of y to z
for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];
// Copy the last t children of y to z
if (y->leaf == false)
{
ComparisonCount++;
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}
// Reduce the number of keys in y
y->n = t - 1;
// Since this node is going to have a new child,
// create space of new child
for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];
// Link the new child to this node
C[i + 1] = z;
// A key of y will move to this node. Find location of
// new key and move all greater keys one space ahead
for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];
// Copy the middle key of y to this node
keys[i] = y->keys[t - 1];
// Increment count of keys in this node
n = n + 1;
}
void BTreeNode::traverse()
{
std::queue<BTreeNode*> queue;
queue.push(this);
while (!queue.empty())
{
BTreeNode* current = queue.front();
queue.pop();
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
queue.push(current->C[i]);
cout << " " << current->keys[i] << endl;
}
if (leaf == false)
queue.push(current->C[i]);
}
}
// Driver program to test above functions
int main()
{
BTree t(4); // A B-Tree with minium degree 4
srand(29324);
for (int i = 0; i<200; i++)
{
int p = rand() % 10000;
t.insert(p);
}
cout << "Traversal of the constucted tree is ";
t.traverse();
int k = 6;
(t.search(k) != NULL) ? cout << "\nPresent" : cout << "\nNot Present";
k = 28;
(t.search(k) != NULL) ? cout << "\nPresent" : cout << "\nNot Present";
cout << "There are " << ComparisonCount << " comparison." << endl;
system("pause");
return 0;
}
Your traversal code uses the field values for this as though they were the values for the current node in the loop body.
You need to stick current-> in front of the member references in the loop body like this (in the lines marked with "//*"):
while (!queue.empty())
{
BTreeNode* current = queue.front();
queue.pop();
int i;
for (i = 0; i < current->n; i++) //*
{
if (current->leaf == false) //*
queue.push(current->C[i]);
cout << " " << current->keys[i] << endl;
}
if (current->leaf == false) //*
queue.push(current->C[i]);
}
This is a strong indicator that all the stuff qualified with current-> in reality wants to live in a function where it is this and thus does not need to be named explicitly.
Your code is better organised and more pleasant to read than most debug requests we get here, but it is still fairly brittle and it contains quite a few smelly bits like if (current->leaf == false) instead of if (not current->is_leaf).
You may want to post it over on Code Review when you have got it into working shape; I'm certain that the experienced coders hanging out there can give you lots of valuable advice on how to improve your code.
In order to ease prototyping and development I would strongly advise the following:
std::vector<> instead of naked arrays during the prototype phaseassert() for documenting - and checking - local invariants /Wall /Wextra and clean it up so that it always compiles without warningsAlso, don't use int indiscriminately; the basic type for things that cannot become negative is unsigned (node degree, current key count etc.).
P.S.: it would be easier to build a conforming B-tree by pinning the order on the number of keys (i.e. number of keys can vary between K and 2*K for some K). Pinning the order on the number of pointers makes things more difficult, and one consequence is that the number of keys for 'order' 2 (where a node is allowed to have between 2 and 4 pointers) can vary between 1 and 3. For most folks dealing with B-trees that will be a rather unexpected sight!