过滤/筛选树节点过滤

过滤/筛选树节点

又是树，是我跟树杠上了吗？—— 不，是树的问题太多了！
相关文章推荐：

使用递归遍历并转换树形数据（以 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 --> N10N6("6 | P6mtcgfCD") N6 --> N8("8 | m6o5UsytQ0") N10("10 | lhDGTNeeSxLNJ") N6 --> N14("14 | ysYwG8EFLAu1a") N10 --> N16("16 | RKuQs4ki65wo")

不过这个 filterTree 有点小瑕疵：

递归调用时还需要传入 predicate，有点繁琐
传入参数应该限制在 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(...) { ... } }

查找节点（不含完整子树）查找节点就要稍微复杂了点了，因为需要保留路径。判断当前节点是否可以删除需要对自己情况进行判断之外，还取决于其所有子孙节点是否可以删除。与前面“过滤掉”的逻辑相比，有两点变化：

不管当前节点是否保留，均需要递归向下，把子孙中符合条件的节点都找出来
只要子孙中存在符合条件的节点，当前节点就应该保留。

这样处理后的节点，所有叶节点都应该符合查找条件。比如在示例数据中按 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 --> N10N1("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