Recipe 10.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 would 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 following NTree class to create the root node for the n -ary tree:

 using System; using System.Collections; public class NTree {     public NTree( )      {         maxChildren = int.MaxValue;     }     public NTree(int maxNumChildren)      {         maxChildren = maxNumChildren;     }     // The root node of the tree     protected NTreeNodeFactory.NTreeNode root = null;     // The maximum number of child nodes that a parent node may contain     protected int maxChildren = 0;     public void AddRoot(NTreeNodeFactory.NTreeNode node)     {         root = node;     }     public NTreeNodeFactory.NTreeNode GetRoot( )     {         return (root);     }     public int MaxChildren     {         get {return (maxChildren);}     } }

The methods defined in Table 10-6 are of particular interest to using an NTree object.

Table 10-6. Members of the NTree class

Member	Description
Overloaded constructor	This constructor creates an `NTree` 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.NTreeNode `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 class is used to create nodes for the n -ary tree. These nodes are defined in the class NTreeNode , which is nested inside of the NTreeNodeFactory class. You are not able to create an NTreeNode without the use of this factory class. The code is:

 public class NTreeNodeFactory {     public NTreeNodeFactory(NTree root)      {         maxChildren = root.MaxChildren;     }     private int maxChildren = 0;     public int MaxChildren     {         get {return (maxChildren);}     }     public NTreeNode CreateNode(IComparable value)     {         return (new NTreeNode(value, maxChildren));     }     // Nested Node class     public class NTreeNode     {         public NTreeNode(IComparable value, int maxChildren)          {             if (value != null)             {                 nodeValue = value;             }             childNodes = new NTreeNode[maxChildren];         }         protected IComparable nodeValue = null;         protected NTreeNode[] childNodes = null;         public int NumOfChildren         {             get {return (CountChildren( ));}         }         public int CountChildren( )         {             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( )         {             int currCount = 0;             for (int index = 0; index <= childNodes.GetUpperBound(0); index++)             {                 if (childNodes[index] != null)                 {                     ++currCount;                 }             }             return (currCount);         }         public NTreeNode[] Children         {             get {return (childNodes);}         }         public NTreeNode GetChild(int index)         {             return (childNodes[index]);         }         public IComparable GetValue( )         {             return (nodeValue);         }         public void AddNode(NTreeNode node)         {             int numOfNonNullNodes = CountImmediateChildren( );             if (numOfNonNullNodes < childNodes.Length)             {                 childNodes[numOfNonNullNodes] = node;             }             else             {                 throw (new Exception("Cannot add more children to this node."));             }         }         public NTreeNode DepthFirstSearch (IComparable targetObj)         {             NTreeNode retObj = null;             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 BreadthFirstSearch (IComparable targetObj)         {             Queue row = new Queue( );             row.Enqueue(this);             while (row.Count > 0)             {                 // Get next node in queue                 NTreeNode currentNode = (NTreeNode)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 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 10-7 are of particular interest to using an NTreeNodeFactory object.

Table 10-7. Members of the NTreeNodeFactory class

Member	Description
Constructor	Creates a new `NTreeNodeFactory` object that will create `NTreeNode` objects with the same number of `MaxChildren` that the `NTree` object passed in supports. Its syntax is: NTreeNodeFactory(NTree `root` ) where `root` is an `NTree` object.
`MaxChildren` property	Read-only property that returns the maximum number of children that the `NTree` object supports. Its syntax is: int MaxChildren {get;}
`CurrentValue` property	Read-only property that returns the `IComparable` object that the node created by the `NTreeNodeFactory` contains. Its syntax is: IComparable CurrentValue {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 10-8 are of particular interest to using the nested NTreeNode object.

Table 10-8. Members of the NTreeNode class

Member	Description
Constructor	Creates a new `NTreeNode` object from the `NTreeNodeFactory` object passed in to it. Its syntax is: NTreeNode(NTreeNodeFactory `factory` ) where `factory` is an `NTreeNodeFactory` object.
`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 non- `null` child node objects in an array that the current node contains. Its syntax is: NTreeNode[] Children {get;}
`CountChildren` method	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` method	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` contained by the current node. Its syntax is: GetChild(int `index` ) where `index` is the array index where the child object is stored.
`GetValue` method	Returns the `IComparable` object that the current node contains. Its syntax is: GetValue( )
`AddNode` method	Adds a new child node to the current node. Its syntax is: AddNode(NTreeNode `node` ) where `node` is the child node to be added.
`DepthFirstSearch` method	Attempts to locate an `NTreeNode` by the `IComparable` object that it contains. An `NTreeNode` is returned if the `IComparable` object is located or a `null` if it is not. Its syntax is: DepthFirstSearch(IComparable `targetObj` ) where `targetObj` is the `IComparable` 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` by the `IComparable` object that it contains. An `NTreeNode` is returned if the `IComparable` object is located or a `null` if it is not. Its syntax is: DepthFirstSearch(IComparable `targetObj` ) where `targetObj` is the `IComparable` 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 following code illustrates the use of the NTree , NtreeNodeFactory , and the NTreeNode classes when creating and using an n -ary tree:

 public static void TestNTree( ) {     NTree topLevel = new NTree(3);     NTreeNodeFactory nodeFactory = new NTreeNodeFactory(topLevel);     NTreeNodeFactory.NTreeNode one = nodeFactory.CreateNode("One");     NTreeNodeFactory.NTreeNode two = nodeFactory.CreateNode("Two");     NTreeNodeFactory.NTreeNode three = nodeFactory.CreateNode("Three");     NTreeNodeFactory.NTreeNode four = nodeFactory.CreateNode("Four");     NTreeNodeFactory.NTreeNode five = nodeFactory.CreateNode("Five");     NTreeNodeFactory.NTreeNode six = nodeFactory.CreateNode("Six");     NTreeNodeFactory.NTreeNode seven = nodeFactory.CreateNode("Seven");     NTreeNodeFactory.NTreeNode eight = nodeFactory.CreateNode("Eight");     NTreeNodeFactory.NTreeNode 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").GetValue( ).ToString( ));     Console.WriteLine("topLevel.DepthFirstSearch(Two): " +              topLevel.GetRoot( ).DepthFirstSearch("Two").GetValue( ).ToString( ));     Console.WriteLine("topLevel.DepthFirstSearch(Three): " +              topLevel.GetRoot( ).DepthFirstSearch("Three").GetValue( ).ToString( ));     Console.WriteLine("topLevel.DepthFirstSearch(Four): " +              topLevel.GetRoot( ).DepthFirstSearch("Four").GetValue( ).ToString( ));     Console.WriteLine("topLevel.DepthFirstSearch(Five): " +              topLevel.GetRoot( ).DepthFirstSearch("Five").GetValue( ).ToString( ));     Console.WriteLine("\r\n\r\nBreadth First Search:");     Console.WriteLine("topLevel.BreadthFirstSearch(One): " +              topLevel.GetRoot( ).BreadthFirstSearch("One").GetValue( ).ToString( ));     Console.WriteLine("topLevel.BreadthFirstSearch(Two): " +              topLevel.GetRoot( ).BreadthFirstSearch("Two").GetValue( ).ToString( ));     Console.WriteLine("topLevel.BreadthFirstSearch(Three): " +              topLevel.GetRoot( ).BreadthFirstSearch("Three").GetValue( ).ToString( ));     Console.WriteLine("topLevel.BreadthFirstSearch(Four): " +              topLevel.GetRoot( ).BreadthFirstSearch("Four").GetValue( ).ToString( )); }

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 10.6, in which each parent node may only contain two children nodes.

NTree 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 object that can contain at most three children is created in the following manner:

 NTree topLevel = new NTree(3);

An NTree object that can contain at most int.MaxValue children, which allows greater flexibility, is created in the following manner:

 NTree topLevel = new NTree( );

The real work is done in the NTreeNodeFactory object and the NTreeNode object, which is nested in the NTreeNodeFactory class. The NTreeNodeFactor class is an object factory that facilitates the construction of all NTreeNode objects. When the factory object is created, the NTree object is passed in to the constructor, as shown here:

 NTreeNodeFactory nodeFactory = new NTreeNodeFactory(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 an overloaded public method, CreateNode , that allows for the creation of an NTreeNode object. If an IComparable type object is passed into this method, the IComparable object will be contained within this new node in the Value field. If no IComparable object is passed in, the new NTreeNode object will contain the IComparable object that was passed in to the CreateNode method of the NTreeNodeFactory object the last time it was called, or null if this is the first time this method has been called. Since the String object implements the IComparable interface, it can be passed in to this parameter with no modifications. Passing in no parameters allows the CreateNode method to be called within a loop to make it easier to create many duplicate nodes at one time. Node creation is performed in the following manner:

 NTreeNodeFactory.NTreeNode one = nodeFactory.CreateNode("One"); NTreeNodeFactory.NTreeNode two = nodeFactory.CreateNode("Two"); NTreeNodeFactory.NTreeNode three = nodeFactory.CreateNode("Three"); NTreeNodeFactory.NTreeNode four = nodeFactory.CreateNode("Four"); NTreeNodeFactory.NTreeNode five = nodeFactory.CreateNode("Five"); NTreeNodeFactory.NTreeNode six = nodeFactory.CreateNode("Six"); NTreeNodeFactory.NTreeNode seven = nodeFactory.CreateNode("Seven"); NTreeNodeFactory.NTreeNode eight = nodeFactory.CreateNode("Eight"); NTreeNodeFactory.NTreeNode nine = nodeFactory.CreateNode("Nine");

The NTreeNode class is nested within the factory class; it is not actually 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 has one constructor that accepts an NTreeNodeFactory object. This factory object exposes critical information used to initialize this instance of the NTreeNode object; namely, the maximum number of child nodes allowed. This value is stored in the ChildNodes field of the NTreeNode object. This object also contains a second field, Value , that is used to store an object that implements the IComparable interface. It is this Value field that we use when we are searching the tree for a particular item.

Adding a root node to the TopLevel NTree object is performed using the AddRoot method of the NTree object:

 topLevel.AddRoot(one);

Each NTreeNode 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 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 similar to the way the same method was constructed for the binary tree in Recipe 9.14. 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);

It is easy to modify the NTreeNodeFactory and NTreeNode classes to accept an object instead of an IComparable type object. To do this:

Search for every occurrence of IComparable and replace it with object .
Search for all occurrences of the CompareTo method and replace them with the == operator.