java 中的组合模式--list to tree

背景

在项目中，使用到了将菜单数据转换为数格式返回给前端的需求。从数据库中读取的数据，是以list格式读取的，那么如何使用java代码将list转换为tree 呢？
tree型数据结构，类似组合模式，只不过组合的子项是自身

image.png

定义TreeNode 节点

定义TreeNode节点数，节点中提供了addChildren/addChild 等方法管理子节点

@Getter
@Setter
@AllArgsConstructor
@NoArgsConstructor
public class TreeNode {

    private static final long serialVersionUID = 1L;

    private String id;
    private String parentId;
    private String title;
    private String key;
    private String value;
    private Collection<TreeNode> children = new ArrayList<>();

        public void addChild(TreeNode treenode) {
           this.initChildren();
           this.children.add(treenode);
        }

public void addChildren(List<TreeNode> children) {

    this.initChildren();

    Optional.ofNullable(children)
      .ifPresent(c -> this.children.addAll(c));
  }

public void clearChildren() {
    this.initChildren();
    this.children.clear();
  }

private void initChildren() {
    if (this.children == null) {
      this.children = new ArrayList<>();
    }
  }

}

使用递归实现

递归是循环list里的数据，从list中读取该项的所有子项

public static List<TreeNode> listToTree(List<TreeNode> items) {

        // 查出父节点
    List<TreeNode> rootList = items.stream().filter(c->c.getParentId()==null||c.getParentId()==0L).collect(Collectors.toList());

        // 按 parentid - list 进行分组
    Map<Long, List<TreeNode>> collect =
      items.stream().collect(Collectors.groupingBy(ITreeNode::getParentId));

    toTree(collect,rootList);

    return rootList;

  }


  private static void toTree(Map<Long, List<TreeNode>> collect, List<TreeNode> rootNodeList){
        // 根据分组情况设置子节点
    if(rootNodeList==null || rootNodeList.isEmpty()){
      return ;
    }
    rootNodeList.forEach(c->{
      // 查找子节点
      List<TreeNode> children = collect.get(c.getId());
      c.addChildren(children);
// 递归调用
      toTree(collect,children);
    });
  }

非递归，使用栈

所有递归调用的方法，都可以使用栈完成

 /**
   * 使用栈替换递归<br><br/>
   * 在栈中存储每一次递归方法调用的参数<br><br/>
     * 参考快速排序非递归实现
   *
   * @param items list  数组
   * @param <T>   树节点
   * @return 树形列表
   */
  public static List<TreeNode> quickListToTree(List<TreeNode> items) {

    List<T> rootList = items.stream().filter(c -> c.getParentId() == null || c.getParentId().equals(0L)).collect(Collectors.toList());

    // 用一个栈集合代替递归的函数栈
    Stack<List<T>> quickStack = new Stack<>();

    // 整个列表的跟，已list形式入栈
    quickStack.push(rootList);

    // 循环结束条件,栈为空时
    while (!quickStack.isEmpty()) {
      // 栈顶元素出栈，得到父级元素列表
      List<TreeNode> root = quickStack.pop();
      if (CollectionUtils.isEmpty(root)) {
        break;
      }
      // 根据父级元素，查找所有的下一子级元素信息
      List<TreeNode> childList = items.stream().filter(c -> root.stream().anyMatch(r -> r.getId().equals(c.getParentId())))
        .collect(Collectors.toList());
      // 填充父级的子级元素
      root.forEach(r -> r.addChildren(childList.stream().filter(c -> c.getParentId().equals(r.getId())).collect(Collectors.toList())));
      // 如果下一自己元素为空，则进行下一轮
      if (!CollectionUtils.isEmpty(childList)) {
        quickStack.push(childList);
      }
    }

    return rootList;

  }

组合模式的意图

将对象组合成树结构以表示部分-整体层次结构。 Composite 允许客户端统一处理单个对象和对象的组合。
复合模式让客户端以统一的方式处理各个对象。

背景案例

每个句子都由单词组成，而单词又由字符组成。这些对象中的每一个都是可打印的，它们可以在它们之前或之后打印一些东西，例如句子总是以句号结尾，单词之前总是有空格

在软件中，复合模式是一种设计模式。复合模式描述了一组对象的处理方式与对象的单个实例相同。
复合的目的是将对象“组合”成树结构以表示部分-整体层次结构。实现复合模式可以让客户统一对待单个对象和组合

代码案例

以上面的句子为例。这里我们有基类 LetterComposite 和不同的可打印类型 Letter、Word、Sentence 。

public abstract class LetterComposite {

  private final List<LetterComposite> children = new ArrayList<>();

  public void add(LetterComposite letter) {
    children.add(letter);
  }

  public int count() {
    return children.size();
  }

  protected void printThisBefore() {
  }

  protected void printThisAfter() {
  }

  public void print() {
    printThisBefore();
    children.forEach(LetterComposite::print);
    printThisAfter();
  }
}

public class Letter extends LetterComposite {

  private final char character;

  public Letter(char c) {
    this.character = c;
  }

  @Override
  protected void printThisBefore() {
    System.out.print(character);
  }
}

public class Word extends LetterComposite {

  public Word(List<Letter> letters) {
    letters.forEach(this::add);
  }

  public Word(char... letters) {
    for (char letter : letters) {
      this.add(new Letter(letter));
    }
  }

  @Override
  protected void printThisBefore() {
    System.out.print(" ");
  }
}

public class Sentence extends LetterComposite {

  public Sentence(List<Word> words) {
    words.forEach(this::add);
  }

  @Override
  protected void printThisAfter() {
    System.out.print(".");
  }
}

组装

public class Messenger {

  LetterComposite messageFromOrcs() {

    var words = List.of(
        new Word('W', 'h', 'e', 'r', 'e'),
        new Word('t', 'h', 'e', 'r', 'e'),
        new Word('i', 's'),
        new Word('a'),
        new Word('w', 'h', 'i', 'p'),
        new Word('t', 'h', 'e', 'r', 'e'),
        new Word('i', 's'),
        new Word('a'),
        new Word('w', 'a', 'y')
    );

    return new Sentence(words);

  }

  LetterComposite messageFromElves() {

    var words = List.of(
        new Word('M', 'u', 'c', 'h'),
        new Word('w', 'i', 'n', 'd'),
        new Word('p', 'o', 'u', 'r', 's'),
        new Word('f', 'r', 'o', 'm'),
        new Word('y', 'o', 'u', 'r'),
        new Word('m', 'o', 'u', 't', 'h')
    );

    return new Sentence(words);

  }

}

使用

var orcMessage = new Messenger().messageFromOrcs();
orcMessage.print(); // Where there is a whip there is a way.
var elfMessage = new Messenger().messageFromElves();
elfMessage.print(); // Much wind pours from your mouth.

何时使用设计模式

• 想要表示对象的部分-整体层次结构
• 希望客户端能够忽略对象组合和单个对象之间的差异。客户端将统一处理复合结构中的所有对象。