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

发表时间：2022-06-23 14:39:06 阅读：132

只要有子集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:'****梅园新村街道'},
]

🎖️ 优质答案

不就是计算节点所在的层数吗。只需要不断的查 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)