前端树结构数据常用操作汇总 - zptime/blog GitHub Wiki

主要介绍了树结构数据的一些常用操作函数，如树的遍历、树转列表、列表转树、树节点查找、树节点路径查找等等。

结合到实际项目中，进行了一些变化处理，如穿梭框组件的封装，本质上是对数据的处理，对数据的过滤以及状态的更改等，反映到页面上展示。

模拟的数据如下所示：

const provinceList = [
  {
    id: "1000",
    label: "湖北省",
    children: [
      {
        id: "1001",
        pid: "1000",
        label: "武汉",
        children: [
          { id: "100101", pid: "1001", label: "洪山区" },
          { id: "100102", pid: "1001", label: "武昌区" },
          { id: "100103", pid: "1001", label: "汉阳区" },
        ],
      },
      { id: "1020", pid: "1000", label: "咸宁" },
      { id: "1022", pid: "1000", label: "孝感" },
      { id: "1034", pid: "1000", label: "襄阳" },
      { id: "1003", pid: "1000", label: "宜昌" },
    ],
  },
  {
    id: "1200",
    value: "江苏省",
    label: "江苏省",
    children: [
      { id: "1201", pid: "1200", label: "南京" },
      { id: "1202", pid: "1200", label: "苏州" },
      { id: "1204", pid: "1200", label: "扬州" },
    ],
  },
];

树的遍历

深度优先遍历

/**
 *  深度优先遍历
 *  @params {Array} tree 树数据
 *  @params {Array} func 操作函数
 */
const dfsTransFn = (tree, func) => {
  tree.forEach((node) => {
    func(node);
    // 如果子树存在，递归调用
    if (node.children?.length) {
      dfsTransFn(node.children, func);
    }
  });
  return tree;
};

// 打印节点
dfsTransFn(tree, (node) => {
  console.log(`${node.id}...${node.value}`);
});

深度循环遍历

与广度优先类似，要维护一个队列。不过本函数是加到队列最前面，而广度优先遍历是加到队尾。

const dfsTreeFn = (tree, func) => {
  let node,
    list = [...tree];
  // shift()-取第一个
  while ((node = list.shift())) {
    func(node);
    // 如果子树存在，递归调用
    // 子节点追加到队列最前面`unshift`
    node.children && list.unshift(...node.children);
  }
};

广度优先遍历

/**
 *  广度优先遍历
 *  @params {Array} tree 树数据
 *  @params {Array} func 操作函数
 */
const bfsTransFn = (tree, func) => {
  let node,
    list = [...tree];
  // shift()-取第一个；pop()-取最后一个
  while ((node = list.shift())) {
    func(node);
    // 如果子树存在，递归调用
    node.children && list.push(...node.children);
  }
};

// 打印节点
bfsTransFn(tree, (node) => {
  console.log(`${node.id}...${node.value}`);
});

整体效果

树转列表

深度优先递归

const dfsTreeToListFn = (tree, result = []) => {
  if (!tree?.length) {
    return [];
  }
  tree.forEach((node) => {
    result.push(node);
    console.log(`${node.id}...${node.label}`); // 打印节点信息
    node.children && dfsTreeToListFn(node.children, result);
  });
  return result;
};

广度优先递归

const bfsTreeToListFn = (tree, result = []) => {
  let node,
    list = [...tree];
  while ((node = list.shift())) {
    result.push(node);
    console.log(`${node.id}...${node.label}`); // 打印节点信息
    node.children && list.push(...node.children);
  }
  return result;
};

整体效果

循环实现

export const treeToListFn = (tree) => {
  let node,
    result = tree.map((node) => ((node.level = 1), node));
  for (let i = 0; i < result.length; i++) {
    // 没有子节点，跳过当前循环，进入下一个循环
    if (!result[i].children) continue;
    // 有子节点，遍历子节点，添加层级信息
    let list = result[i].children.map(
      (node) => ((node.level = result[i].level + 1), node)
    );
    // 将子节点加入数组
    result.splice(i + 1, 0, ...list);
  }
  return result;
};

列表转树

const listToTreeFn = (list) => {
  // 建立了id=>node的映射
  let obj = list.reduce(
    // map-累加器，node-当前值
    (map, node) => ((map[node.id] = node), (node.children = []), map),
    // 初始值
    {}
  );
  return list.filter((node) => {
    // 寻找父元素的处理：
    // 1. 遍历list：时间复杂度是O(n)，而且在循环中遍历，总体时间复杂度会变成O(n^2)
    // 2. 对象取值：时间复杂度是O(1)，总体时间复杂度是O(n)
    obj[node.pid] && obj[node.pid].children.push(node);
    // 根节点没有pid，可当成过滤条件
    return !node.pid;
  });
};

查找节点

判断某个节点是否存在，存在返回 true，否则返回 false

const treeFindFn = (tree, func) => {
  for (let node of tree) {
    if (func(node)) return node;
    if (node.children) {
      let result = treeFindFn(node.children, func);
      if (result) return result;
    }
  }
  return false;
};

// 测试代码
let findFlag1 = treeFindFn(provinceList, (node) => node.id === "1020");
let findFlag2 = treeFindFn(provinceList, (node) => node.id === "100125");
console.log(`1020 is ${JSON.stringify(findFlag1)}, 100125 is ${findFlag2}`);

// 打印结果：
1020 is {"id":"1020","pid":"1000","label":"咸宁","key":"1020","title":"咸宁","level":2,"children":[]}, 100125 is null

查找节点路径

