如何判断节点A是节点B的子节点呢？？

小册子里有一篇《如何设计树形结构》，讲了如何根据id和pid进行自关联，查询时在内存中嵌套后返回JSON。最后的效果大概是这样的：

想想上面的结构，甚至有点痛苦，这大概不是严格意义上的树：

但这确实是一个实际开发出来的设计，比如商品分类，省市可以用这种结构设计，姑且称之为树状结构吧。

一位小册子读者昨晚说，他现在期望的 JSON 是这个平铺列表：

也就是说，数据库可能会找到一个List：

public class CascadeTest {
    public static void main(String[] args) throws JsonProcessingException {
        // 假设这是数据库查出来的结果，遵循id-pid结构，根节点pid=0（我故意打乱了顺序）
        List<Person> personList = Arrays.asList(
                new Person(1, 0, new ArrayList()),
                new Person(4, 2, new ArrayList()),
                new Person(3, 1, new ArrayList()),
                new Person(2, 1, new ArrayList()),
                new Person(6, 3, new ArrayList()),
                new Person(5, 2, new ArrayList()),
                new Person(7, 6, new ArrayList())
        );

    }
}
@Data
@AllArgsConstructor
class Person {
    private Integer id;
    private Integer pid;
    private List<Person> children;
}

那么，如何实现get(id)来获取分块的List子节点呢？

我写了一个带有递归的版本，感觉不是很好。你可以在下面的评论中发布你自己的写作方法，甚至可以从表格设计中重构。

我的想法是：

1.虽然这不是严格意义上的树，但是子节点的id肯定要大于父节点的id，所以可以使用id>pid的判断来排除部分节点（子节点插入到数据库之后，父节点id已经生成读取textbox的内容往树控件添加父节点的代码，当然如果是随机的id或者id-pid本质上只是一个业务字段…乱七八糟）。

2.如何判断节点A是节点B的子节点？最直观的想法是从 A 查找到节点 B 或根节点。如果 A-Root 或 A-B 链接包含指定的节点 B读取textbox的内容往树控件添加父节点的代码，则 A 是 B 的子节点。

public class CascadeTest {
    public static void main(String[] args) throws JsonProcessingException {

        List<Person> personList = Arrays.asList(
                new Person(1, 0, new ArrayList()),
                new Person(4, 2, new ArrayList()),
                new Person(3, 1, new ArrayList()),
                new Person(2, 1, new ArrayList()),
                new Person(6, 3, new ArrayList()),
                new Person(5, 2, new ArrayList()),
                new Person(7, 6, new ArrayList())
        );
        ObjectMapper objectMapper = new ObjectMapper();
        System.out.println(objectMapper.writerWithDefaultPrettyPrinter().writeValueAsString(get(personList, 2)));
    }
    public static List<Person> get(List<Person> personList, Integer id) {
        List<Person> result = new ArrayList();
        Map<Integer, Person> personMap = personList
                .stream()
                .collect(Collectors.toMap(Person::getId, person -> person, (pre, next) -> next));

        for (Person person : personList) {
            Set<Integer> personBetween = findPersonBetween(id, person.getId(), personMap, new HashSet());
            if (personBetween.contains(person.getId())) {
                result.add(person);
            }
        }
        return result;
    }
    /**
     * 倒挂的树，从low节点向上追溯至high节点，返回该区间内所有直系节点
     * 比如highId=1, lowId=7，那么结果是[1,3,6,7]
     * ======1
     * ====/   
     * ===2    3
     * ==/    /
     * =4 5   6
     * ======/

     * =====7
     *
     * @param highId
     * @param lowId
     * @param personMap
     * @param personId
     * @return
     */
    private static Set<Integer> findPersonBetween(Integer highId, Integer lowId, Map<Integer, Person> personMap, Set<Integer> personId) {
        // 由于要的是highId的子节点，所以当lowId>highId时，直接返回空set，因为肯定不符合条件
        if (lowId < highId) {
            return new HashSet();
        }
        // 从自己开始计算
        Person self = personMap.get(lowId);
        // 只要不为null，就持续收集
        if (self != null) {
            personId.add(self.getId());

        }
        // 递归的结束条件：self不存在 || self是指定的高节点
        if (self == null || self.getId().equals(highId)) {
            personId.add(highId);
            return personId;
        }
        // 否则继续从下往上爬
        return findPersonBetween(highId, self.getPid(), personMap, personId);
    }
}
@Data
@AllArgsConstructor
class Person {
    private Integer id;
    private Integer pid;
    private List<Person> children;
}

昨晚小册子群里也有讨论。也欢迎您发布自己的代码。最好根据本文实际案例编写代码。