关于父子关系数据处理问题

null
  • 57

只要有子集address字段内容前面加一个符号,如果子集又有子集,就加2个符号*,以此类推,请问怎样实现呢

const array = [
 {id:1,pid:0,address:'安徽'},
 {id:3,pid:1,address:'合肥'},
 {id:12,pid:1,address:'安庆'},
 {id:4,pid:3,address:'庐阳区'},
 {id:5,pid:4,address:'大扬镇'},
 {id:2,pid:0,address:'江苏'},
 {id:6,pid:2,address:'南京'},
 {id:7,pid:6,address:'玄武区'},
 {id:8,pid:7,address:'梅园新村街道'},
]
//希望得到结果
const res = [
 {id:1,pid:0,address:'安徽'},
 {id:3,pid:1,address:'*合肥'},
 {id:12,pid:1,address:'*安庆'},
 {id:4,pid:3,address:'**庐阳区'},
 {id:5,pid:4,address:'***大扬镇'},
 {id:2,pid:0,address:'江苏'},
 {id:6,pid:2,address:'*南京'},
 {id:7,pid:6,address:'**玄武区'},
 {id:8,pid:7,address:'****梅园新村街道'},
]
回复
阅读 438
2 个回答
✓ 已被采纳

不就是计算节点所在的层数吗。只需要不断的查 parent 查到 0 为止,看查了多少次就得到这个层次数了。

// 为了快速查找,做个 map
const map = Object.fromEntries(
    array.map(it => [it.id, it])
);

function calculateLevel(id) {
    let count = 0;
    while (id > 0) {
        ({ pid: id } = map[id]);
        count++;
    }
    return count;
}

const result = array.map(({ id, pid, address }) => ({
    id,
    pid,
    address: `${Array(calculateLevel(id)).join("*")}${address}`
}));

console.log(result);

最后那个 梅园新村街道 前面应该是 3 个 *

先贴两种 O(n) 的算法

// 方法一:DFS
// 自顶向下建树,即记录每个结点的子集,然后 DFS 遍历一次即可,时间复杂度 O(n)
const tree = array.reduce((t, c) => ((t[c.pid] ??= []).push(c), t), {})
const dfs = (id, d) => tree[id]?.forEach(c => (c.address = '*'.repeat(d) + c.address, dfs(c.id, d + 1)))
dfs(0, 0)
console.log(array)

// 方法二:记忆化搜索
// 先记录每个结点的上级,然后遍历一次数组计算结点深度
// 计算公式:结点深度 = 父结点深度 + 1(根结点深度为 -1)
// 若父结点深度还没计算,则递归计算父结点深度
// 计算出结点深度后,存储起来,以供给子结点计算使用,时间复杂度降低到 O(n)
const nodes = array.reduce((ns, { id, pid }) => (ns[id] = { pid }, ns), {})
nodes[0] = { d: -1 }
const d = id => nodes[id].d ??= d(nodes[id].pid) + 1
array.forEach(n => n.address = '*'.repeat(d(n.id)) + n.address)
console.log(array)
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