java - 递归地将arraylist排序为树

Question

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

1. 有些对象不应该有子对象(非类别对象)
2. 类别对象应该有子对象(可以是额外的类别对象，或非类别对象)
3. 应跳过/删除没有子项的类别对象

所有对象都有一个变量来表示它们的父对象是什么。但是我没有一个好的算法可以递归地确定每个类别对象有多少个 child 。同一级别的所有 child 都是一个 ArrayList<Object>

我目前有一个只能深入一层的迭代方法，无法区分场景 2 的某些版本。我认为它的代码不相关，因为它不是递归的。

赞赏的洞察力

Answer 1

使用 Composite Pattern为您的所有对象提供一个通用接口(interface)。

接口(interface)或抽象父类(super class)，组件，代表所有可能有关系的对象。一个子类 Leaf 没有任何子类。 (可能有其他非复合类 Leaf 子类。)另一个子类 Composite 包含许多对象，通常是任何类型的组件。这允许 Composite 包含其他 Composites 或其他非复合 Material ，例如 Leaf。

我在这里创建的组件父类(super class)是ComponentObject。在这里，所有 ComponentObjects 都有一个父级，即下面介绍的 CategoryObject。

组件对象

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。

非类别对象

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”方法对于通过复合模式查找 child 的数量很重要。

设置数据

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

现在所有的 parent 都知道他们的 child 是谁。接下来，我们将调用 2 种不同的方法，每种方法都有自己的方式来确定 child 的数量:

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

方法

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