Recipe 11.7. Creating an n-ary Tree Problem You need a tree that can store a number of child nodes in each of its nodes. A binary tree will work if each node needs to have only two children, but in this case each node needs to have a fixed number of child nodes greater than two. Solution Use the Ntree<T> class shown in Example 11-14 to create the root node for the n-ary tree. Example 11-14. Generic NTree class using System; using System.Collections; using System.Collections.Generic; public class NTree<T> : IEnumerable<T> where T : IComparable<T> { public NTree() { maxChildren = int.MaxValue; } public NTree(int maxNumChildren) { maxChildren = maxNumChildren; } // The root node of the tree protected NTreeNode<T> root = null; // The maximum number of child nodes that a parent node may contain protected int maxChildren = 0; public void AddRoot(NTreeNode<T> node) { root = node; } public NTreeNode<T> GetRoot() { return (root); } public int MaxChildren { get {return (maxChildren);} } IEnumerator<T> System.Collections.Generic.IEnumerable<T>.GetEnumerator() { List<T> nodes = new List<T>(); nodes = GetRoot().IterateDepthFirst(); nodes.Add(GetRoot().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 methods defined in Table 11-6 are of particular interest to using an Ntree<T> object. Table 11-6. Members of the NTree<T> classMember | Description |
|---|
Overloaded constructor | This constructor creates an Ntree<T> object. Its syntax is: NTree(int maxNumChildren)
where maxNumChildren is the maximum number of children that one node may have at any time. | MaxChildren property | A read-only property to retrieve the maximum number of children any node may have. Its syntax is: int MaxChildren {get;}
The value this property returns is set in the constructor. | AddRoot method | Adds a node to the tree. Its syntax is: AddRoot(NTreeNodeFactory<T>.NTreeNode<U> node)
where node is the node to be added as a child to the current node. | Getroot method | Returns the root node of this tree. Its syntax is: GetRoot( )
|
The NtreeNodeFactory<T> class is used to create nodes for the n-ary tree. These nodes are defined in the class NtreeNode<U>, which is nested inside of the NtreeNodeFactory<T> class. You are not able to create an NtreeNode<U> without the use of this factory class, as shown in Example 11-15. Example 11-15. Using the class to create the nodes for an n-ary tree public class NTreeNodeFactory<T> where T : IComparable<T> { public NTreeNodeFactory(NTree<T> root) { maxChildren = root.MaxChildren; } private int maxChildren = 0; public int MaxChildren { get {return (maxChildren);} } public NTreeNode<T> CreateNode(T value) { return (new NTreeNode<T>(value, maxChildren)); } } // Node class public class NTreeNode<U> where U : IComparable<U> { public NTreeNode(U value, int maxChildren) { if (value != null) { nodeValue = value; } childNodes = new NTreeNode<U>[maxChildren]; } protected U nodeValue = default(U); protected NTreeNode<U>[] childNodes = null; public int CountChildren { get { int currCount = 0; for (int index = 0; index <= childNodes.GetUpperBound(0); index++) { if (childNodes[index] != null) { ++currCount; currCount += childNodes[index].CountChildren; } } return (currCount); } } public int CountImmediateChildren { get { int currCount = 0; for (int index = 0; index <= childNodes.GetUpperBound(0); index++) { if (childNodes[index] != null) { ++currCount; } } return (currCount); } } public NTreeNode<U>[] Children { get {return (childNodes);} } public NTreeNode<U> GetChild(int index) { return (childNodes[index]); } public U Value() { return (nodeValue); } public void AddNode(NTreeNode<U> node) { int numOfNonNullNodes = CountImmediateChildren; if (numOfNonNullNodes < childNodes.Length) { childNodes[numOfNonNullNodes] = node; } else { throw (new Exception("Cannot add more children to this node.")); } } public NTreeNode<U> DepthFirstSearch(U targetObj) { NTreeNode<U> retObj = default(NTreeNode<U>); if (targetObj.CompareTo(nodeValue) == 0) { retObj = this; } else { for (int index=0; index<=childNodes.GetUpperBound(0); index++) { if (childNodes[index] != null) { retObj = childNodes[index].DepthFirstSearch(targetObj); if (retObj != null) { break; } } } } return (retObj); } public NTreeNode<U> BreadthFirstSearch(U targetObj) { Queue<NTreeNode<U>> row = new Queue<NTreeNode<U>>(); row.Enqueue(this); while (row.Count > 0) { // Get next node in queue. NTreeNode<U> currentNode = row.Dequeue(); // Is this the node we are looking for? if (targetObj.CompareTo(currentNode.nodeValue) == 0) { return (currentNode); } for (int index = 0; index < currentNode.CountImmediateChildren; index++) { if (currentNode.Children[index] != null) { row.Enqueue(currentNode.Children[index]); } } } return (null); } public void PrintDepthFirst() { Console.WriteLine("this: " + nodeValue.ToString()); for (int index = 0; index < childNodes.Length; index++) { if (childNodes[index] != null) { Console.WriteLine("\tchildNodes[" + index + "]: " + childNodes[index].nodeValue.ToString()); } else { Console.WriteLine("\tchildNodes[" + index + "]: NULL"); } } for (int index = 0; index < childNodes.Length; index++) { if (childNodes[index] != null) { childNodes[index].PrintDepthFirst(); } } } public List<U> IterateDepthFirst() { List<U> tempList = new List<U>(); for (int index = 0; index < childNodes.Length; index++) { if (childNodes[index] != null) { tempList.Add(childNodes[index].nodeValue); } } for (int index = 0; index < childNodes.Length; index++) { if (childNodes[index] != null) { tempList.AddRange(childNodes[index].IterateDepthFirst()); } } return (tempList); } public void RemoveNode(int index) { // Remove node from array and compact the array. if (index < childNodes.GetLowerBound(0) || index > childNodes.GetUpperBound(0)) { throw (new ArgumentOutOfRangeException("index", index, "Array index out of bounds.")); } else if (index < childNodes.GetUpperBound(0)) { Array.Copy(childNodes, index + 1, childNodes, index, childNodes.Length - index - 1); } childNodes.SetValue(null, childNodes.GetUpperBound(0)); } }
|
The methods defined in Table 11-7 are of particular interest to using an NtreeNodeFactory<T> object. Table 11-7. Members of the NTreeNodeFactory<T> classMember | Description |
|---|
Constructor | Creates a new NTReeNodeFactory<T> object that will create NTReeNode<U> objects with the same number of MaxChildren that the Ntree<T> object passed in supports. Its syntax is: NTreeNodeFactory(NTree<T> root)
where root is an Ntree<T> object. | MaxChildren property | Read-only property that returns the maximum number of children that the Ntree<T> object supports. Its syntax is: int MaxChildren {get;}
| CreateNode method | Overloaded. Returns a new NTReeNode object. Its syntax is: CreateNode( ) CreateNode(IComparable value)
where value is the IComparable object this new node object will contain. |
The methods defined in Table 11-8 are of particular interest to using the nested NtreeNode<U> object. Table 11-8. Members of the NTreeNode<U> classMember | Description |
|---|
Constructor | Creates a new NtreeNode<U> object from the NtreeNodeFactory<T> object passed in to it. Its syntax is: NTreeNode(T value, int maxChildren)
where value is an IComparable<T> object and maxChildren is the total number of children allowed by this node. | NumOfChildren property | Read-only property that returns the total number of children below this node. Its syntax is: int NumOfChildren {get;}
| Children property | Read-only property that returns all of the non-null child-node objects in an array that the current node contains. Its syntax is: NTreeNode<U>[] Children {get;}
| CountChildren property | Recursively counts the number of non-null child nodes below the current node and returns this value as an integer. Its syntax is: CountChildren
| CountImmediateChildren property | Counts only the non-null child nodes contained in the current node. Its syntax is: CountImmediateChildren
| GetChild method | Uses an index to return the NtreeNode<U> contained by the current node. Its syntax is: GetChild(int index)
where index is the array index where the child object is stored. | Value method | Returns an object of type T that the current node contains. Its syntax is: Value( )
| AddNode method | Adds a new child node to the current node. Its syntax is: AddNode(NTreeNode<U> node)
where node is the child node to be added. | DepthFirstSearch method | Attempts to locate an NTReeNode<U> by the IComparable<T> object that it contains. An NtreeNode<U> is returned if the IComparable<T> object is located or a null if it is not. Its syntax is: DepthFirstSearch(IComparable<T> targetObj)
where targetObj is the IComparable<T> object to locate in the tree. Note that this search starts with the current node, which may or may not be the root of the tree. The tree traversal is done in a depth-first manner. | BreadthFirstSearch method | Attempts to locate an NTReeNode<U> by the IComparable<T> object that it contains. An NTReeNode<U> is returned if the IComparable<T> object is located or a null if it is not. Its syntax is: BreadthFirstSearch(IComparable<T> targetObj)
where targetObj is the IComparable<T> object to locate in the tree. Note that this search starts with the current node, which may or may not be the root of the tree. The tree traversal is done in a breadth-first manner. | PrintDepthFirst method | Displays the tree structure on the console window starting with the current node. Its syntax is: PrintDepthFirst( )
This method uses recursion to display each node in the tree. | RemoveNode method | Removes the child node at the specified index on the current node. Its syntax is: RemoveNode(int index)
where index is the array index where the child object is stored. Note that when a node is removed, all of its children nodes are removed as well. |
The code shown in Example 11-16 illustrates the use of the Ntree<T>, Ntree-NodeFactory<T>, and NtreeNode<U> classes to create and manipulate an n-ary tree. Example 11-16. Using the NTree<T>, NTreeNodeFactory<T>, and NTreeNode<U> classes public static void TestNTree() { NTree<string> topLevel = new NTree<string>(3); NTreeNodeFactory<string> nodeFactory = new NTreeNodeFactory<string>(topLevel); NTreeNode<string> one = nodeFactory.CreateNode("One"); NTreeNode<string> two = nodeFactory.CreateNode("Two"); NTreeNode<string> three = nodeFactory.CreateNode("Three"); NTreeNode<string> four = nodeFactory.CreateNode("Four"); NTreeNode<string> five = nodeFactory.CreateNode("Five"); NTreeNode<string> six = nodeFactory.CreateNode("Six"); NTreeNode<string> seven = nodeFactory.CreateNode("Seven"); NTreeNode<string> eight = nodeFactory.CreateNode("Eight"); NTreeNode<string> nine = nodeFactory.CreateNode("Nine"); topLevel.AddRoot(one); Console.WriteLine("topLevel.GetRoot().CountChildren: " + topLevel.GetRoot().CountChildren); topLevel.GetRoot().AddNode(two); topLevel.GetRoot().AddNode(three); topLevel.GetRoot().AddNode(four); topLevel.GetRoot().Children[0].AddNode(five); topLevel.GetRoot().Children[0].AddNode(eight); topLevel.GetRoot().Children[0].AddNode(nine); topLevel.GetRoot().Children[1].AddNode(six); topLevel.GetRoot().Children[1].Children[0].AddNode(seven); Console.WriteLine("Display Entire tree:"); topLevel.GetRoot().PrintDepthFirst(); Console.WriteLine("Display tree from node [two]:"); topLevel.GetRoot().Children[0].PrintDepthFirst(); Console.WriteLine("Depth First Search:"); Console.WriteLine("topLevel.DepthFirstSearch(One): " + topLevel.GetRoot().DepthFirstSearch("One").Value().ToString()); Console.WriteLine("topLevel.DepthFirstSearch(Two): " + topLevel.GetRoot().DepthFirstSearch("Two").Value().ToString()); Console.WriteLine("topLevel.DepthFirstSearch(Three): " + topLevel.GetRoot().DepthFirstSearch("Three").Value().ToString()); Console.WriteLine("topLevel.DepthFirstSearch(Four): " + topLevel.GetRoot().DepthFirstSearch("Four").Value().ToString( )); Console.WriteLine("topLevel.DepthFirstSearch(Five): " + topLevel.GetRoot().DepthFirstSearch("Five").Value().ToString( )); Console.WriteLine("\r\n\r\nBreadth First Search:"); Console.WriteLine("topLevel.BreadthFirstSearch(One): " + topLevel.GetRoot().BreadthFirstSearch("One").Value().ToString()); Console.WriteLine("topLevel.BreadthFirstSearch(Two): " + topLevel.GetRoot().BreadthFirstSearch("Two").Value().ToString()); Console.WriteLine("topLevel.BreadthFirstSearch(Three): " + topLevel.GetRoot().BreadthFirstSearch("Three").Value().ToString( )); Console.WriteLine("topLevel.BreadthFirstSearch(Four): " + topLevel.GetRoot().BreadthFirstSearch("Four").Value().ToString()); }
|
The output for this method is shown here: topLevel.GetRoot().CountChildren: 0 Display Entire tree: this: One childNodes[0]: Two childNodes[1]: Three childNodes[2]: Four this: Two childNodes[0]: Five childNodes[1]: Eight childNodes[2]: Nine this: Five childNodes[0]: NULL childNodes[1]: NULL childNodes[2]: NULL this: Eight childNodes[0]: NULL childNodes[1]: NULL childNodes[2]: NULL this: Nine childNodes[0]: NULL childNodes[1]: NULL childNodes[2]: NULL this: Three childNodes[0]: Six childNodes[1]: NULL childNodes[2]: NULL this: Six childNodes[0]: Seven childNodes[1]: NULL childNodes[2]: NULL this: Seven childNodes[0]: NULL childNodes[1]: NULL childNodes[2]: NULL this: Four childNodes[0]: NULL childNodes[1]: NULL childNodes[2]: NULL Display tree from node [two]: this: Two childNodes[0]: Five childNodes[1]: Eight childNodes[2]: Nine this: Five childNodes[0]: NULL childNodes[1]: NULL childNodes[2]: NULL this: Eight childNodes[0]: NULL childNodes[1]: NULL childNodes[2]: NULL this: Nine childNodes[0]: NULL childNodes[1]: NULL childNodes[2]: NULL Depth First Search: topLevel.DepthFirstSearch(One): One topLevel.DepthFirstSearch(Two): Two topLevel.DepthFirstSearch(Three): Three topLevel.DepthFirstSearch(Four): Four topLevel.DepthFirstSearch(Five): Five Breadth First Search: topLevel.BreadthFirstSearch(One): One topLevel.BreadthFirstSearch(Two): Two topLevel.BreadthFirstSearch(Three): Three topLevel.BreadthFirstSearch(Four): Four
Discussion An n-ary tree is one that has no limitation on the number of children each parent node may contain. This is in contrast to the binary tree in Recipe 11.6, in which each parent node may contain only two children nodes. Ntree<T> is a simple class that contains only a constructor and three public methods. Through this object, you can create an n-ary tree, set the root node, and obtain the root node in order to navigate and manipulate the tree. An Ntree<T> object that can contain at most three children is created in the following manner: NTree<string> topLevel = new NTree<string>(3);
An Ntree<T> object that can contain at most int.MaxValue children, which allows greater flexibility, is created in the following manner: NTree<string> topLevel = new NTree<string>();
The real work is done in the NTReeNodeFactory<T> object and the NtreeNode<U> object, which is nested in the NtreeNodeFactory<T> class. The NtreeNodeFactory<T> class is an object factory that facilitates the construction of all NtreeNode<U> objects. When the factory object is created, the NTRee<T> object is passed in to the constructor, as shown here: NTreeNodeFactory<string> nodeFactory = new NTreeNodeFactory<string>(topLevel);
Therefore, when the factory object is created, it knows the maximum number of children that a parent node may have. The factory object provides a public method, CreateNode, that allows for the creation of an NtreeNode<U> object. If an IComparable<T> type object is passed into this method, the IComparable<T> object will be contained within this new node in the nodeValue field. If a null is passed in, the new NtreeNode<U> object will contain the object U with it initialized using the default keyword. The String object can be passed in to this parameter with no modifications. Node creation is performed in the following manner: NTreeNode<string> one = nodeFactory.CreateNode("One"); NTreeNode<string> two = nodeFactory.CreateNode("Two"); NTreeNode<string> three = nodeFactory.CreateNode("Three"); NTreeNode<string> four = nodeFactory.CreateNode("Four"); NTreeNode<string> five = nodeFactory.CreateNode("Five"); NTreeNode<string> six = nodeFactory.CreateNode("Six"); NTreeNode<string> seven = nodeFactory.CreateNode("Seven"); NTreeNode<string> eight = nodeFactory.CreateNode("Eight"); NTreeNode<string> nine = nodeFactory.CreateNode("Nine");
The NTReeNode<U> class is nested within the factory class; it is not supposed to be used directly to create a node object. Instead, the factory will create a node object and return it to the caller. NtreeNode<U> has one constructor that accepts two parameters: value, which is an object of type U used to store an object implementing the IComparable<T> interface; and an integer value, maxChildren, which is used to define the total number of child nodes allowed. It is the nodeValue field that you use when you are searching the tree for a particular item. Adding a root node to the TopLevel NTree<T> object is performed using the AddRoot method of the Ntree<T> object: topLevel.AddRoot(one);
Each NtreeNode<U> object contains a field called childNodes. This field is an array containing all child nodes attached to this parent node object. The maximum number of childrenobtained from the factory classprovides this number, which is used to create the fixed-size array. This array is initialized in the constructor of the NtreeNode<U> object. The following code shows how to add nodes to this tree: // Add nodes to root. topLevel.GetRoot().AddNode(two); topLevel.GetRoot().AddNode(three); topLevel.GetRoot().AddNode(four); // Add node to the first node Two of the root. topLevel.GetRoot().Children[0].AddNode(five); // Add node to the previous node added, node five. topLevel.GetRoot().BreadthFirstSearch("Five").AddNode(six);
The searching method BreadthFirstSearch is constructed similarly to the way the same method was constructed for the binary tree in Recipe 11.6. The DepthFirstSearch method is constructed a little differently from the same method in the binary tree. This method uses recursion to search the tree, but it uses a for loop to iterate over the array of child nodes, searching each one in turn. In addition, the current node is checked first to determine whether it matches the targetObj parameter to this method. This is a better performing design, as opposed to moving this test to the end of the method. If the RemoveNode method is successful, the array containing all child nodes of the current node is compacted to prevent fragmentation, which allows nodes to be added later in a much simpler manner. The AddNode method only has to add the child node to the end of this array as opposed to searching the array for an open element. The following code shows how to remove a node: // Remove all nodes below node 'Two'. // Nodes 'Five' and 'Six' are removed. topLevel.GetRoot().BreadthFirstSearch("Two").RemoveNode(0); // Remove node 'Three' from the root node. topLevel.GetRoot().RemoveNode(1);
See Also See the "Queue<T> Class" and "IComparable Interface" topics in the MSDN documentation. | 