js,关于 tree 数据结构的递归算法工具。

javascript tree

背景：前端日常业务开发的工作中，关于树状数据结构的增删改查肯定避免不了， 这里整理下日常通用的工具函数，方便下次快速改造。

类型、使用数据示例

//以下函数示例的类型合数据 参考这里定义。
type ilist = {
  id: number;
  pid: number | null;
  value: string;
};
type itree = {
  children?: itree[];
} & ilist;

let list: ilist[] = [
  { id: 1, pid: null, value: "item 1" },
  { id: 2, pid: 1, value: "item 1-1" },
  { id: 3, pid: 1, value: "item 1-2" },
  { id: 4, pid: 2, value: "item 1-1-1" },
  { id: 5, pid: null, value: "item 2" },
];

let tree: itree[] = [
  {
    id: 1,
    pid: null,
    value: "item 1",
    children: [
      {
        id: 2,
        pid: 1,
        value: "item 1-1",
        children: [{ id: 4, pid: 2, value: "item 1-1-1" }],
      },
      { id: 3, pid: 1, value: "item 1-2" },
    ],
  },
  { id: 5, pid: null, value: "item 2" },
];

线性列表转树结构

/**
 * 匹配等于父节点的层，增加children，递归匹配查询
 * @param olddata 线性列表数据源
 * @param id 唯一标识
 * @param newdata 转完返回的树结构
 * @returns
 */
const listtotree = (
  olddata: ilist[],
  id: number | null,
  newdata: itree[] = []
) => {
  olddata.foreach((item) => {
    if (item.pid === id) {
      newdata.push(item);
    }
  });
  newdata.foreach((i) => {
    i.children = [];
    listtotree(olddata, i.id, i.children);
    if (i.children.length === 0) {
      delete i.children;
    }
  });
  return newdata;
};

console.log(listtotree(list, null));

树结构转线性列表

/**
 * 递归，把每一个节点push到新数组
 * @param treedata tree数据源
 * @param result 线性列表
 * @returns
 */
const flattentree = (treedata: itree[], result: ilist[] = []) => {
  treedata.foreach((node) => {
    result.push(node);
    if (node.children && node.children?.length > 0) {
      flattentree(node.children, result);
      delete node.children;
    }
  });

  return result;
};

console.log(flattentree(tree));

树：删除一个节点

/**
 * 删除树结构对应条件的某一节点  (引用删除)
 * @param treedata 数据源
 * @param id 唯一标识
 * @returns
 */
const removetreeitem = (treedata: itree[], id: number) => {
  if (!treedata || !treedata.length) {
    return;
  }
  for (let i = 0; i < treedata.length; i++) {
    let node = treedata[i];
    if (node.id === id) {
      treedata.splice(i, 1);
      break;
    }
    if (node.children && node.children?.length > 0) {
      removetreeitem(node.children, id);
    }
  }
  return treedata;
};
console.log(json.stringify(removetreeitem(tree, 2)));

树：批量过滤

/**
 * 批量过滤出树结构满足对应字段条件的节点 (从最顶层过滤，有缺陷)
 * @param {array}  treedata 要查找的源数组
 * @param {functiuon} ruleval   匹配的条件函数
 */
const filtertree = (treedata: itree[], ruleval: (item: itree) => boolean) => {
  var newdata = treedata.filter(ruleval);
  newdata.foreach(
    (item) =>
      item.children && (item.children = filtertree(item.children, ruleval))
  );
  return newdata;
};

console.log(
  json.stringify(
    filtertree(tree, (item: itree) => item.value.indexof("2") > -1)
  )
);

树：查询一个节点

/**
 *根据要查找的key返回这一项 （递归查找,引用查找）
 * @param {array}  treedata 要查找的源数组
 * @param {string} id   唯一标识
 * @param {string} key   要查找的键名
 */
const findtreeitem = (
  treedata: itree[],
  id: number,
  key: keyof itree = "id"
) => {
  for (const item of treedata) {
    if (item[key] === id) return item;
    if (item.children && item.children.length > 0) {
      let forfindret: any = findtreeitem(item.children, id, key);
      if (forfindret) return forfindret;
    }
  }
};

console.log(json.stringify(findtreeitem(tree, 2)));

树：增加一个节点

/**
 * 添加一个节点， (没有考虑节点的关联关系)
 * @param {array}  treedata 数据源
 * @param {number} id  唯一标识
 * @param {itree} newobj  新数据项
 */

const addtreeitem = (treedata: itree[], id: number | null, newobj: itree) => {
  if (!treedata || !treedata.length) {
    return;
  }
  if (id === null) {
    treedata.push(newobj);
    return treedata;
  }
  for (let i = 0; i < treedata.length; i++) {
    let node = treedata[i];
    if (node.id === id) {
      node.children ? node.children.push(newobj) : (node.children = [newobj]);
      break;
    }
    if (node.children && node.children?.length > 0) {
      addtreeitem(node.children, id, newobj);
    }
  }
  return treedata;
};
console.log(
  json.stringify(addtreeitem(tree, 5, { id: 6, pid: 5, value: "item 5-1" }))
);
console.log(
  json.stringify(addtreeitem(tree, 6, { id: 7, pid: 6, value: "item 6-1" }))
);
console.log(
  json.stringify(addtreeitem(tree, null, { id: 8, pid: null, value: "item 3" }))
);

树：批量修改

/**
 * 树：批量修改， (节点映射新字段)
 * @param  treedata 数据源
 * @param  maprule  自定义要映射的规则
 */

const maptree = <t>(
  treedata: itree[],
  maprule: (item: itree) => t
): (t & itree)[] => {
  return treedata.map((item) => ({
    ...item,
    ...maprule(item),
    children:
      item.children && item.children.length
        ? maptree(item.children, maprule)
        : null,
  }));
};

type inewfield = {
  newval: string;
  newfield: string;
};
console.log(
  json.stringify(
    maptree<inewfield>(tree, (item) => ({
      newval: "追加字段",
      newfield: item.value.indexof("1") > -1 ? "特殊标识" : "普通标识",
    }))
  )
);

树：查找树的最大层级

/**
 * 查找树的最大层级
 * @param  treedata 数据源
 * @returns {number}
 */
const findtreedepth = (treedata: itree[] | undefined): number => {
  if (!treedata || treedata.length === 0) {
    return 0;
  }
  let maxdepth = 0;
  for (let node of treedata) {
    const depth = findtreedepth(node.children);
    maxdepth = math.max(maxdepth, depth);
  }
  // 返回子节点中最大深度加上当前节点的深度
  return maxdepth + 1;
};
console.log(json.stringify(findtreedepth(tree)));

总结：上述代码中

• 方便同学理解，所有的方法都是围绕上面定义的【数据示例】进行代码编写。
• 关于js 树的操作，写的都是最简单易懂的基础代码，特殊场景或特殊字段，需要自己在进行特殊改造。

有疑问的同学可以私信我、对帮助到同学欢迎大家收藏评论。