jeudi 22 avril 2021

Creating a tree with specific depth and children

I am trying to generate a random tree using the composite pattern design. The tree must have a specified depth, and each node in the tree must have a specified number of children. In the node class, I have a List<> structure, which holds all the children of that particular node. I have attached the composite class with just the relevant code: (Note, componentNode is the interface of the composite pattern, a componentNode can be either a compositeNode or a leafNode, which is why the List<> holds componentNode).

class compositeNode implements componentNode
{
    //a compositeNode holds a list of other components inside of it 
    List<componentNode> components = new ArrayList<componentNode>();

    String name;

    public compositeNode(String inName)
    {
        name = inName;
    }

    public List<componentNode> getList()
    {
        return components;
    }

    public void addComponent(componentNode newComponent)
    {
        components.add(newComponent);
    }

    public String getName()
    {
        return name;
    }

}

This is my attempt at generating the tree:

    public static void treeGeneration()
    {
        int numChildNodes = 2;
        int treeDepth = 2;
        //getRandomNumber(1,5); 
        compositeNode tree = new compositeNode("Root");
        compositeNode currNode = tree;
        compositeNode currDepth;        

        for (int x=0; x<numChildNodes; x++)
        {
            compositeNode node = new compositeNode(generateName());
            tree.addComponent(node);
        }

        List<componentNode> treeList = tree.getList();
        Iterator<componentNode> iterTree = treeList.iterator();

        
        while(iterTree.hasNext())
        {
            currNode = (compositeNode) iterTree.next();//iterate through the children of the root node
            for (int i=1; i<treeDepth; i++)//accessing the child nodes so depth is 1
            {
                for (int x=0; x<numChildNodes; x++)
                {       
                    compositeNode newNode = new compositeNode(generateName());
                    currNode.addComponent(newNode);//add newly created nodes to the 
                }
                List<componentNode> currList = currNode.getList();
                Iterator<componentNode> iterList = currList.iterator();//iterate through the newly created nodes to add nodes to them 
                currNode = (compositeNode) iterList.next();
            } 
        }

The issue in my code is that the specified depth is only reached for the FIRST node of each list. For example, this is what the tree looks like when I execute it with a depth of 3, with each node having 2 children:

                         Root
                      /       \ 
                  Node1         Node2 
                 /     \        /     \
              Node3   Node4   Node7   Node8
             /    \          /     \
          Node5  Node6      Node9  Node10

As you can see node4 and node8 do not have any children, when I need them to have children. I understand the issue in my code is because once I have reached the end of the for loop where I am iterating until I reach the depth, it moves onto the next node. However, I have no clue as to how I am supposed to fix it. I have been stuck on this problem for hours now, any help will be appreciated. Thanks :)

Aucun commentaire:

Enregistrer un commentaire