search

zptime / blog

个人博客
0 stars 0 forks source link

树结构模拟数据 #1

Open zptime opened 3 years ago

zptime commented 3 years ago 
// 树结构模拟数据
export 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": "扬州" }
    ]
  }
]

实际使用函数：

(1)树数据转化：模拟数据转为封装组件需要的数据 数据源字段为id,pid,label,children;而ant tree需要的字段为key，title和children，当然你也可以改变组件replaceFields的赋值，替换treeNode的字段

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

(2)选中节点禁用

export 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;
};

(3)选中节点过滤：源数据处理，不展示选中节点 过滤条件是：当前节点且其后代节点都没有符合条件的数据

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, tree)
  );
};

(4)选中节点过滤：目标数据处理，仅仅展示选中节点 过滤条件是：当前节点或者是其后代节点有符合条件的数据

export const filterTargetTreeFn = (tree = [], targetKeys = []) => {
  return R.filter((o) => {
    // 存在子节点时，递归处理
    if (o.children?.length) {
      o.children = filterTargetTreeFn(o.children, targetKeys);
    }
    // 当前节点或者是其后代节点有符合条件的数据
    return (
      R.indexOf(o.id, targetKeys) > -1 || (o.children && o.children.length)
    );
  }, tree);
};
zptime commented 3 years ago
  1. 树的遍历 
    
/**
*  深度优先遍历
*  @params {Array} tree 树数据
*  @params {Array} func 操作函数
*/
export const dfsTransFn = (tree, func) => {
tree.forEach((node) => {
func(node);
// 如果子树存在，递归调用
// ?. 可选链，等价于node.children && node.children.length
if (node.children?.length) {
  dfsTransFn(node.children, func);
}
});
return tree;
};

// 深度优先循环实现，与广度优先类似，要维护一个队列 export const dfsTreeFn = (tree, func) => { let node, list = [...tree]; // shift()-取第一个 while ((node = list.shift())) { func(node); // 如果子树存在，递归调用 // 子节点追加到队列最前面unshift node.children && list.unshift(...node.children); } };

/**

zptime commented 3 years ago
  1. 树结构转列表结构 
    
// 深度优先递归
export const dfsTreeToListFn = (tree = [], result = []) => {
tree.forEach((node) => {
result.push(node);
// 打印节点信息
// console.log(`${node.id}...${node.label}`);
node.children && dfsTreeToListFn(node.children, result);
});
return result;
};

// 广度优先递归 export 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; };

zptime commented 3 years ago
  1. 列表结构转为树结构

reduce官网介绍：https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce

arr.reduce(callback(accumulator, currentValue[, index[, array]])[, initialValue])

export const listToTreeFn = (list) => {
  // 建立了id=>node的映射
  let obj = list.reduce(
    // (map, node) => ((map[node.id] = node), (node.children = []), map),
    // map-累加器，node-当前值
    (map, node) => {
      map[node.id] = node;
      node.children = [];
      return 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;
  });
};
zptime commented 3 years ago
  1. 查找节点：判断某个节点是否存在 
    export 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 null;
};
zptime commented 3 years ago
  1. 查找节点路径（回溯法） 查找路径要使用先序遍历，维护一个队列存储路径上每个节点的id，假设节点就在当前分支，如果当前分支查不到，则回溯。 
    export 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 [];
};
// treeFindPathFn(tree, (node) => node.id === "1001");
zptime commented 3 years ago
  1. 树结构数据节点过滤（去掉选中节点，仅保留非选中节点）

（1）硬写的过滤三级树结构数据

export const filterSourceTreeFn = (tree = [], targetKeys = []) => {
  let result = [];
  R.forEach((o) => {
    // 1. 判断当前节点是否含符合条件的数据：是-继续；否-过滤
    if (targetKeys.indexOf(o.id) < 0) {
      // 2. 判断是否含有子节点：是-继续；否-直接返回
      if (o.children?.length) {
        // 3. 存在子节点数据时，进行递归，重复之前的操作
        let childResult = [];
        R.forEach((m) => {
          if (targetKeys.indexOf(m.id) < 0) {
            if (m.children?.length) {
              m.children = R.filter(
                (n) => targetKeys.indexOf(n.id) < 0,
                m.children
              );
              if (m.children.length) childResult.push(m);
            } else {
              childResult.push(m);
            }
          }
        }, o.children);
        // 4. 子节点递归后，进行过滤处理
        o.children = R.filter((r) => targetKeys.indexOf(r.id) < 0, childResult);
        // 5. 存在子节点，且子节点也有符合条件的子节点，直接返回
        if (o.children.length) result.push(o);
      } else {
        result.push(o);
      }
    }
  }, tree);
  return result;
};

（2）递归写法

父节点满足条件，且存在满足条件的子节点时返回

export 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;
};

（3）最终版

当父节点满足条件，但是没有子节点时，也返回了

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, tree)
  );
};
zptime commented 3 years ago
  1. 树结构数据保留（仅保留选中节点）

（1）初始版

export const 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;
    // 合并后判断条件
    // return (
    //   R.indexOf(o.id, targetKeys) > -1 || (o.children && o.children.length)
    // );
  }, tree);
};

（2）最终版

export const filterTargetTreeFn = (tree = [], targetKeys = []) => {
  return R.filter((o) => {
    // 存在子节点时，递归处理
    if (o.children?.length) {
      o.children = filterTargetTreeFn(o.children, targetKeys);
    }
    // 当前节点或者是其后代节点有符合条件的数据
    return (
      R.indexOf(o.id, targetKeys) > -1 || (o.children && o.children.length)
    );
  }, tree);
};