Binary Trees
Binary Tree Searching: Improving Search Performance with Sentinels
Thu, 06/08/2006 - 07:29 — tekpoolA normal search across a BST (Binary Search Tree) would look like this
bool BinaryTree::Search (int data )
{
Node *current = this->root;
while ( current != NULL )
{
if (current->data < data)
{
current = current->left;
}
else if (current->data > data)
{
current = current->right;
}
else if ( current->data == data )
{
return true;
}
}
return false;
}
Binary Tree Traversal: Breadth First aka Width First aka Level Order
Thu, 06/01/2006 - 07:07 — tekpoolBinary Tree Traversal: Breadth First aka Width First aka Level Order
This is the lesser know of the different kinds of binary tree traversals. Most beginner books and articles only cover the depth first searches. Breadth first traversals are an extremely important tool when working with Binary Trees. The idea is pretty nifty. Basically you work with a Queue, and push the root node into the Queue. Then do the following until you have visited all nodes in the tree.
