algorithm - 查找二叉树的根值？

Question

我有一个存储值关系的数组，它使几棵树像这样:

所以，在这种情况下，我的数组将是(root，链接到)

(8,3)(8,10)(3,1)(3,6)(6,4)(6,7)(10,14)(14,13)

我想将数组中的所有根值设置为树中的主根(在所有树中):

(8,3)(8,1)(8,6)(8,4)(8,7)(8,10)(8,14)(8,13)

我应该研究什么算法？

Answer 1

1) 列出元组中所有唯一的第一个元素。

2) 删除任何也作为元组第二个元素出现的元素。

3) 您将得到根目录(此处为 8)。用这个值替换所有元组的第一个元素。

---

编辑:

适用于多棵树的更复杂的方法如下。

首先，转换为父查找表:

1 -> 3
3 -> 8
4 -> 6
6 -> 3
7 -> 6
10 -> 8
13 -> 14
14 -> 10

接下来，在每个元素上运行“使用路径压缩查找父元素”:

1)

1 -> 3 -> 8

给予

1 -> 8
3 -> 8
4 -> 6
...

3)

3 -> 8

4)

4 -> 6 -> 3 -> 8

给予

1 -> 8
3 -> 8
4 -> 8
6 -> 8
7 -> 6
...

6)

6 -> 8 (already done)

7)

7 -> 6 -> 8

等等

结果:

1 -> 8
3 -> 8
4 -> 8
6 -> 8
7 -> 8
...

然后将其转换回元组列表:

(8,1)(8,3)(8,4)...

---

具有路径压缩算法的查找父节点与 find_set 一样适用于不相交的集合森林，例如

int find_set(int x) const
{
    Element& element = get_element(x);
    int& parent = element.m_parent;
    if(parent != x)
    {
        parent = find_set(parent);
    }
    return parent;
}

关键是路径压缩可以帮助您避免大量工作。在上面，例如，当您查找 4 时，您存储 6 -> 8，这使得以后查找引用 6 更快.