乐趣区

关于树形结构:过滤筛选树节点

jiezi

过滤 / 筛选树节点

又是树，是我跟树杠上了吗？—— 不，是树的问题太多了！

🔗 相干文章举荐：

  • 应用递归遍历并转换树形数据（以 TypeScript 为例）
  • 从列表生成树 (JavaScript/TypeScript)

过滤和筛选是一个意思，都是 filter。

对于列表来说，过滤就是丢掉不须要的，留下须要的。但对于树来说就得分状况了。

  • 如果想“过滤掉”（丢掉）某些节点，会把它的子节点一并摈弃，就像砍树枝一样，干之不存，枝将焉附？这种状况多是去除不须要的子树。

  • 如果是想“查找”某些节点，会将找到的节点及其上溯到根的所有节点都保留下来。对于找到的节点，除了保留其残缺门路之外，对其子树还有两种解决形式：

    • 一种是“到此为止”，也就是说，如果其子树中没有符合条件的节点，那就不须要了，砍掉。须要定位到符合条件的节点以便后继操作是采纳这种形式，这也是最罕用的查找形式。
    • 另一种是保留其残缺子树。如果须要应用符合条件节点的子节点（比方抉择指定部门及其子部门）会采纳这种形式。

过滤和查找的次要区别在于：“过滤”通常会遇到不合乎保留条件（或合乎剔除条件）的节点就间接砍掉，不论其子树中是否还存在合乎保留条件的节点；而查找则会始终找到叶节点上，只有整条门路都没有合乎保留条件的节点，才会从其某个先人节点上砍掉（先人节点是否保留取决于其下是否存在合乎保留条件的子孙节点）。

上面一样一样来。示例代码应用 TypeScript 编写，示例数据起源 于从列表生成树 (JavaScript/TypeScript) 一文，同时应用该文中定义的节点类型接口：

interface TreeNode {
    id: number;
    parentId: number;
    label: string;
    children?: TreeNode[]}

过滤掉不须要的节点

过滤掉不须要的节点，思路比较简单：

  • 遍历以后节点的所有子节点，须要的留，不须要的删
  • 对留下的节点，通过递归进行过滤

按此思路，TypeScript 代码是

/**
 * @param nodes 要过滤的树节点集（多根）* @param predicate 过滤条件，返回 `true` 保留
 * @returns 过滤后的树节点集
 */
function filterTree(nodes: TreeNode[] | undefined,
    predicate: (node: TreeNode) => boolean
): TreeNode[] | undefined {if (!nodes?.length) {return nodes;}

    // 间接应用 Array 的 filter 能够过滤当层节点
    return nodes.filter(it => {
        // 不符合条件的间接砍掉
        if (!predicate(it)) {return false;}

        // 符合条件的保留，并且须要递归解决其子节点
        it.children = filterTree(it.children, predicate);
        return true;
    });
}

如果对示例数据（见前文）进行过滤，仅保留 id 是偶数的节点，那后果是

flowchart LR
%%{init: { "theme": "forest"} }%%

S(("Virtual\nRoot"))
S --> N6
S --> N10

N6("6 | P6mtcgfCD")
N6 --> N8("8 | m6o5UsytQ0")
N10("10 | lhDGTNeeSxLNJ")
N6 --> N14("14 | ysYwG8EFLAu1a")
N10 --> N16("16 | RKuQs4ki65wo")

不过这个 filterTree 有点小瑕疵：

  1. 递归调用时还须要传入 predicate，有点繁琐
  2. 传入参数应该限度在 TreeNode[] 类型上，增加 undefined 只是为了简化递归调用（不必先判空）

解决起来也简略，加一层接口封装一下（门面模式）：

/**
 * @param nodes 要过滤的树节点集（多根）* @param predicate 过滤条件，返回 `true` 保留
 * @returns 过滤后的树节点集
 */
function filterTree(nodes: TreeNode[],
    predicate: (node: TreeNode) => boolean
): TreeNode[] {return filter(nodes) ?? [];

    // 原 filterTree，更名，并删除 predicate 参数
    function filter(nodes: TreeNode[] | undefined): TreeNode[] | undefined {if (!nodes?.length) {return nodes;}

        return nodes.filter(it => {if (!predicate(it)) {return false;}
            // 递归调用不须要再传入 predicate
            it.children = filter(it.children);
            return true;
        });
    }
}

理论应用的时候，可能传入的可能是单根树 (TreeNode)，也有可能是多根 (TreeNode[])，那能够写个重载：

function filterTree(node: TreeNode, predicate: (node: TreeNode) => boolean): TreeNode;
function filterTree(nodes: TreeNode[], predicate: (node: TreeNode) => boolean): TreeNode[];
function filterTree(tree: TreeNode | TreeNode[],
    predicate: (node: TreeNode) => boolean
): TreeNode | TreeNode[] {if (Array.isArray(tree)) {return filter(tree) ?? [];} else {tree.children = filter(tree.children);
        return tree;
    }

    function filter(...) {...}
}

查找节点（不含残缺子树）

查找节点就要略微简单了点了，因为须要保留门路。判断以后节点是否能够删除须要对本人状况进行判断之外，还取决于其所有子孙节点是否能够删除。与后面“过滤掉”的逻辑相比，有两点变动：

  1. 不论以后节点是否保留，均须要递归向下，把子孙中符合条件的节点都找进去
  2. 只有子孙中存在符合条件的节点，以后节点就应该保留。

