java - 递归将arraylist排序到树中

我有一个Object的数组列表。但是我需要一棵具有以下参数的树:

某些对象不应具有子对象(非类别对象)

类别对象应该具有子项(可以是其他类别对象或非类别对象)

没有子级的

类别对象应被跳过/删除

所有对象的父对象都有一个变量。但是我没有一个好的算法可以递归确定每个类别对象有多少个孩子。所有处于同一级别的孩子都将成为ArrayList<Object>
我目前有一个迭代方法，该方法只能深入一层，不能区分方案2的某些版本。我认为它的代码不相关，因为它不是递归的。

有识之士赞赏

最佳答案

使用Composite Pattern为所有对象提供一个通用接口。

接口或抽象超类Component表示可能具有关系的所有对象。一个子类，叶子，没有任何子代。 (可能还有其他非复合的类似Leaf的子类。)另一个子类Composite包含许多对象，通常是任何种类的Component。这样就可以使Composite包含其他Composites或其他非复合材料，例如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(不包含子代的Leaf子叶)和CategoryObject，封装了子代对象列表的Composite，可以是其他CategoryObject或NonCategoryObject。

NonCategoryObject

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

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

类别对象

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

“getNumChildren”方法对于通过Composite Pattern查找子代数很重要。

设置数据

您有一个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);
}

方法

这里是方法。首先是“复合”方法，该方法利用复合模式确定子代数。它只是调用根的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

关于java - 递归将arraylist排序到树中，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21570138/