const treeFindPathFn = (tree, func, path = []) => {
  if (!tree) return [];

  for (let node of tree) {
    path.push(node.id);
    if (func(node)) return path;
    if (node.children) {
      const findChild = treeFindPathFn(node.children, func, path);
      if (findChild.length) return findChild;
    }
    path.pop();
  }
  return [];
};

// 测试代码
let findPathFlag = treeFindPathFn(
  provinceList,
  (node) => node.id === "100102"
);
console.log(`100102 path is ${findPathFlag}`);

// 打印结果
100102 path is 1000,1001,100102

整体效果

实际函数应用

页面展示

<template>
  <div class="demo-block">
    <div class="demo-block-title">穿梭框数据处理函数：</div>
    <div class="demo-block-content">
      <div class="demo-block-title">原数据：</div>
      <a-tree blockNode checkable defaultExpandAll :tree-data="provinceData" />
    </div>
    <div
      class="demo-block-content"
      style="margin-left: 40px;vertical-align: top;"
    >
      <div class="demo-block-title">处理后数据：filterSourceTreeFn</div>
      <a-tree
        blockNode
        checkable
        defaultExpandAll
        :tree-data="optProvinceData"
      />
    </div>
  </div>
</template>

<script>
  import * as R from "ramda";
  import provinceList from "./mock.json";
  export default {
    data() {
      return {
        provinceData: [],
        optProvinceData: [],
      };
    },
  };
</script>

<style lang="scss"></style>

数据转化(遍历)

将模拟数据转为组件需要的数据，遍历数据，添加 title 和 key 字段

const treeTransFn = (tree) =>
  dfsTransFn(tree, (o) => {
    o["key"] = o.id;
    o["title"] = o.label;
  });

this.provinceData = treeTransFn(provinceList);

整体效果

选中节点禁用

const disabledTreeFn = (tree, targetKeys) => {
  tree.forEach((o) => {
    let flag = targetKeys.includes(o.id);
    o["key"] = o.id;
    o["title"] = flag ? `${o.label}(已配置)` : o.label;
    o["disabled"] = flag;
    o.children && disabledTreeFn(o.children, targetKeys);
  });
  return tree;
};

this.provinceData = disabledTreeFn(provinceList, ["100101", "1022", "1200"]);

整体效果

选中节点过滤

源数据框数据处理，过滤掉选中节点，不展示

/**
 *  选中节点过滤
 *  @params {Array} tree 树数据
 *  @params {Array} targetKeys 选中数据key集合
 * 过滤条件是：当前节点且其后代节点都没有符合条件的数据
 */
const filterSourceTreeFn = (tree = [], targetKeys = [], result = []) => {
  R.forEach((o) => {
    // 1. 判断当前节点是否含符合条件的数据：是-继续；否-过滤
    if (targetKeys.indexOf(o.id) < 0) {
      // 2. 判断是否含有子节点：是-继续；否-直接返回
      if (o.children?.length) {
        // 3. 子节点递归处理
        o.children = filterSourceTreeFn(o.children, targetKeys);
        // 4. 存在子节点，且子节点也有符合条件的子节点，直接返回
        if (o.children.length) result.push(o);
      } else {
        result.push(o);
      }
    }
  }, tree);
  return result;
};

this.optProvinceData = treeTransFn(
  filterSourceTreeFn(R.clone(provinceList), ["100101", "1022", "1200"])
);

整体效果

有时候，当父节点满足条件，但是没有满足条件的子节点时，也要正常返回数据。上面的方法就不符合条件了，改成如下实现了。

export const filterSourceTreeFn = (tree = [], targetKeys = []) => {
  return R.map(
    (o) => {
      // 2. 存在子节点，递归处理
      if (o.children?.length) {
        o.children = filterSourceTreeFn(o.children, targetKeys) || [];
      }
      return o;
    },
    // 1. 过滤不符合条件的数据
    R.filter(
      (r) => targetKeys.indexOf(r.id) < 0,
      // 避免直接修改原数据，需要R.clone()处理一下
      R.clone(tree)
    )
  );
};

整体效果

选中节点保留

目标数据处理，仅仅展示选中节点，其他数据过滤掉

// 过滤条件是：当前节点或者是其后代节点有符合条件的数据
filterTargetTreeFn = (tree = [], targetKeys = []) => {
  return R.filter((o) => {
    // 当前节点符合条件，则直接返回
    if (R.indexOf(o.id, targetKeys) > -1) return true;
    // 否则看其子节点是否符合条件
    if (o.children?.length) {
      // 子节点递归调用
      o.children = filterTargetTreeFn(o.children, targetKeys);
    }
    // 存在后代节点是返回
    return o.children && o.children.length;
  }, tree);
};

this.optProvinceData = treeTransFn(
  filterTargetTreeFn(R.clone(provinceList), ["100101", "1022", "1200"])
);

整体效果

关键词过滤

export const filterKeywordTreeFn = (tree = [], keyword = "") => {
  if (!(tree && tree.length)) {
    return [];
  }
  if (!keyword) {
    return tree;
  }

  return R.filter((o) => {
    // 1. 父节点满足条件，直接返回
    if (o.title.includes(keyword)) {
      return true;
    }
    if (o.children?.length) {
      // 2. 否则，存在子节点时，递归处理
      o.children = filterKeywordTreeFn(o.children, keyword);
    }
    // 3. 子节点满足条件时，返回
    return o.children && o.children.length;
    // 避免修改原数据，此处用R.clone()处理一下
  }, R.clone(tree));
};

整体效果

⚠️ **GitHub.com Fallback** ⚠️