找到二叉树的根值？

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

接下来,在每个元素上运行"find parent with path compression":

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更快地引用.