从元组列表中查找树的根

Question

我在编写一个函数时遇到问题，该函数查找 python 中表示为元组列表的树的根。

树：

[(39, 38), (80, 70), (39, 42), (80, 91), (37, 22), (37, 39), (42, 45), (48, 37), (91, 85), (48, 60), (60, 80), (60, 50)]

我研究了如何为此使用类，但不确定是否有任何聪明的方法可以做到这一点。

Answer 1

只要找到不在任何元组结尾的元组开头:

lst = [(39, 38), (80, 70), (39, 42), (80, 91), (37, 22), (37, 39), (42, 45), (48, 37), (91, 85), (48, 60), (60, 80), (60, 50)]

rt = set([t[0] for t in lst if not t[0] in [t[1] for t in lst]])

print(rt)  # nothing links to 48 so it must be the root

输出

{48}

如果需要，您可以将 t[1] 循环分配给一个变量：

lst1 = [t[1] for t in lst]  # all end nodes
rt = set([t[0] for t in lst if not t[0] in lst1])

从元组列表中查找树的根

Finding Root of Tree from List of Tuples

python

tree

binary-search-tree