寻找二叉树的根节点值？

Question

我有一个存储值关系的数组，它形成了多棵树，如下图所示：


因此，在这种情况下，我的数组是（根节点，与之连接的节点）：

(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)

我应该研究哪个算法？

- Gabriel

---

“主”根是唯一从未出现在等式右侧的数值。 - Oliver Charlesworth

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

etc.

Result:

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的查找更加迅速。

- Stuart Golodetz

---

@David 使用 BFS 将意味着您需要准备一些图形结构，而在这种情况下，这将是过度的。您在这里唯一需要的是具有某种 contains() 的集合。 - soulcheck

简单的方法是使用类似于std::set（在C++中）或您所使用编程语言的等效方式。 - Stuart Golodetz

@stuart，由于我的数组有几棵树，如果按照你说的做法，结果会为空。 - Gabriel

算法基本上是：（1）将您拥有的配对转换为更易处理的表示形式，即子代->父代查找表。 （2）计算每个子代的最终祖先，并将其设置为其新的父代（但使用路径压缩来最小化您所做的工作量）。 （3）将修改后的查找表转换回您实际需要的表示形式。 - Stuart Golodetz

并查集不是重点，我只提到它是因为路径压缩通常用于实现不相交集合森林。 - Stuart Golodetz

Answer 2

假设你有一个表示点的元组列表：

def find_root(ls):
  child, parent, root = [], [], []
  for node in ls:
    parent.append(node[0])
    child.append(node[1])

  for dis in parent: 
    if (!child.count(dis)): 
      root.append(dis)

  if len(root) > 1 : return -1 # failure, the tree is not formed well

  for nodeIndex in xrange(len(ls)):
    ls[nodeIndex] = (root[0], ls[nodeIndex][1])

  return ls

- Noxville