javascript - 将平面数组的人转换为 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 定义。未知的 parent (最年长的已知祖先，或仅通过伙伴关系相关)只是未定义。伙伴关系由一系列 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所需的输出格式不是为了存储，而是为了更容易可视化和处理以供以后渲染。

我尝试遍历平面列表，创建一个哈希表来引用单例，然后找到伴侣和普通 child 。我的问题是虽然我的方法只适用于两代或一层嵌套，但我需要它适合 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

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

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

1. 有合伙关系的人
2. 包含合作伙伴和 child 的伙伴关系(每个 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)。你必须解决这个问题。