Sort arraylist into tree recursively

Question

Sort arraylist into tree recursively

I have an arraylist Object. But I need a tree with the following parameters:

Some objects should not have child objects (non-category objects)
In the category, Objects must have children (which can be objects of additional categories or objects that are not related to the category)
Category objects that do not have children should be skipped / deleted.

All objects have a variable for their parent. But I do not have a good algorithm that can recursively determine how many children each object in a category has. All children on the same level will beArrayList<Object>

I currently have an iterative method that can go only one level and cannot distinguish some versions of scenario 2. I don't think this code matters because it is not recursive.

insight appreciated

+3

java treemap recursion tree treeset

Cqm Feb 05 '14 at 6:29

source share

3 answers

, , , . , , .

"id" , . , . .

:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;

public class TestStructure {

public interface ElementVisitor<E>{
    boolean startVisit(Element<E> e);
    void endVisit(Element<E> e);
}

public interface Element<E>{
    E getId();
    public boolean isParent();
    Parent<E> getParent();
    void visit(ElementVisitor<E> visitor);
}

public interface Parent<E> extends Element<E>{
    List<Element<E>> getChildren();
    int size();
}

public static abstract class ElementImpl<E> implements Element<E>{
    private final E id;
    private ParentImpl<E> parent;

    public ElementImpl(E id) {
        super();
        if (id == null) {
            throw new IllegalArgumentException("id must not be null");
        }
        this.id = id;
    }

    void setParent(ParentImpl<E> parent) {
        this.parent = parent;
    }
    @Override
    public final ParentImpl<E> getParent() {
        return parent;
    }
    protected final void addToParent(){
        parent.addChild(this);
    }
    protected final void removeFromParent(){
        parent.removeChild(this);
    }
    public final boolean isTreeRoot(){
        return parent == null;
    }

    @Override
    public String toString() {
        return getId().toString();
    }

    public int getTreeLevel() {
        int level = 0;
        ParentImpl<E> parent = this.parent;
        while (parent != null) {
            parent = parent.getParent();
            level++;
        }
        return level;
    }

    public ParentImpl<E> getRoot(){
        ElementImpl<E> e = this;
        while (e.parent != null) {
            e = e.parent;
        }
        return (ParentImpl<E>) e;
    }

    public E getId() {
        return id;
    }
}

public static class ChildImpl<E> extends ElementImpl<E> implements Element<E>{

    public ChildImpl(E id) {
        super(id);
    }

    @Override
    public void visit(ElementVisitor<E> visitor) {
        visitor.startVisit(this);
        visitor.endVisit(this);
    }

    @Override
    void setParent(ParentImpl<E> parent) {
        super.setParent(parent);
        // add childs to parent automatically
        addToParent();
    }
    @Override
    public boolean isParent() {
        return false;
    }
}

public static class ParentImpl<E> extends ElementImpl<E> implements Parent<E>{
    private List<ElementImpl<E>> children;
    boolean added = false;

    public ParentImpl(E id) {
        super(id);
    }

    @SuppressWarnings("unchecked")
    @Override
    public List<Element<E>> getChildren() {
        return children == null ? Collections.EMPTY_LIST : children;
    }

    public void addChild(ElementImpl<E> child){
        if (children == null) {
            children = new ArrayList<>();
        }
        if (getParent() != null && children.size() == 0) {
            // only include parents in the tree if they have children
            addToParent();
            added = true;
        }
        children.add(child);
    }

    public boolean removeChild(ElementImpl<E> e) {
        if (children != null && children.remove(e)) {
            if (children.size() == 0) {
                children = null;
                removeFromParent();
                added = false;
            }
        }
        return false;
    }

    @Override
    void setParent(ParentImpl<E> parent) {
        super.setParent(parent);
        if (children != null && !added) {
            addToParent();
            added = true;
        }
    }

    @Override
    public int size() {
        return children == null ? 0 : children.size();
    }

    @Override
    public void visit(ElementVisitor<E> visitor) {
        if (visitor.startVisit(this)) {
            for (Element<E> e : getChildren()) {
                e.visit(visitor);
            }
        }
        visitor.endVisit(this);
    }