这样解决后的节点，所有叶节点都应该合乎查找条件。比方在示例数据中按 id 参整除 6 来查找节点，后果是：

flowchart LR
%%{init: { "theme": "forest"} }%%
classDef found fill:#ffeeee,stroke:#cc6666;

S(("Virtual\nRoot")) --> N1
S --> N6:::found;

N1("1 | 8WUg35y")
N1 --> N4("4 | IYkxXlhmU12x")
N4 --> N5("5 | p2Luabg9mK2")
N6("6 | P6mtcgfCD")
N1 --> N7("7 | yluJgpnqKthR")
N7 --> N12("12 | 5W6vy0EuvOjN"):::found
N5 --> N13("13 | LbpWq")
N13 --> N18("18 | 03X6e4UT"):::found

依据下面的逻辑，写一个 findTreeNode()：

function findTreeNode(node: TreeNode, predicate: (node: TreeNode) => boolean): TreeNode;
function findTreeNode(nodes: TreeNode[], predicate: (node: TreeNode) => boolean): TreeNode[];
function findTreeNode(tree: TreeNode | TreeNode[],
    predicate: (node: TreeNode) => boolean
): TreeNode | TreeNode[] {if (Array.isArray(tree)) {return filter(tree) ?? [];} else {tree.children = filter(tree.children);
        return tree;
    }

    function filter(nodes: TreeNode[] | undefined): TreeNode[] | undefined {if (!nodes?.length) {return nodes;}
        return nodes.filter(it => {// 先筛选子树，如果子树中没有符合条件的，children 会是 [] 或 undefined
            const children = filter(it.children);
            // 依据以后节点状况和子树筛选后果判断是否保留以后节点
            if (predicate(it) || children?.length) {
                // 如果要保留，children 应该用筛选进去的那个；不保留的话就不 care 子节点了
                it.children = children;
                return true;
            }
            return false;
        });
    }
}

上面把代码批改下，在后果中保留子树。

查找节点（含残缺子树）

这个思路跟最下面那个“剔除”的思路正好相同，

  • 遇到符合条件的节点，间接保留整棵子树，也不须要递归去解决了
  • 不符合条件的节点，递归进去持续找

既然都是查找，能够给 findTreeNode() 增加一个 keepSubTree: boolean 参数来扩大函数性能。接口局部扭转如下：

function findTreeNode(
    node: TreeNode,
    predicate: (node: TreeNode) => boolean,
    keepSubTree?: boolean  // <--
): TreeNode;
function findTreeNode(nodes: TreeNode[],
    predicate: (node: TreeNode) => boolean,
    keepSubTree?: boolean  // <--
): TreeNode[];
function findTreeNode(tree: TreeNode | TreeNode[],
    predicate: (node: TreeNode) => boolean,
    keepSubTree: boolean = false  // <--
): TreeNode | TreeNode[] {...}

而后须要批改的中央次要是 Array.prototype.filter 回调函数，能够先把原来的箭头函数提取进去，命名为 filterWithoutSubTree()。

而后再写一个 filterWithSubTree() 处理函数。依据 keepSubTree 的值来决定应用哪一个过滤器。要害代码如下：

function findTreeNode(...): TreeNode | TreeNode[] {
    const filterHandler = keepSubTree ? filterWithSubTree : filterWithoutSubTree;
    //    ^^^^^^^^^^^^^

    if (Array.isArray(tree)) {...} else {...}

    function filter(nodes: TreeNode[] | undefined): TreeNode[] | undefined {if (!nodes?.length) {return nodes;}
        return nodes.filter(filterHandler);
        //                  ^^^^^^^^^^^^^
    }

    function filterWithSubTree(it: TreeNode): boolean {
        // 如果符合条件，保留整棵子树，不须要递归进去
        if (predicate(it)) {return true;}

        // 否则依据子孙节点的状况来决定是否须要保留以后节点（作为门路节点）it.children = filter(it.children);
        return !!it.children?.length;
    }

    function filterWithoutSubTree(it: TreeNode): boolean {...}
}

含残缺子树的查找后果示例（查找条件：it => it.id % 4 === 0）如下图：

flowchart LR
%%{init: { "theme": "forest"} }%%
classDef found fill:#ffeeee,stroke:#cc6666;
classDef subs fill:#ffffff;

S(("Virtual\nRoot")) --> N1
S --> N6
S --> N10

N1("1 | 8WUg35y")
N1 --> N4("4 | IYkxXlhmU12x"):::found
N4 --> N5("5 | p2Luabg9mK2"):::subs
N6("6 | P6mtcgfCD")
N1 --> N7("7 | yluJgpnqKthR")
N6 --> N8("8 | m6o5UsytQ0"):::found
N10("10 | lhDGTNeeSxLNJ")
N7 --> N12("12 | 5W6vy0EuvOjN"):::found
N5 --> N13("13 | LbpWq"):::subs
N10 --> N16("16 | RKuQs4ki65wo"):::found
N13 --> N18("18 | 03X6e4UT"):::subs
N7 --> N19("19 | LTJTeF")
N19 --> N20("20 | 3rqUqE3MLShh"):::found
退出移动版