java – 递归地将arraylist排序到树中

使用 Composite Pattern为所有对象提供通用接口.

接口或抽象超类Component表示可能具有关系的所有对象.一个子类,Leaf,没有任何孩子. (可能还有其他非复合的Leaf类子类.)另一个子类Composite包含许多对象,通常是任何类型的Component.这允许Composite包含其他复合材料或其他非复合材料,如Leaf.

我在这里创建的Component超类是ComponentObject.这里,所有ComponentObject都有一个父类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,它封装了一个子对象列表,可以是其他CategoryObjects或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;
   }
}

“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 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