Recipe 11.6. Creating a Binary Tree Problem 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 in which 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. Solution To implement a binary tree of the type described in the Problem statement, each node must be an object that inherits from the IComparable<T> 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 BinaryTree<T> class shown in Example 11-10, which contains all of the nodes in a binary tree and lets you traverse it. Example 11-10. Generic BinaryTree class using System; using System.Collections; using System.Collections.Generic; public class BinaryTree<T> : IEnumerable<T> where T: IComparable<T> { public BinaryTree( ) {} public BinaryTree(T value) { BinaryTreeNode<T> node = new BinaryTreeNode<T>(value); root = node; counter = 1; } protected int counter = 0; // Number of nodes in tree protected BinaryTreeNode<T> root = null; // Pointer to root node in this tree public void AddNode(T value) { BinaryTreeNode<T> node = new BinaryTreeNode<T>(value); ++counter; if (root == null) { root = node; } else { root.AddNode(node); } } public BinaryTreeNode<T> SearchDepthFirst(T value) { return (root.DepthFirstSearch(value)); } public void Print( ) { root.PrintDepthFirst( ); } public BinaryTreeNode<T> Root { get {return (root);} } public int Count { get {return (counter);} } IEnumerator<T> System.Collections.Generic.IEnumerable<T>.GetEnumerator() { List<T> nodes = new List<T>(); nodes = root.IterateDepthFirst(); nodes.Add(root.Value); foreach (T t in nodes) yield return (t); } IEnumerator System.Collections.IEnumerable.GetEnumerator() { throw (new NotSupportedException("This operation is not " + "supported use the GetEnumerator() that returns an IEnumerator<T>.")); } }
|
The BinaryTreeNode<T> shown in Example 11-11 encapsulates the data and behavior of a single node in the binary tree. Example 11-11. Generic BinaryTreeNode class public class BinaryTreeNode<T> where T: IComparable<T> { public BinaryTreeNode( ) {} public BinaryTreeNode(T value) { nodeValue = value; } protected T nodeValue = default(T); protected BinaryTreeNode<T> leftNode = null; // leftNode.nodeValue < Value protected BinaryTreeNode<T> rightNode = null; // rightNode.nodeValue >= Value public int Children { get { int currCount = 0; if (leftNode != null) { ++currCount; currCount += leftNode.Children(); } if (rightNode != null) { ++currCount; currCount += rightNode.Children(); } return (currCount); } } public BinaryTreeNode<T> Left { get {return (leftNode);} } public BinaryTreeNode<T> Right { get {return (rightNode);} } public T Value { get {return (nodeValue);} } public void AddNode(BinaryTreeNode<T> 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<T> 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<T> DepthFirstSearch(T targetObj) { // NOTE: foo.CompareTo(bar) == -1 --> (foo < bar) BinaryTreeNode<T> 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()); if (leftNode != null) { Console.WriteLine("\tContains Left: " + leftNode.nodeValue.ToString()); } else { Console.WriteLine("\tContains Left: NULL"); } if (rightNode != null) { Console.WriteLine("\tContains Right: " + rightNode.nodeValue.ToString()); } else { Console.WriteLine("\tContains Right: NULL"); } if (rightNode != null) { rightNode.PrintDepthFirst(); } } public List<T> IterateDepthFirst() { List<T> tempList = new List<T>(); if (leftNode != null) { tempList.AddRange(leftNode.IterateDepthFirst()); } if (leftNode != null) { tempList.Add(leftNode.nodeValue); } if (rightNode != null) { tempList.Add(rightNode.nodeValue); } if (rightNode != null) { tempList.AddRange(rightNode.IterateDepthFirst()); } return (tempList); } public void RemoveLeftNode() { leftNode = null; } public void RemoveRightNode() { rightNode = null; } }
|
The methods defined in Table 11-4 are of particular interest to using a BinaryTree<T> object. Table 11-4. Members of the BinaryTree<T> classMember | Description |
|---|
Overloaded constructor | This constructor creates a BinaryTree<T> object with a root node. Its syntax is: BinaryTree(T value)
where value is the root node for the tree. Note that this tree may not be flattened. | AddNode method | Adds a node to the tree. Its syntax is: AddNode(T value, int id)
where value is the object to be added and id is the node index. Use this method if the tree will be flattened. | AddNode method | Adds a node to the tree. Its syntax is: AddNode(T value)
where value is the object to be added. Use this method if the tree will not be flattened. | SearchDepthFirst method | Searches for and returns a BinaryTreeNode<T> object in the tree, if one exists. This method searches the depth of the tree first. Its syntax is: SearchDepthFirst(T value)
where value is the object to be found in the tree. | Print method | Displays the tree in depth-first format. Its syntax is: Print( )
| Root property | Returns the BinaryTreeNode<T> object that is the root of the tree. Its syntax is: Root
| treeSize property | A read-only property that gets the number of nodes in the tree. Its syntax is: int TreeSize {get;}
|
The methods defined in Table 11-5 are of particular interest to using a BinaryTreeNode<T> object. Table 11-5. Members of the BinaryTreeNode<T> classMember | Description |
|---|
Overloaded constructor | This constructor creates a BinaryTreeNode<T> object. Its syntax is: BinaryTreeNode(T value)
where value is the object contained in this node, which will be used to compare to its parent. | NumOfChildren property | A read-only property to retrieve the number of children below this node. Its syntax is: int NumOfChildren {get;}
| Left property | A read-only property to retrieve the left child node below this node. Its syntax is: BinaryTreeNode<T> Left {get;}
| Right property | A read-only property to retrieve the right child node below this node. Its syntax is: BinaryTreeNode<T> Right {get;}
| Children method | Retrieves the number of child nodes below this node. Its syntax is: Children( )
| GetValue method | Returns the IComparable<T> object that this node contains. Its syntax is: GetValue( )
| AddNode method | Adds a new node recursively to either the left or right side. Its syntax is: AddNode(BinaryTreeNode<T> node)
where node is the node to be added. Duplicate nodes may be added using this method. | AddUniqueNode method | Adds a new node recursively to either the left side or the right side. Its syntax is: AddUniqueNode(BinaryTreeNode<T> node)
where node is the node to be added. Duplicate nodes may not be added using this method. A Boolean value is returned: true indicates a successful operation; false indicates an attempt to add a duplicate node. | DepthFirstSearch method | Searches for and returns a BinaryTreeNode<T> object in the tree, if one exists. This method searches the depth of the tree first. Its syntax is: DepthFirstSearch(T targetObj)
where targetObj is the object to be found in the tree. | PrintDepthFirst method | Displays the tree in depth-first format. Its syntax is: PrintDepthFirst( )
| RemoveLeftNode method | Removes the left node and any child nodes of this node. Its syntax is: RemoveLeftNode( )
| RemoveRightNode method | Removes the right node and any child nodes of this node. Its syntax is: RemoveRightNode( )
|
The code in Example 11-12 illustrates the use of the BinaryTree<T> and BinaryTreeNode<T> classes when creating and using a binary tree. Example 11-12. Using the BinaryTree and Binary TreeNode classes public static void TestBinaryTree() { BinaryTree<string> tree = new BinaryTree<string>("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.Count); Console.WriteLine("tree.Root.DepthFirstSearch(b).Children: " + tree.Root.DepthFirstSearch("b").Children); Console.WriteLine("tree.Root.DepthFirstSearch(a).Children: " + tree.Root.DepthFirstSearch("a").Children); Console.WriteLine("tree.Root.DepthFirstSearch(g).Children: " + tree.Root.DepthFirstSearch("g").Children); Console.WriteLine("tree.SearchDepthFirst(a): " + tree.SearchDepthFirst("a").Value); Console.WriteLine("tree.SearchDepthFirst(b): " + tree.SearchDepthFirst("b").Value); Console.WriteLine("tree.SearchDepthFirst(c): " + tree.SearchDepthFirst("c").Value); Console.WriteLine("tree.SearchDepthFirst(d): " + tree.SearchDepthFirst("d").Value); Console.WriteLine("tree.SearchDepthFirst(e): " + tree.SearchDepthFirst("e").Value); Console.WriteLine("tree.SearchDepthFirst(f): " + tree.SearchDepthFirst("f").Value); tree.Root.RemoveLeftNode(); tree.Print(); tree.Root.RemoveRightNode(); tree.Print(); }
|
The output for this method is shown here: a Contains Left: NULL Contains Right: b b Contains Left: NULL Contains Right: c c Contains Left: NULL Contains Right: NULL d Contains Left: a Contains Right: f e Contains Left: NULL Contains Right: NULL f Contains Left: e Contains Right: g g Contains Left: NULL Contains Right: NULL a Contains Left: NULL Contains Right: b b Contains Left: NULL Contains Right: c c Contains Left: NULL Contains Right: NULL d Contains Left: a Contains Right: f e Contains Left: NULL Contains Right: NULL f Contains Left: e Contains Right: g g Contains Left: NULL Contains Right: NULL tree.TreeSize: 7 tree.Root.DepthFirstSearch(a).Children: 1 tree.Root.DepthFirstSearch(a).Children: 2 tree.Root.DepthFirstSearch(g).Children: 0 tree.SearchDepthFirst(a): a tree.SearchDepthFirst(b): b tree.SearchDepthFirst(c): c tree.SearchDepthFirst(d): d tree.SearchDepthFirst(e): e tree.SearchDepthFirst(f): f d Contains Left: NULL Contains Right: f e Contains Left: NULL Contains Right: NULL f Contains Left: e Contains Right: g g Contains Left: NULL Contains Right: NULL d Contains Left: NULL Contains Right: NULL
Discussion Trees are data structures in which 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 11.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 you are done. If no, continue.
Is the object to be added to the tree less than (less than is determined by the IComparable<T>.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<T> class is not a part of the actual tree; rather, it acts as a starting point from which you 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<T>, 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<T> class contains a protected field, nodeValue, that contains an object implementing the IComparable<T> interface. This structure allows you to perform searches and add nodes in the correct location in the tree. The CompareTo method of the IComparable<T> interface is used in searching and adding methods to determine whether you need to follow the left or right branch. See the AddNode, AddUniqueNode, and DepthFirstSearch methodsdiscussed in the following paragraphsto 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 or 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<T> class is provided to create and manage the tree of BinaryTreeNode<T> objects, you can merely use the BinaryTreeNode<T> class as long as you keep track of the root node yourself. The code shown in Example 11-13 creates and manages the tree without the use of the BinaryTree<T> class. Example 11-13. Creating and managing a binary tree without using the BinaryTree class public static void TestManagedTreeWithNoBinaryTreeClass() { // Create the root node. BinaryTreeNode<string> topLevel = new BinaryTreeNode<string>("d"); // Create all nodes that will be added to the tree. BinaryTreeNode<string> one = new BinaryTreeNode<string>("b"); BinaryTreeNode<string> two = new BinaryTreeNode<string>("c"); BinaryTreeNode<string> three = new BinaryTreeNode<string>("a"); BinaryTreeNode<string> four = new BinaryTreeNode<string>("e"); BinaryTreeNode<string> five = new BinaryTreeNode<string>("f"); BinaryTreeNode<string> six = new BinaryTreeNode<string>("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.Children: " + topLevel.Children); Console.WriteLine("one.Children: " + one.Children); Console.WriteLine("three.Children: " + three.Children); Console.WriteLine("six.Children: " + six.Children); // Search the tree using the depth-first searching method. Console.WriteLine("topLevel.DepthFirstSearch(a): " + topLevel.DepthFirstSearch("a").Value.ToString()); Console.WriteLine("topLevel.DepthFirstSearch(b): " + topLevel.DepthFirstSearch("b").Value.ToString()); Console.WriteLine("topLevel.DepthFirstSearch(c): " + topLevel.DepthFirstSearch("c").Value.ToString()); Console.WriteLine("topLevel.DepthFirstSearch(d): " + topLevel.DepthFirstSearch("d").Value.ToString()); Console.WriteLine("topLevel.DepthFirstSearch(e): " + topLevel.DepthFirstSearch("e").Value.ToString()); Console.WriteLine("topLevel.DepthFirstSearch(f): " + topLevel.DepthFirstSearch("f").Value.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(); }
|
The output for this method is shown here: a Contains Left: NULL Contains Right: b b Contains Left: NULL Contains Right: c c Contains Left: NULL Contains Right: NULL d Contains Left: a Contains Right: f e Contains Left: NULL Contains Right: NULL f Contains Left: e Contains Right: g g Contains Left: NULL Contains Right: NULL a Contains Left: NULL Contains Right: b b Contains Left: NULL Contains Right: c c Contains Left: NULL Contains Right: NULL topLevel.Children: 6 one.Children: 1 three.Children: 2 six.Children: 0 topLevel.DepthFirstSearch(a): a topLevel.DepthFirstSearch(b): b topLevel.DepthFirstSearch(c): c topLevel.DepthFirstSearch(d): d topLevel.DepthFirstSearch(e): e topLevel.DepthFirstSearch(f): f d Contains Left: NULL Contains Right: f e Contains Left: NULL Contains Right: NULL f Contains Left: e Contains Right: g g Contains Left: NULL Contains Right: NULL d Contains Left: NULL Contains Right: NULL
See Also See the "Queue Class" and "IComparable<T> Interface" topics in the MSDN documentation. | 