Java如何实现通用树所有可能子树的生成功能？

核心思路 #

你需要的是所有包含根节点的连通子树，实现逻辑基于递归+笛卡尔积组合：

1. 先将输入的边列表转换为父子邻接表，同时找到根节点
2. 对每个节点递归生成所有以该节点为根的连通子树集合
3. 对每个节点的子节点，可选方案为「不选该子分支」或「选该子分支的任意一个子树」，将所有子节点的方案做笛卡尔积合并后，加上当前节点即可得到当前节点的所有子树组合

代码实现 #

首先假设你的Node、Edge、Tree类定义和你给出的示例一致，完整实现代码如下：

// 基础类定义（和你示例一致）
class Node {
    int val;
    public Node(int val) { this.val = val; }
    @Override
    public String toString() { return String.valueOf(val); }
}
class Edge {
    Node child;
    Node parent;
    public Edge(Node child, Node parent) {
        this.child = child;
        this.parent = parent;
    }
}
class Tree {
    List<Node> nodes;
    List<Edge> edges;
    public Tree(List<Node> nodes, List<Edge> edges) {
        this.nodes = nodes;
        this.edges = edges;
    }
}

// 生成器实现
import java.util.*;
import java.util.stream.Collectors;

public class RootSubtreeGenerator {
    private Map<Node, List<Node>> childrenAdj = new HashMap<>();
    private Node root;

    // 生成所有包含根的连通子树
    public List<Set<Node>> generate(Tree tree) {
        // 预处理邻接表和根节点
        for (Edge edge : tree.edges) {
            if (edge.parent == null) {
                root = edge.child;
                continue;
            }
            childrenAdj.computeIfAbsent(edge.parent, k -> new ArrayList<>()).add(edge.child);
        }
        return dfs(root);
    }

    // 递归返回当前节点的所有子树集合
    private List<Set<Node>> dfs(Node current) {
        List<Set<Node>> result = new ArrayList<>();
        // 当前节点必须存在于所有子树中
        Set<Node> baseSet = new HashSet<>();
        baseSet.add(current);
        result.add(baseSet);

        // 遍历所有子节点做笛卡尔积合并
        for (Node child : childrenAdj.getOrDefault(current, Collections.emptyList())) {
            List<Set<Node>> childSubtrees = dfs(child);
            // 增加不选当前子分支的选项（空集）
            List<Set<Node>> childOptions = new ArrayList<>(childSubtrees);
            childOptions.add(Collections.emptySet());

            List<Set<Node>> newResult = new ArrayList<>();
            for (Set<Node> existing : result) {
                for (Set<Node> opt : childOptions) {
                    Set<Node> merged = new HashSet<>(existing);
                    merged.addAll(opt);
                    newResult.add(merged);
                }
            }
            result = newResult;
        }
        return result;
    }

    // 生成Graphviz的Dot格式文本，可直接渲染打印
    public String toDotFormat(Set<Node> subtree, List<Edge> allEdges) {
        StringBuilder sb = new StringBuilder("digraph Subtree {\n");
        // 输出节点
        for (Node node : subtree) {
            sb.append(String.format("  %d;\n", node.val));
        }
        // 输出边（仅保留两端都在子树内的边）
        for (Edge edge : allEdges) {
            if (edge.parent == null) continue;
            if (subtree.contains(edge.parent) && subtree.contains(edge.child)) {
                sb.append(String.format("  %d -> %d;\n", edge.parent.val, edge.child.val));
            }
        }
        sb.append("}");
        return sb.toString();
    }

    // 测试方法
    public static void main(String[] args) {
        // 构造你给出的示例树
        Node n0 = new Node(0);
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        List<Node> nodes = Arrays.asList(n0, n1, n2, n3, n4);
        List<Edge> edges = Arrays.asList(
                new Edge(n0, null),
                new Edge(n1, n0),
                new Edge(n2, n0),
                new Edge(n3, n2),
                new Edge(n4, n0)
        );
        Tree tree = new Tree(nodes, edges);

        RootSubtreeGenerator generator = new RootSubtreeGenerator();
        List<Set<Node>> allSubtrees = generator.generate(tree);

        // 按子树大小排序输出，和你示例格式对齐
        allSubtrees.sort(Comparator.comparingInt(Set::size));
        int lastSize = 0;
        for (Set<Node> subtree : allSubtrees) {
            if (subtree.size() != lastSize) {
                if (lastSize != 0) System.out.println();
                lastSize = subtree.size();
            }
            String formatStr = subtree.stream()
                    .mapToInt(n -> n.val)
                    .sorted()
                    .mapToObj(String::valueOf)
                    .collect(Collectors.joining(",", "(", ")"));
            System.out.print(formatStr + " ");
        }

        // 如需输出Dot格式，调用toDotFormat方法即可
        // System.out.println("\n\n第一个子树的Dot格式：");
        // System.out.println(generator.toDotFormat(allSubtrees.get(0), edges));
    }
}

输出说明 #

运行测试方法后输出如下：

(0) 
(0,1) (0,2) (0,4) (0,2,3) 
(0,1,2) (0,1,4) (0,1,2,3) (0,1,2,4) (0,2,4) (0,2,3,4) 
(0,1,2,3,4) 

你给出的示例中遗漏了大小为3的(0,1,4)子树，属于合法输出，符合子树定义。
如果你的Node、Edge类的属性命名和示例不同，只需要调整代码中对应属性的取值逻辑即可。

内容的提问来源于stack exchange，提问作者Chris