Binary Tree and Binary Search Tree
From XNAWiki
Foreword: this is not binary space partitioning, though that spatial partition scheme is based around this stuff. A binary tree is a very efficient data structures to use when your data set can easily be divided into a true-false hierarchy of choices.
A binary node stores the following information:
- Data that the node represents.
- Reference to the node that is the left child.
- Reference to the node that is the right child.
/// <summary>
/// A class which represents a binary node, which is a node that can have two child nodes,
/// which in turn can have two child nodes, and so on. Each node is capable of storing a
/// user data object, which could be anything from a number to a spatial node.
/// </summary>
/// <typeparam name="UserType">Type of data to store in this node.</typeparam>
public class BinaryNode<UserType> : IDisposable
{
UserType m_userData;
internal BinaryNode<UserType> m_left, m_right;
/// <summary>
/// User data stored in this node, this could be anything from a number, to a spatial node.
/// </summary>
public UserType UserData { get { return m_userData; } set { m_userData = value; } }
/// <summary>
/// Gets the left child of this node.
/// </summary>
public BinaryNode<UserType> Left { get { return m_left; } }
/// <summary>
/// Gets the right child of this node.
/// </summary>
public BinaryNode<UserType> Right { get { return m_right; } }
/// <summary>
/// Gets a value indicating whether this node has child nodes.
/// </summary>
public bool IsLeaf { get { return (m_left == null && m_right == null); } }
/// <summary>
/// Create a new binary node.
/// </summary>
/// <param name="userData">Optional data to store in the node.</param>
public BinaryNode(UserType userData = default(UserType))
{
m_userData = userData;
}
#region IDisposable Members
~BinaryNode() { Dispose(false); }
/// <summary>
/// Disposes of this node and it's user data.
/// </summary>
public void Dispose()
{
Dispose(true);
GC.SuppressFinalize(this);
}
/// <summary>
/// Called when this node is being disposed of.
/// </summary>
/// <param name="disposing">Should managed resources be disposed of as well.</param>
protected virtual void Dispose(bool disposing)
{
if (disposing)
{
IDisposable disposable = m_userData as IDisposable;
if (disposable != null)
disposable.Dispose();
m_userData = null;
}
}
#endregion
}A binary tree exposes the following information:
- Root node that the tree begins at.
- Height of the tree, which represents the number of nodes on the longest path from outer most (root) to inner most.
- Number of nodes in the tree.
- Number of leaves in the tree (nodes without children).
A binary tree can be traversed in one of three ways:
- Inorder: move into the left sub-tree, visit the node, move into the right sub-tree.
- Preorder: visit the node, move into the left sub-tree, move into the right sub-tree.
- Postorder: move into the left sub-tree, move into the right sub-tree, visit the node.
/// <summary>
/// Determines the pattern used to visit nodes in a binary tree.
/// </summary>
public enum BinaryTreeTraversal
{
/// <summary>
/// Move into the left sub-tree.
/// Visit the node.
/// Move into the right sub-tree.
/// </summary>
Inorder = 0,
/// <summary>
/// Visit the node.
/// Move into the left sub-tree.
/// Move into the right sub-tree.
/// </summary>
Preorder,
/// <summary>
/// Move into the left sub-tree.
/// Move into the right sub-tree.
/// Visit the node.
/// </summary>
Postorder
}
/// <summary>
/// Delegate used when visiting a node in the binary tree.
/// </summary>
/// <typeparam name="UserType">Type of data stored in the nodes.</typeparam>
/// <param name="node">The node being visited.</param>
/// <param name="cancel">True if the traversal should stop.</param>
public delegate void BinaryTreeVisitDelegate<UserType>(BinaryNode<UserType> node, ref bool cancel);
/// <summary>
///
/// </summary>
/// <typeparam name="UserType">Type of data stored in the nodes.</typeparam>
public class BinaryTree<UserType> : IDisposable
{
protected BinaryNode<UserType> m_root;
/// <summary>
/// Number of nodes traversed from the root to the deepest part of the tree.
/// </summary>
public int Height { get { return GetHeight(m_root); } }
/// <summary>
/// Number of nodes in the tree.
/// </summary>
public int NodeCount { get { return GetNodeCount(m_root); } }
/// <summary>
/// Number of nodes without children in the tree.
/// </summary>
public int LeafCount { get { return GetLeafCount(m_root); } }
/// <summary>
/// Does the tree even have any nodes?
/// </summary>
public bool IsEmpty { get { return (m_root == null); } }
/// <summary>
/// Create a new binary tree.
/// </summary>
/// <param name="cloneSource">A binary tree to copy into this tree.</param>
public BinaryTree(BinaryTree<UserType> cloneSource = null)
{
m_root = null;
if (cloneSource != null)
CopyTree(out m_root, cloneSource.m_root);
}
/// <summary>
/// Traverses the binary tree calling a visit method on each node.
/// </summary>
/// <param name="visitMethod">A method to be called on each visited node.</param>
/// <param name="traversalMode">Mode of traversal to perform.</param>
public void Traverse(BinaryTreeVisitDelegate<UserType> visitMethod,
BinaryTreeTraversal traversalMode = BinaryTreeTraversal.Inorder)
{
if (visitMethod != null)
{
bool cancel = false;
if (traversalMode == BinaryTreeTraversal.Inorder)
TraverseInorder(visitMethod, ref cancel, m_root);
else if (traversalMode == BinaryTreeTraversal.Preorder)
TraversePreorder(visitMethod, ref cancel, m_root);
else if (traversalMode == BinaryTreeTraversal.Postorder)
TraversePostorder(visitMethod, ref cancel, m_root);
}
}
void CopyTree(out BinaryNode<UserType> copyRoot, BinaryNode<UserType> otherRoot)
{
copyRoot = null;
if (otherRoot != null)
{
copyRoot = new BinaryNode<UserType>(otherRoot.UserData);
CopyTree(out copyRoot.m_left, otherRoot.m_left);
CopyTree(out copyRoot.m_right, otherRoot.m_right);
}
}
void TraverseInorder(BinaryTreeVisitDelegate<UserType> visitMethod, ref bool cancel,
BinaryNode<UserType> node)
{
if (node != null && !cancel)
{
TraverseInorder(visitMethod, ref cancel, node.Left);
if (!cancel) visitMethod(node, ref cancel);
TraverseInorder(visitMethod, ref cancel, node.Right);
}
}
void TraversePreorder(BinaryTreeVisitDelegate<UserType> visitMethod, ref bool cancel,
BinaryNode<UserType> node)
{
if (node != null && !cancel)
{
if (!cancel) visitMethod(node, ref cancel);
TraversePreorder(visitMethod, ref cancel, node.Left);
TraversePreorder(visitMethod, ref cancel, node.Right);
}
}
void TraversePostorder(BinaryTreeVisitDelegate<UserType> visitMethod, ref bool cancel,
BinaryNode<UserType> node)
{
if (node != null && !cancel)
{
TraversePostorder(visitMethod, ref cancel, node.Left);
TraversePostorder(visitMethod, ref cancel, node.Right);
if (!cancel) visitMethod(node, ref cancel);
}
}
int GetHeight(BinaryNode<UserType> node)
{
if (node != null)
return 1 + Math.Max(GetHeight(node.m_left), GetHeight(node.m_right));
return 0;
}
int GetNodeCount(BinaryNode<UserType> node)
{
if (node != null)
return 1 + GetNodeCount(node.m_left) + GetNodeCount(node.m_right);
return 0;
}
int GetLeafCount(BinaryNode<UserType> node)
{
if (node != null)
return GetLeafCount(node.m_left) + GetLeafCount(node.m_right);
return 1;
}
#region IDisposable Members
~BinaryTree() { Dispose(false); }
/// <summary>
/// Dispose of this binary tree, it's nodes and their data.
/// </summary>
public void Dispose()
{
Dispose(true);
GC.SuppressFinalize(this);
}
/// <summary>
/// Called when this binary tree is being disposed of.
/// </summary>
/// <param name="disposing">Should managed resources be disposed of as well.</param>
protected virtual void Dispose(bool disposing)
{
if (disposing)
Dispose(ref m_root);
}
// recursive disposal function, pre-order traversal
void Dispose(ref BinaryNode<UserType> node)
{
if (node != null)
{
Dispose(ref node.m_left);
Dispose(ref node.m_right);
node.Dispose();
node = null;
}
}
#endregion
}A binary search tree is a special type of binary tree which allows for inserting/removing data from the tree, as well as checking if a specific piece of data exists in the tree. This is implemented using an IComparer interface to handle the search routines.
/// <summary>
/// A binary tree which assist with inserting, removing, and finding whether data exist in
/// the tree.
/// </summary>
/// <typeparam name="UserType">Type of data stored in the binary nodes.</typeparam>
public class BinarySearchTree<UserType> : BinaryTree<UserType>
{
IComparer<UserType> m_comparer;
/// <summary>
/// Create a new binary search tree.
/// </summary>
/// <param name="comparer">A comparer to use for determining which nodes are greater/less
/// than other nodes.</param>
/// <param name="cloneSource">A binary tree to copy into this tree.</param>
public BinarySearchTree(IComparer<UserType> comparer,
BinaryTree<UserType> cloneSource = null)
: base(cloneSource)
{
if (m_comparer == null)
throw new ArgumentNullException("comparer");
m_comparer = comparer;
}
/// <summary>
/// Checks whether the specified item exist in this binary tree.
/// </summary>
/// <param name="searchItem"></param>
/// <returns>True if the item exist in this tree; false if it does not.</returns>
public bool Contains(UserType searchItem)
{
BinaryNode<UserType> current = m_root;
bool found = false;
while (current != null && !found)
{
int comprand = m_comparer.Compare(current.UserData, searchItem);
if (comprand > 0)
current = current.m_left;
else if (comprand < 0)
current = current.m_right;
else
found = true;
}
return found;
}
/// <summary>
/// Inserts an item into this binary tree.
/// </summary>
/// <param name="insertItem"></param>
public void Insert(UserType insertItem)
{
if (m_root == null)
m_root = new BinaryNode<UserType>(insertItem);
else
{
BinaryNode<UserType> current = m_root;
BinaryNode<UserType> trailCurrent = null;
int comparand = 0;
while (current != null)
{
trailCurrent = current;
comparand = m_comparer.Compare(current.UserData, insertItem);
if (comparand == 0)
throw new InvalidOperationException(
"The item being inserted already exist in the binary search tree.");
else
current = (comparand > 0) ? current.m_left : current.m_right;
}
comparand = m_comparer.Compare(trailCurrent.UserData, insertItem);
if (comparand > 0)
trailCurrent.m_left = new BinaryNode<UserType>(insertItem);
else
trailCurrent.m_right = new BinaryNode<UserType>(insertItem);
}
}
/// <summary>
/// Removes an itemf rom this binary tree.
/// </summary>
/// <param name="removeItem"></param>
public bool Remove(UserType removeItem)
{
if (m_root != null)
{
BinaryNode<UserType> current = m_root;
BinaryNode<UserType> trailCurrent = m_root;
bool found = false;
int comparand = 0;
while (current != null && !found)
{
comparand = m_comparer.Compare(current.UserData, removeItem);
if (comparand == 0)
found = true;
else
{
trailCurrent = current;
if (comparand > 0)
current = current.m_left;
else
current = current.m_right;
}
}
if (current != null && found)
{
if (current == m_root)
RemoveFromTree(ref m_root);
else
{
comparand = m_comparer.Compare(trailCurrent.UserData, removeItem);
if (comparand > 0)
RemoveFromTree(ref trailCurrent.m_left);
else
RemoveFromTree(ref trailCurrent.m_right);
}
}
return found;
}
return false;
}
void RemoveFromTree(ref BinaryNode<UserType> node)
{
if (node != null)
{
BinaryNode<UserType> temp = node;
if (node.m_left == null && node.m_right == null)
{
node = null;
temp.Dispose();
}
else if (node.m_left == null)
{
node = temp.m_right;
temp.Dispose();
}
else if (node.m_right == null)
{
node = temp.m_left;
temp.Dispose();
}
else
{
BinaryNode<UserType> current = node.m_left;
BinaryNode<UserType> trailCurrent = null;
while (current.m_right != null)
{
trailCurrent = current;
current = current.m_right;
}
node.UserData = current.UserData;
if (trailCurrent == null)
node.m_left = current.m_left;
else
trailCurrent.m_right = current.m_left;
current.Dispose();
}
}
}
}