You need to store information in a tree structure, where the left node is less than its parent node, and the right node is greater than or equal to (in cases where the tree can contain duplicates) its parent. The stored information must be easily inserted into the tree, removed from the tree, and found within the tree.
Each node must be an object that inherits from the
IComparable
interface. This means that every node that wishes to be included in
the binary tree must implement the
CompareTo
method. This
method will allow one node to determine whether it is less than,
greater than, or equal to another node.
Use the following BinaryTree
class, which contains
all of the nodes in a binary tree and lets you traverse
it:
using System; using System.Collections; public class BinaryTree { public BinaryTree( ) {} public BinaryTree(IComparable value, int index) { BinaryTreeNode node = new BinaryTreeNode(value, index); root = node; counter = 1; } // Use this .ctor when you need to flatten this tree (see recipe 9.15) public BinaryTree(IComparable value) { BinaryTreeNode node = new BinaryTreeNode(value); root = node; counter = 1; } protected int counter = 0; // Number of nodes in tree protected BinaryTreeNode root = null; // Pointer to root node in this tree public void AddNode(IComparable value, int index) { BinaryTreeNode node = new BinaryTreeNode(value, index); ++counter; if (root == null) { root = node; } else { root.AddNode(node); } } // Use this method to add a node // when you need to flatten this tree (see recipe 9.15) public int AddNode(IComparable value) { BinaryTreeNode node = new BinaryTreeNode(value); ++counter; if (root == null) { root = node; } else { root.AddNode(node); } return (counter - 1); } public BinaryTreeNode SearchDepthFirst(IComparable value) { return (root.DepthFirstSearch(value)); } public void Print( ) { root.PrintDepthFirst( ); } public BinaryTreeNode GetRoot( ) { return (root); } public int TreeSize { get {return (counter);} } }
The
BinaryTreeNode
encapsulates the data and behavior
of a single node in the binary tree:
public class BinaryTreeNode { public BinaryTreeNode( ) {} public BinaryTreeNode(IComparable value) { nodeValue = value; } // These 2 ctors Added to allow tree to be flattened public BinaryTreeNode(int index) { nodeIndex = index; } public BinaryTreeNode(IComparable value, int index) { nodeValue = value; nodeIndex = index; } protected int nodeIndex = 0; // Added to allow tree to be flattened protected IComparable nodeValue = null; protected BinaryTreeNode leftNode = null; // leftNode.Value < Value protected BinaryTreeNode rightNode = null; // rightNode.Value >= Value public int NumOfChildren { get {return (CountChildren( ));} } public int CountChildren( ) { int currCount = 0; if (leftNode != null) { ++currCount; currCount += leftNode.CountChildren( ); } if (rightNode != null) { ++currCount; currCount += rightNode.CountChildren( ); } return (currCount); } public int Index { get {return (nodeIndex);} } public BinaryTreeNode Left { get {return (leftNode);} } public BinaryTreeNode Right { get {return (rightNode);} } public IComparable GetValue { get {return (nodeValue);} } public void AddNode(BinaryTreeNode node) { if (node.nodeValue.CompareTo(nodeValue) < 0) { if (leftNode == null) { leftNode = node; } else { leftNode.AddNode(node); } } else if (node.nodeValue.CompareTo(nodeValue) >= 0) { if (rightNode == null) { rightNode = node; } else { rightNode.AddNode(node); } } } public bool AddUniqueNode(BinaryTreeNode node) { bool isUnique = true; if (node.nodeValue.CompareTo(nodeValue) < 0) { if (leftNode == null) { leftNode = node; } else { leftNode.AddNode(node); } } else if (node.nodeValue.CompareTo(nodeValue) > 0) { if (rightNode == null) { rightNode = node; } else { rightNode.AddNode(node); } } else //node.nodeValue.CompareTo(nodeValue) = 0 { isUnique = false; // Could throw exception here as well... } return (isUnique); } public BinaryTreeNode DepthFirstSearch(IComparable targetObj) { // NOTE: foo.CompareTo(bar) == -1 --> (foo < bar) BinaryTreeNode retObj = null; int comparisonResult = targetObj.CompareTo(nodeValue); if (comparisonResult == 0) { retObj = this; } else if (comparisonResult > 0) { if (rightNode != null) { retObj = rightNode.DepthFirstSearch(targetObj); } } else if (comparisonResult < 0) { if (leftNode != null) { retObj = leftNode.DepthFirstSearch(targetObj); } } return (retObj); } public void PrintDepthFirst( ) { if (leftNode != null) { leftNode.PrintDepthFirst( ); } Console.WriteLine(this.nodeValue.ToString( )); try { Console.WriteLine(" Contains Left: " + leftNode.nodeValue.ToString( )); } catch { Console.WriteLine(" Contains Left: NULL"); } try { Console.WriteLine(" Contains Right: " + rightNode.nodeValue.ToString( )); } catch { Console.WriteLine(" Contains Right: NULL"); } if (rightNode != null) { rightNode.PrintDepthFirst( ); } } public void RemoveLeftNode( ) { leftNode = null; } public void RemoveRightNode( ) { rightNode = null; } }
The methods defined in Table 10-4 are of particular
interest to using a BinaryTree
object.
Table 10-4. Members of the BinaryTree class
The methods defined in Table 10-5 are of particular
interest to using a BinaryTreeNode
object.
Table 10-5. Members of the BinaryTreeNode class
The following code illustrates the use of the
BinaryTree
and BinaryTreeNode
classes when creating and using a binary tree:
public static void TestBinaryTree( ) { BinaryTree tree = new BinaryTree("d"); tree.AddNode("a"); tree.AddNode("b"); tree.AddNode("f"); tree.AddNode("e"); tree.AddNode("c"); tree.AddNode("g"); tree.Print( ); tree.Print( ); Console.WriteLine("tree.TreeSize: " + tree.TreeSize); Console.WriteLine("tree.GetRoot( ).DepthFirstSearch(a).NumOfChildren: " + tree.GetRoot( ).DepthFirstSearch("b").NumOfChildren); Console.WriteLine("tree.GetRoot( ).DepthFirstSearch(a).NumOfChildren: " + tree.GetRoot( ).DepthFirstSearch("a").NumOfChildren); Console.WriteLine("tree.GetRoot( ).DepthFirstSearch(g).NumOfChildren: " + tree.GetRoot( ).DepthFirstSearch("g").NumOfChildren); Console.WriteLine("tree.SearchDepthFirst(a): " + tree.SearchDepthFirst("a").GetValue.ToString( )); Console.WriteLine("tree.SearchDepthFirst(b): " + tree.SearchDepthFirst("b").GetValue.ToString( )); Console.WriteLine("tree.SearchDepthFirst(c): " + tree.SearchDepthFirst("c").GetValue.ToString( )); Console.WriteLine("tree.SearchDepthFirst(d): " + tree.SearchDepthFirst("d").GetValue.ToString( )); Console.WriteLine("tree.SearchDepthFirst(e): " + tree.SearchDepthFirst("e").GetValue.ToString( )); Console.WriteLine("tree.SearchDepthFirst(f): " + tree.SearchDepthFirst("f").GetValue.ToString( )); tree.GetRoot( ).RemoveLeftNode( ); tree.Print( ); tree.GetRoot( ).RemoveRightNode( ); tree.Print( ); }
Trees are data structures where each node has exactly one parent and possibly many children. The root of the tree is a single node that branches out into one or more child nodes. A node is the part of the tree structure that contains data and contains the branches (or in more concrete terms, references) to its children node(s).
A tree can be used for many things, such as to represent a management hierarchy with the president of the company at the root node and the various vice-presidents as child nodes of the president. The vice-presidents may have managers as child nodes, and so on. A tree can be used to make decisions, where each node of the tree contains a question and the answer given depends on which branch is taken to a child node. The tree described in this recipe is called a binary tree. A binary tree can have zero, one, or two child nodes for every node in the tree. A binary tree node can never have more than two child nodes; this is where this type of tree gets its name. (There are other types of trees. For instance, the n-ary tree can have zero to n nodes for each node in the tree. This type of tree is defined in Recipe 10.7.)
A binary tree is very useful for storing objects and then efficiently searching for those objects. The following algorithm is used to store objects in a binary tree:
Start at the root node
Is this node free?
If yes, add the object to this node, and we are done.
If no, continue.
Is the object to be added to the tree less than
(“less than” is determined by the
IComparable.CompareTo
method of the node being
added) the current node?
If yes, follow the branch to the node on the left side of the current node, and go to step 2.
If no, follow the branch to the node of the right side of the current node, and go to step 2.
Basically, this algorithm states that the node to the left of the current node contains an object or value less than the current node, and the node to the right of the current node contains an object or value greater than (or equal to, if the binary tree can contain duplicates) the current node.
Searching for an object in a tree is easy. Just start at the root and ask yourself, “Is the object I am searching for less than the current node’s object?” If it is, follow the left branch to the next node in the tree. If it is not, check the current node to determine whether it contains the object you are searching for. If this is still not the correct object, continue down the right branch to the next node. When you get to the next node, start the process over again.
The binary tree used in this recipe is made up of two classes.
The
BinaryTree
class is not a part of the actual tree;
rather, it acts as a starting point from which we can create a tree,
add nodes to it, search the tree for items, and retrieve the root
node to perform other actions.
The
second class, BinaryTreeNode
, is the heart of the
binary tree and represents a single node in the tree. This class
contains all the members that are required to create and work with a
binary tree.
The BinaryTreeNode
class contains a protected
field, nodeValue
, that contains an object
implementing the IComparable
interface. This
structure allows us to perform searches and add nodes in the correct
location in the tree. The Compare
method of the
IComparable
interface is used in searching and
adding methods to determine whether we need to follow the left or
right branch. See the AddNode
,
AddUniqueNode
, and
DepthFirstSearch
methods to see this in action.
There are two
methods to add nodes to the tree, AddNode
and
AddUniqueNode
. The AddNode
method allows duplicates to be introduced to the tree, whereas the
AddUniqueNode
allows only unique nodes to be
added.
The
DepthFirstSearch
method allows the tree to be searched
by first checking the current node to see whether it contains the
value searched for; if not, recursion is used to check the left and
then the right node. If no matching value is found in any node, this
method returns null
.
It is interesting to note that even though the
BinaryTree
class is provided to create and manage
the tree of BinaryTreeNode
objects, we could
merely use the BinaryTreeNode
class as long as we
keep track of the root node ourselves. The following code creates and
manages the tree without the use of the BinaryTree
class:
public static void TestManagedTreeWithNoBinaryTreeClass( ) { // Create the root node BinaryTreeNode topLevel = new BinaryTreeNode("d"); // Create all nodes that will be added to the tree BinaryTreeNode one = new BinaryTreeNode("b"); BinaryTreeNode two = new BinaryTreeNode("c"); BinaryTreeNode three = new BinaryTreeNode("a"); BinaryTreeNode four = new BinaryTreeNode("e"); BinaryTreeNode five = new BinaryTreeNode("f"); BinaryTreeNode six = new BinaryTreeNode("g"); // Add nodes to tree through the root topLevel.AddNode(three); topLevel.AddNode(one); topLevel.AddNode(five); topLevel.AddNode(four); topLevel.AddNode(two); topLevel.AddNode(six); // Print the tree starting at the root node topLevel.PrintDepthFirst( ); // Print the tree starting at node 'Three' three.PrintDepthFirst( ); // Display the number of child nodes of various nodes in the tree Console.WriteLine("topLevel.NumOfChildren: " + topLevel.NumOfChildren); Console.WriteLine("one.NumOfChildren: " + one.NumOfChildren); Console.WriteLine("three.NumOfChildren: " + three.NumOfChildren); Console.WriteLine("six.NumOfChildren: " + six.NumOfChildren); // Search the tree using the depth-first searching method Console.WriteLine("topLevel.DepthFirstSearch(a): " + topLevel.DepthFirstSearch("a").GetValue.ToString( )); Console.WriteLine("topLevel.DepthFirstSearch(b): " + topLevel.DepthFirstSearch("b").GetValue.ToString( )); Console.WriteLine("topLevel.DepthFirstSearch(c): " + topLevel.DepthFirstSearch("c").GetValue.ToString( )); Console.WriteLine("topLevel.DepthFirstSearch(d): " + topLevel.DepthFirstSearch("d").GetValue.ToString( )); Console.WriteLine("topLevel.DepthFirstSearch(e): " + topLevel.DepthFirstSearch("e").GetValue.ToString( )); Console.WriteLine("topLevel.DepthFirstSearch(f): " + topLevel.DepthFirstSearch("f").GetValue.ToString( )); // Remove the left child node from the root node and display the entire tree topLevel.RemoveLeftNode( ); topLevel.PrintDepthFirst( ); // Remove all nodes from the tree except for the root and display the tree topLevel.RemoveRightNode( ); topLevel.PrintDepthFirst( ); }