如果两棵树结构相等，BFS 和树数据结构是否足以进行比较？

Question

我正在解决一个问题，我需要比较多个谱系（家谱）以检查它们在结构上是否相同。每个谱系都从一个根（祖先）开始并向下延伸。这些树按孩子的年龄排序，每个节点都有一个性别指示符（I、M、K 分别表示双性人、男性、女性）。

如果满足以下条件，则认为树在结构上相等：

1. 两棵树的根节点具有相同的性别。
2. 每个节点的子节点数量在树之间匹配。
3. 每一级的子级都以相同的方式排序，并且一个根的第 n 个子级在结构上与另一个根的第 n 个子级相同。

这是一个示例，显示两棵树在结构上不相等。

该问题需要时间复杂度为 O(n * m) 的算法，其中 n 是谱系数，m 是最大树中的节点数。我们规定父母不能拥有超过 12 个孩子。我们需要在算法中使用分解。

我考虑过使用 BFS 进行树遍历，因为它逐级处理节点，这非常适合比较有序的子节点。我还将使用树数据结构来表示每个谱系，其中每个节点包含性别和对其子代的引用。

但是，我并不完全确定这种方法是否足以满足问题的要求，特别是考虑到结构不相同时的排序和提前终止的限制。

所以我的问题是：将 BFS 与树数据结构结合使用是否足以在时间复杂度和结构方面比较这些树？在没有公共根的情况下，BFS 如何启动？这是否意味着有一个共同的祖先并且对于这种类型的比较来说是不正确的？

Answer 1

您可以使用深度优先算法，但在深入树中之前检查规则 2（子级数量必须相等）。这方面可以被认为是类似 BFS 的，但相似之处仅此而已。

DFS 遍历将“串联”发生，即您同时在两个谱系中以相同的方式移动。 DFS 遍历适合递归实现，从而还满足使用“分解”的要求：一个节点的问题被拆分为该节点的子节点代表的子问题。

按照建议，数据结构将由具有两个属性的节点组成：性别和子节点列表，其中每个子节点也是这样的节点。

这是 JavaScript 中的实现：

class Person {
    constructor(gender, children=[]) { // Second argument defaults to empty list
        this.gender = gender;
        this.children = children;
    }
}

function areIdentical(lineageA, lineageB) {
    // The root nodes of both trees must have the same gender:
    if (lineageA.gender != lineageB.gender) return false;
    // The number of children at each node matches between the trees
    if (lineageA.children.length != lineageB.children.length) return false;
    for (let i = 0; i < lineageA.children.length; i++) {
        // The nth child of one root is structurally identical to the nth child of the other root
        if (!areIdentical(lineageA.children[i], lineageB.children[i])) return false;
    }
    // All conditions are satisfied
    return true;
}

// Create the lineages as in your example:
const lineageA = new Person("K", [
    new Person("K", [
        new Person("I"),
        new Person("M"),
    ]),
    new Person("M"),
    new Person("K", [
        new Person("K"),
    ]),
]);

const lineageB = new Person("K", [
    new Person("M"),
    new Person("K", [
        new Person("I"),
        new Person("M"),
    ]),
    new Person("K", [
        new Person("K"),
    ]),
]);

const result = areIdentical(lineageA, lineageB);
console.log(result); // false