Java – recursively sort ArrayLists into a tree

I have an ArrayList of objects But I need a tree with the following parameters:

>Some objects should not have children (non category objects) > category objects should have children (can be other category objects or non category objects) > category objects without children should be skipped / deleted

All objects have a parent variable But I don't have a good algorithm to recursively determine how many children each category object has All child nodes at the same level are ArrayList < Object >

I currently have an iterative method that can only drill down one level and cannot distinguish some versions of scheme 2 I don't think its code is relevant because it's not recursive

Insight appreciation

Solution

Use composite pattern to provide a common interface for all objects

Interface or abstract superclass component represents all objects that may have relationships A subclass, leaf, has no children (there may be other non compound leaf subclasses.) Another subclass, composite, contains many objects, usually any type of component This allows composite to contain other composite materials or other non composite materials, such as leaf

The component superclass I created here is componentobject Here, all componentobjects have a parent class categoryobject, which will be described below

ComponentObject

public abstract class ComponentObject
{
   private CategoryObject myParent;

   protected ComponentObject(CategoryObject parent)
   {
      myParent = parent;
   }

   public CategoryObject getParent()
   {
      return myParent;
   }

   public abstract int getNumChildren();
}

It has two specific subclasses, noncategoryobject. Leaf cannot contain child nodes, categoryobject and composite. It encapsulates a list of child objects, which can be other categoryobjects or noncategoryobjects

NonCategoryObject

public class NonCategoryObject extends ComponentObject
{
   public NonCategoryObject(CategoryObject parent)
   {
      super(parent);
   }

   @Override
   public int getNumChildren()
   {
      return 0;
   }
}

CategoryObject

public class CategoryObject extends ComponentObject
{
   private ArrayList<ComponentObject> myChildren;

   public CategoryObject(CategoryObject parent)
   {
      super(parent);
      myChildren = new ArrayList<ComponentObject>();
   }

   public void addChild(ComponentObject child)
   {
      myChildren.add(child);
   }

   public ComponentObject getChild(int index)
   {
      return myChildren.get(index);
   }

   public int getNumDirectChildren()
   {
      return myChildren.size();
   }

   @Override
   public int getNumChildren()
   {
      int numChildren = 0;
      for (ComponentObject child : myChildren)
      {
         // One for the child itself,plus add any of the child's children.
         numChildren += 1 + child.getNumChildren();
      }
      return numChildren;
   }
}

The "getnumchildren" method is very important for finding the number of children through the composite pattern

Set data

You have an ArrayList of components. Each component knows their parents, but does not know who their children are:

public static void main(String[] args)
{
   // Create a tree structure,parent information only.
   CategoryObject root = new CategoryObject(null);
   CategoryObject categoryOne = new CategoryObject(root);
   CategoryObject categoryTwo = new CategoryObject(root);
   CategoryObject categoryThree = new CategoryObject(root);
   CategoryObject categoryOneOne = new CategoryObject(categoryOne);
   CategoryObject categoryOneTwo = new CategoryObject(categoryOne);
   CategoryObject categoryOneThree = new CategoryObject(categoryOne);
   NonCategoryObject leafOneFour = new NonCategoryObject(categoryOne);
   NonCategoryObject leafOneOneOne = new NonCategoryObject(categoryOneOne);
   NonCategoryObject leafOneOneTwo = new NonCategoryObject(categoryOneTwo);
   NonCategoryObject leafOneTwoOne  = new NonCategoryObject(categoryOneTwo);
   NonCategoryObject leafOneThreeOne  = new NonCategoryObject(categoryOneThree);
   NonCategoryObject leafTwoOne = new NonCategoryObject(categoryTwo);
   NonCategoryObject leafThreeOne = new NonCategoryObject(categoryThree);

   // We're given the ArrayList
   ArrayList<ComponentObject> components = new ArrayList<ComponentObject>();
   // The order doesn't matter.
   components.addAll(Arrays.asList(leafOneFour,leafOneOneTwo,leafOneThreeOne,categoryOne,categoryOneOne,categoryOneThree,root,leafThreeOne,leafOneOneOne,categoryThree,leafOneTwoOne,leafTwoOne,categoryTwo,categoryOneTwo));

The sub information is determined by looping through the list We will also find the root (assuming there is only one parent component)

ComponentObject foundRoot = null;
   for (ComponentObject c : components)
   {
      CategoryObject parent = c.getParent();
      if (parent == null)
      {
         foundRoot = c;
      }
      else
      {
         parent.addChild(c);
      }
   }

Now all parents know who their children are Next, we will call two different methods. Each method has its own method to determine the number of sub items:

// 2 methods to determine the number of children.
   compositeMethod(foundRoot);
   recursiveMethod(foundRoot);
}

method

This is the method First, the "compound" method uses the compound pattern to determine the number of sub items It simply calls the getnumchildren () method of root

private static void compositeMethod(ComponentObject root)
{
   int numChildren = root.getNumChildren();
   System.out.println("Composite method: " + numChildren);
}

Output:

Composite method: 13

A composite method is not very recursive because even if it calls itself, the object it calls itself is different It calls itself the child of the object

The recursive method you are interested in invokes itself at each level in the hierarchy:

private static void recursiveMethod(ComponentObject root)
{
   int numChildren = findNumChildren(root);
   System.out.println("Recursive method: " + numChildren);
}

// The actual recursive method.
private static int findNumChildren(ComponentObject root)
{
   if (root instanceof CategoryObject)
   {
      CategoryObject parent = (CategoryObject) root;
      int numChildren = 0;
      for (int i = 0; i < parent.getNumDirectChildren(); i++)
      {
         ComponentObject child = parent.getChild(i);
         // One for the child itself,plus its children.
         numChildren += 1 + findNumChildren(child);
      }
      return numChildren;
   }

   // Base case: NonCategoryObjects have no children.
   return 0;
}

Output:

Recursive method: 13