将人的平面数组转换为 JavaScript 中的嵌套谱系树

Question

我正在尝试将一个简单的人员列表转换为一个结构化的祖先树。

人员的源数组如下所示：

const list = [
    {
        id: 1,
        name: 'John',
        akin: true,
        motherId: undefined,
        fatherId: undefined,
        partnerIds: [2]
    },
    {
        id: 2,
        name: 'Maria',
        akin: false,
        motherId: undefined,
        fatherId: undefined,
        partnerIds: [1]
    },
    {
        id: 3,
        name: 'Steven',
        akin: true,
        fatherId: 1,
        motherId: 2,
        partnerIds: [4, 5]
    },
    {
        id: 4,
        name: 'Stella',
        akin: false,
        motherId: undefined,
        fatherId: undefined,
        partnerIds: [3]
    },
    {
        id: 5,
        name: 'Laura',
        akin: false,
        motherId: undefined,
        fatherId: undefined,
        partnerIds: [3]
    },
    {
        id: 5,
        name: 'Solomon',
        akin: true,
        motherId: 4,
        fatherId: 3,
        partnerIds: []
    },
    {
        id: 6,
        name: 'Henry',
        akin: true,
        fatherId: 3,
        motherId: 5,
        partnerIds: []
    }
]

它可以包含n代人，他们的直系祖先由他们各自的fatherId和motherId定义。未知 parents（最古老的已知祖先，或仅通过伙伴关系相关）只是未定义。伙伴关系由一组 partnerIds 表示。

预期输出应如下所示：

const pedigree = [
    {
        id: 1,
        name: 'John',
        partnerships: [
            {
                partner: {
                    id: 2,
                    name: 'Maria',
                },
                children: [
                    {
                        id: 3,
                        name: 'Steven',
                        partnerships: [
                            {
                                partner: {
                                    id: 4,
                                    name: 'Stella',
                                },
                                children: [
                                    {
                                        id: 5,
                                        name: 'Solomon'
                                    }
                                ]
                            },
                            {
                                partner: {
                                    id: 5,
                                    name: 'Laura',
                                },
                                children: [
                                    {
                                        id: 6,
                                        name: 'Henry',
                                    }
                                ]
                            }
                        ]
                    }
                ]
            }
        ]
    }
]

从视觉上看，结果如下所示： Visual pedigree 所需的输出格式不是为了存储，而是为了更容易可视化和处理以供以后渲染。

我试着遍历平面列表，创建一个哈希表来引用单身人士，然后找到合作伙伴和共同点 children。我的问题是虽然我的方法只适用于两代或一层嵌套，但我需要它适合 n 代。我想我需要一些递归函数或以某种方式从祖先的底部开始循环的方法，但我想不出一个聪明的方法。

我很乐意提供任何建议或提示！

编辑： 这是我试过的：

const createPedigree = (dataset) => {
    const hashTable = Object.create(null)
    dataset.forEach(
        (person) => (hashTable[person.id] = { ...person, partnerships: [] })
    )
    const dataTree = []
    dataset.forEach((person) => {
        if (person.akin) {
            if (person.partnerIds.length) {
                person.partnerIds.forEach((partnerId) => {
                    hashTable[person.id].partnerships.push({
                        partner: { ...dataset.find((p) => p.id === partnerId) },
                        children: []
                    })
                })
            }
        }
        dataTree.push(hashTable[person.id])
    })
    dataset.forEach((child) => {
        // fill partnerships with children
        if (child.fatherId && child.motherId) {
            if (
                hashTable[child.fatherId].akin &&
                hashTable[child.fatherId].partnerships.length
            ) {
                let mother = hashTable[child.fatherId].partnerships.find(
                    (partnership) => {
                        return partnership.partner.id === child.motherId
                    }
                )
                mother.children.push(child)
            } else if (hashTable[child.motherId].akin) {
                let father = hashTable[child.motherId].partnerships.find(
                    (partnership) => {
                        return partnership.partner.id === child.fatherId
                    }
                )
                father.children.push(child)
                
            }
        }
    })
    return dataTree
}

Answer 1

你假设通用解决方案将涉及一些递归调用（或扩展候选队列直到队列为空）是正确的。

输出结构级别在以下之间交替：

有伙伴关系的人
包含合伙人和 children 的合伙企业（每个 child 又是 1。）

为了让事情更简单，我们可以用 2 个单独的函数对上面的 2 个步骤进行建模。我选择了名称 expandPerson 和 expandPartnership.

const expandPerson = (personId, dataset) => {
    // we get the person from the dataset by their id
    const personData = dataset.find(p => p.id == personId)
    // we clone only the data that we want in the output
    const person = { id: personData.id, name: personData.name }

    // all partnerIds of this person need to become their parnerships
    // so we just map them to an "expanded partnership" (step 2.)
    person.partnerships = personData.partnerIds
       .map(partnerId => expandPartnership(partnerId, person.id, dataset))

    // we return the "expanded" person
    return person
}

const expandPartnership = (partner1Id, partner2Id, dataset) => {
    // we get the partner from the dataset by their id
    const partnerData = dataset.find(p => p.id == partner1Id)
    // we clone only the data that we want in the output
    const partner = { id: partnerData.id, name: partnerData.name }

    // all people in the dataset, whose parents are partner1Id
    // and pertner2Id are the children
    const children = dataset
      .filter(p => p.motherId == partner1Id && p.fatherId == partner2Id
        || p.motherId == partner2Id && p.fatherId == partner1Id)
      // we map each child as an "expanded person" again (back to step 1.)
      .map(p => expandPerson(p.id, dataset))

    // we return the "expanded" partnership
    return { partner, children }
}

在代码中，您只需调用 const pedigree = expandPerson(1, list)

如果根不总是id: 1先找到根id

const rootId = list.find(p => p.akin && !p.fatherId && !p.motherId).id
const pedigree = expandPerson(rootId, list)

注意：您在提供的输入中有重复的 id (id: 5)。你必须解决这个问题。

将人的平面数组转换为 JavaScript 中的嵌套谱系树

Convert flat array of persons into nested pedigree tree in JavaScript

javascript

arrays

tree

recursion

hierarchy