Java如何在树结构上做模糊查询

开发企业后台管理应用时，经常会遇到一种场景：在树结构上做模糊查询。
比如：公司组织架构树、分类树等，通常是在页面上的文本框中输入一个关键字，例如"数据"，然后在公司组织架构树中过滤出名字包含数据的部门，且保持树结构不变。
公司的一级部门、二级部门、三级部门等等，名字都有可能包含"数据"，比如一级部门叫大数据部门，二级部门叫数据分析部门或数据开发部门等等，这些都是符合要求的。

下面我将造出一个简单的分类树，并实现在树结构上模糊查询的功能（这里为了简单，将树的层级固定为三级，但实际上树的层级是未知的且远远不止三级，那就需要用到递归了）。

package cc.oyz.netty;


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

class TreeNode {
    int id; // 节点ID
    String name; // 节点名称
    int parentId; // 父节点ID
    List<TreeNode> children; // 子节点列表

    // 构造函数
    public TreeNode(int id, String name, int parentId) {
        this.id = id;
        this.name = name;
        this.parentId = parentId;
        this.children = new ArrayList<>(); // 初始化子节点列表
    }

    // 添加子节点方法
    public void addChild(TreeNode child) {
        children.add(child);
    }

    // 模糊搜索方法，返回符合条件的节点列表
    public List<TreeNode> fuzzySearch(String query) {
        List<TreeNode> results = new ArrayList<>(); // 存储搜索结果
        fuzzySearchHelper(this, query, results); // 调用搜索辅助方法
        return results;
    }

    // 判断节点是否有子节点的方法
    private boolean hasLeaf(TreeNode node) {
        for (TreeNode child : node.children) {
            if (child.children.isEmpty()) { // 如果存在叶子节点，返回true
                return true;
            }
        }
        return false; // 否则返回false
    }

    // 判断节点的子节点是否存在符合条件的节点的方法
    private boolean hasMatchingChild(TreeNode node, String query) {
        for (TreeNode child : node.children) {
            if (child.name.contains(query) || hasMatchingChild(child, query)) {
                return true; // 如果子节点的名称包含查询字符串，或者子节点的子节点存在符合条件的节点，则返回true
            }
        }
        return false; // 否则返回false
    }

    // 递归搜索辅助方法
    private void fuzzySearchHelper(TreeNode node, String query, List<TreeNode> results) {
        // 如果当前节点的值包含查询字符串，并且至少有一个子节点也符合查询条件，则将其添加到结果列表中
        if (node.name.contains(query) || hasMatchingChild(node, query)) {
            results.add(node);
        }

        // 递归搜索子节点
        List<TreeNode> removableChildren = new ArrayList<>();
        for (TreeNode child : node.children) {
            fuzzySearchHelper(child, query, results);
            if (!hasLeaf(child)) {
                removableChildren.add(child);
            }
        }

        // 删除没有树叶的子节点
        for (TreeNode child : removableChildren) {
            node.children.remove(child);
        }
    }
}

package cc.oyz.netty;

import org.junit.Test;
import java.util.List;

public class TreeTest {

    @Test
    public void test1(){

        // 创建一个示例树
        TreeNode root = new TreeNode(1, "root", 0);
        TreeNode node1 = new TreeNode(2, "node1", 1);
        TreeNode node2 = new TreeNode(3, "node2", 1);
        TreeNode node3 = new TreeNode(4, "node3", 3);
        TreeNode node4 = new TreeNode(5, "node4", 3);
        TreeNode subnode1 = new TreeNode(6, "subnode1", 2);
        TreeNode subnode2 = new TreeNode(7, "subnode2", 2);

        TreeNode node8 = new TreeNode(8, "研发部门", 1);
        TreeNode node9 = new TreeNode(9, "张三", 1);
        TreeNode node10 = new TreeNode(10, "李四", 8);
        TreeNode node11 = new TreeNode(11, "王五", 1);

        TreeNode node12 = new TreeNode(12, "销售部门", 1);
        TreeNode node13 = new TreeNode(13, "小朱", 1);
        TreeNode node14 = new TreeNode(14, "米工", 8);
        TreeNode node15 = new TreeNode(15, "小武", 1);

        root.addChild(node1);
        root.addChild(node2);
        root.addChild(node8);
        root.addChild(node12);
        node1.addChild(subnode1);
        node1.addChild(subnode2);
        node2.addChild(node3);
        node2.addChild(node4);
        node8.addChild(node9);
        node8.addChild(node10);
        node8.addChild(node11);
        node12.addChild(node13);
        node12.addChild(node14);
        node12.addChild(node15);

        // 在树中进行模糊搜索
        List<TreeNode> searchResults = root.fuzzySearch("武");

        // 打印搜索结果
        System.out.println("搜索结果:");
        for (TreeNode result : searchResults) {
            System.out.println("ID: " + result.id + ", Name: " + result.name);
        }

    }

}

假如查询的关键字是“武”，运行，输出结果如下：

假如查询的关键字是“1”，运行，输出结果如下：