    @Override
    public boolean isParent() {
        return true;
    }

}


public static void main(String[] args) {

    // elements below parentRange are considered parents
    int parentRange = 80;

    // The number of all elements in the tree
    int numberOfElements = 150;

    Map<Integer, Integer> relationMap = new HashMap<>(); // map from child id to parent id
    Random random = new Random();

    // id 0 == root id
    // create an initial parent element at the root
    relationMap.put(1, 0);
    // create the parent elements
    for (int id = 2; id < parentRange; id++) {
        int parentId = random.nextInt(id-1);
        relationMap.put(id, parentId);
    }

    // create the child elements
    for (int id = parentRange; id < numberOfElements; id++) {
        int parentId = random.nextInt(parentRange);
        relationMap.put(id, parentId);
    }

    HashMap<Integer, ParentImpl<Integer>> map = new HashMap<>();

    final ParentImpl<Integer> treeRoot = new ParentImpl<>(0);
    map.put(0, treeRoot);
    // create the tree structure
    for (Entry<Integer, Integer> entry : relationMap.entrySet()) {
        Integer childId = entry.getKey();
        Integer parentId = entry.getValue();

        ParentImpl<Integer> parentImpl = map.get(parentId);
        if (parentImpl == null) {
            parentImpl = new ParentImpl<>(parentId);
            map.put(parentId, parentImpl);
        }

        ElementImpl<Integer> child;
        if (childId < parentRange) {
            // this child is a parent
            child = map.get(childId);
            if (child == null) {
                ParentImpl<Integer> p = new ParentImpl<>(childId);
                child = p;
                map.put(childId, p);
            }
        } else{
            child = new ChildImpl<>(childId);
        }
        child.setParent(parentImpl);

    }

    // count the number of elements in the tree
    class Counter  implements ElementVisitor<Integer> {
        int count = 0;
        @Override
        public boolean startVisit(Element<Integer> e) {
            count++;
            return true;
        }
        @Override
        public void endVisit(Element<Integer> e) {}
    };

    Counter counter = new Counter();
    treeRoot.visit(counter);
    System.out.println("Number of all elements in the tree: " + counter.count);

    // validate the tree structure
    ElementVisitor<Integer> treeValidator = new ElementVisitor<Integer>() {
        @Override
        public boolean startVisit(Element<Integer> e) {
            if (!e.getId().equals(0) && e.getParent() == null) {
                throw new IllegalStateException("child with no parent...");
            }
            if (e.isParent()) {
                Parent<Integer> parent = (Parent<Integer>)e;
                if (parent.size() == 0) {
                    throw new IllegalStateException("parent with no children...");
                }
            }
            return true;
        }

        @Override
        public void endVisit(Element<Integer> e) {}
    };
    treeRoot.visit(treeValidator);

    final StringBuilder b = new StringBuilder();
    // print the tree structure
    ElementVisitor<Integer> treePrinter = new ElementVisitor<Integer>() {
        int level = 0;
        @Override
        public boolean startVisit(Element<Integer> e) {
            for (int i = 0; i < level; i++) {
                b.append("  ");
            }
            if (e.isParent()) {
                b.append("Parent ");
                level++;
            } else{
                b.append("Child ");
            }
            b.append(e.getId());
            b.append('\n');
            return true;
        }

        @Override
        public void endVisit(Element<Integer> e) {
            if (e.isParent()) {
                level--;
            }
        }
    };
    treeRoot.visit(treePrinter);
    System.out.println("The generated tree structure: ");
    System.out.println(b.toString());
}
}

+3

Balder 07 . '14 11:22

I had a similar problem, but in Javascript. Someone answered this for me using a recursive algorithm:

Convert parent-child array to tree

It may not be exactly as it is, but hopefully it will give you a starting point.

+1

Mark pope Feb 11 '14 at 13:41

source share

rgettman · Accepted Answer · 2014-02-08T01:09:55+0000

Use the Composite Template to provide a common interface for all of your objects.

, , , . "" . ( Leaf- .) Composite , , . Composite , Leaf.

ComponentObject. ComponentObjects CategoryObject, .

ComponentObject

public abstract class ComponentObject
{
   private CategoryObject myParent;

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

   public CategoryObject getParent()
   {
      return myParent;
   }

   public abstract int getNumChildren();
}

: NonCategoryObject, , , CategoryObject, , , CategoryObject, NonCategoryObject s.

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 children.
         numChildren += 1 + child.getNumChildren();
      }
      return numChildren;
   }
}

getNumChildren .

ArrayList , , , :

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));

, . ( ).

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

, . 2 , :

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

. -, "" , . root getNumChildren().

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

:

Composite method: 13

, , , , , . .

, , :

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;
}

:

Recursive method: 13

Sort arraylist into tree recursively

More articles: