Game Programming III – the third week, binary search tree part one (1)

Hello!

This week I finally managed to finalize the binary search tree that I’ve been working on. I’ve had a lot of trouble since I did not have the sense to look up tutorials on the subject even though that is usually the first thing I do. I guess I got too cocky and figured I should be able to do it all on my own pretty quick. I was wrong, and I would have saved myself a lot of pain if I had turned to tutorials from the very beginning. To my credit my way of thinking wasn’t exactly wrong, its just that I did not connect it with using methods recursively. Recursive method (or function) means a method (or function) that calls on itself.

For example, here is some code that uses recursion to count factorials:

int factorial(int number)

{

if(number == 0)

{

return 1;

}

return number*factorial(number – 1);

}

So what is a binary search tree then? Its an elementary data structure that works a bit different than the linked list I wrote about in my last three posts.  A binary search tree consists of nodes, just like a linked list. However, unlike a linked list, each node has two references instead of one. These references point to a left child and a right child. Each node that has at least one child that is not pointing to NULL is considered a parent. If a node doesn’t have any children it is considered a leaf. The left child points to a node containing data of lower value than its parent’s data, while the right child points to a node cointaing data of a higher value.

Part of the assignment was to provide the following methods with the class: insert, erase, search, size, traversal_pre_order, traversal_in_order and traversal_post_order.

The code I used for the insert method:

void Insert(T add_data)
{
Node* n = new Node;
n->data = add_data;

if (m_root == nullptr)
{
m_root = n;
std::cout << ”Data inserted”;
size++;
}
else
{
if (n->data == m_root->data)
{
std::cout << ”Data already present, aborting insert”;
}
else if (n->data data)
{
Left(n);
}
else
{
Right(n);
}
}

std::cout << ”( ” << add_data << ” )” << std::endl;
}

As you can see, it calls on two other methods, Left and Right. Here is the code for them:

void Left(Node* node)
{
if (m_root->left_child == nullptr)
{
m_root->left_child = node;
std::cout << ”Data inserted”;
size++;
}
else
{
Climb(node, m_root->left_child);
}
}

void Right(Node* node)
{
if (m_root->right_child == nullptr)
{
m_root->right_child = node;
std::cout << ”Data inserted”;
size++;
}
else
{
Climb(node, m_root->right_child);
}
}

These in turn both call in the Climb method. Here is the code for that:

void Climb(Node* add_node, Node* current)
{
m_current = current;
bool climbing = true;

while (climbing)
{
if (add_node->data == m_current->data)
{
std::cout << ”Data already present, aborting insert”;
climbing = false;
}
else if (add_node->data data)
{
if (m_current->left_child == nullptr)
{
m_current->left_child = add_node;
size++;
std::cout << ”Data inserted”;
climbing = false;
}
else
{
m_current = m_current->left_child;
}
}
else // if add_node-> data > m_current->data
{
if (m_current->right_child == nullptr)
{
m_current->right_child = add_node;
size++;
std::cout << ”Data inserted”;
climbing = false;
}
else
{
m_current = m_current->right_child;
}
}
}
}

As you’ve probably noticed, this is not the most elegant way of doing things nor the easiest. Using recursion this could have been done with much less code. However, since these were some of the methods I did before I had to turn to tutorials, and because they work, I’ve left them as is. In the next part we will look at more methods, some of which makes proper use of recursion.

To be continued…