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 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:

See Also

See the "Queue Class" and "IComparable Interface" topics in the MSDN documentation.