Game Development Reference
In-Depth Information
4
2
5
1
3
7
Figure 16-1.
A binary search tree
The binary search tree stores the tree in a sorted order to make it a very efficient structure when
looking up nodes. The
head
node of the tree in Figure
16-1
stores the value 4. If we were looking
for the node that stores the value 2, we would begin by comparing 2 against the value at the head,
which is 4. If our search value is equal to the current node, we have found our value. If it is lower we
move to the left node; if it is higher we move to the right node. As 2 is less than 4, in our example
we would move to the left node. We would then repeat this process at the new node. We compare
first to the value of the node, and 2 equals 2, so we know that we have found the node we were
searching for.
The process of repeating the same operation over and over like this is known as
recursion.
We
generally implement recursive algorithms using functions that call themselves. Listing 16-7 shows an
implementation of a simple
TreeNode
class that can be used to recursively search a binary tree structure.
Listing 16-7. A simple
TreeNode
class TreeNode
{
private:
int m_value;
TreeNode* m_pLeft = nullptr;
TreeNode* m_pRight = nullptr;
public:
TreeNode(int value)
: m_value{value}
{}
TreeNode* Find(int searchValue)
{
TreeNode* pResult = nullptr;
if (m_value == searchValue)
{
pResult = this;
}
else if (m_pLeft != nullptr && m_value > searchValue)
{
pResult = m_pLeft->Find(searchValue);
}
else if (m_pRight != nullptr && m_value < searchValue)
