在Java中将分层列表转换为平面列表

Question

我有一个层级结构的列表，如下所示，我想将其转换为扁平的列表。

我编写了一个名为"convertToFlatList"的方法，并使用它。但是最终结果中缺少一些元素。我做错了什么？

此外，除了我使用的方法之外，是否有更好的方法将我的列表转换为扁平列表？

我添加了一个示例代码和一些类似于我在场景中使用的对象。最终结果应该是1、2、3、4、5、6、7。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main
{
  public static void main(String[] args)
  {
    Member memberOne = new Member(1);
    Member memberTwo = new Member(2);
    Member memberThree = new Member(3);
    Member memberFour = new Member(4);
    Member memberFive = new Member(5);
    Member memberSix = new Member(6);
    Member memberSeven = new Member(7);

    memberTwo.setChildren(Arrays.asList(memberThree, memberFour));
    memberFour.setChildren(Arrays.asList(memberFive, memberSix));

    List<Member> memberList = Arrays.asList(memberOne, memberTwo, memberSeven);
    List<Member> flatList = new ArrayList<>();
    List<Member> convertedList = convertToFlatList(memberList, flatList);
    System.out.println(convertedList);
  }

  private static List<Member> convertToFlatList(List<Member> memberList, List<Member> flatList)
  {
    for (Member member : memberList)
    {
      if (member.getChildren() != null)
      {
        convertToFlatList(member.getChildren(), flatList);
      }
      else
      {
        flatList.add(member);
      }
    }
    return flatList;
  }
}

class Member
{
  private List<Member> children;

  private int memberId;

  Member(int memberId)
  {
    this.memberId = memberId;
  }

  List<Member> getChildren()
  {
    return children;
  }

  void setChildren(List<Member> children)
  {
    this.children = children;
  }

  int getMemberId()
  {
    return memberId;
  }

  void setMemberId(int memberId)
  {
    this.memberId = memberId;
  }

  @Override
  public String toString()
  {
    return String.valueOf(this.memberId);
  }
}

- Sandeepa

---

无论Member是否有子元素，您都需要始终调用flatList.add(member);。 - Ivan

Answer 1

如果您使用Java 8，只需将此方法添加到Member类中：

public Stream<Member> streamAll(){
    if(getChildren() == null){
        return Stream.of(this);
    }
    return Stream.concat(Stream.of(this), getChildren().stream().flatMap(Member::streamAll));
}

或者，如果您始终将children初始化为空列表，则可以删除空值检查：

public Stream<Member> streamAll(){
    return Stream.concat(Stream.of(this), getChildren().stream().flatMap(Member::streamAll));
}

然后获取平面列表:

List<Member> convertedList = memberList.stream()
                                       .flatMap(Member::streamAll)
                                       .collect(Collectors.toList());

- Ricola

---

假设孩子们总是初始化为空列表。在递归中，当满足某些条件时终止。你的第二个程序是如何工作的？它在那里起作用。我只是想了解它是如何工作的。 - Sandeepa

如果children是一个空列表，那么getChildren().stream().flatMap(Member::streamAll))返回一个空流，然后将Stream.of(this)和一个空流连接起来就是Stream.of(this)。 - Ricola

Answer 2

如果一个Member有子节点，你需要将子节点正确添加到扁平化列表中，但是你会忽略Member本身。只需将成员的添加移至else块之外即可解决问题：

private static List<Member> 
convertToFlatList(List<Member> memberList, List<Member> flatList)
{
    for (Member member : memberList)
    {
        // Always add the member to flatList
        flatList.add(memeber);

        // If it has children, add them toore
        if (member.getChildren() != null)
        {
            convertToFlatList(member.getChildren(), flatList);
        }
    }
    return flatList;
}

- Mureinik

Answer 3

使用java-8的flatMap和递归来实现此操作

将convertToFlatList方法更改为只接受一个参数（即List<Member>）

如果getChildren()不为null，则进行递归操作，否则返回当前对象

private static List<Member> convertToFlatList(List<Member> memberList)
  {
       return memberList.stream().flatMap(i->{
          if(Objects.nonNull(i.getChildren())) {
             return Stream.concat(Stream.of(i), convertToFlatList(i.getChildren()).stream());
          }
          return Stream.of(i);

      }).collect(Collectors.toList());

  }   

输出：

[1, 2, 3, 4, 5, 6, 7]

- Ryuzaki L

Answer 4

实际上，这是树的层次/递归遍历问题。以下是问题和解决方案的详细信息：

https://en.wikipedia.org/wiki/Tree_traversal

顺便提一下，这是您问题的遍历（深度优先-前序）：

static class Member {
  List<Member> children = new ArrayList<>();
  int id;
  boolean visit = false;
}
public List<Member> printList(Member member) {
  Stack<Member> stack =  new Stack<>();
  List<Member> list =  new ArrayList<>();
  stack.push(member);
  while(!stack.isEmpty()) {
    Member node = stack.pop();
    list.add(node);
    for(Member m: node.children) {
    stack.push(m);
    }
  }
  return list;
}

- Mostafa Barmshory

---

@BoristheSpider 我不同意。如果你使用堆栈（LIFO）或递归方法，那么它就是深度优先搜索（DFS）。如果你使用队列（FIFO），那么它就是广度优先搜索（BFS）。 - Ricola

@Ricola 这个问题不是关于遍历和方法，而是关于树节点列表。实际上，这个示例代码是深度优先（前序）模式。更多信息请参见https://en.wikipedia.org/wiki/Tree_traversal#Pre-order。 - Mostafa Barmshory

我完全同意，这只是对@BoristheSpider删除评论的回应。 - Ricola