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.
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
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(" childNodes[" + index + "]: " + childNodes[index].nodeValue.ToString( )); } else { Console.WriteLine(" childNodes[" + 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
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
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(" Breadth 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( )); }
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 children—obtained from the factory class—provides 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.