python - 树搜索-给定树中的两个节点，检查它们是否已连接-python

给定一个搜索树，例如

"1"
 └ "2"
    ├ "2.1"
    ┊   └ "3"
    ┊
    └ "2.2"
        └ "2.2.1"
             └ "3"

以及属于该树的两个节点a和b，例如“ 2.1”和“ 3”。我们如何检查a和b是否与父子（或子父母）相关/连接？

对于第一个示例，应产生True。这里还有一些：

a="3"      b="1"    -> False
a="3"      b="2"    -> False
a="2.2.1"  b="2.2"  -> True
a="2.2.1"  b="3"    -> True

我当前正在使用anytree库，正在使用该库来实现此解决方案。上图是结构上的简化。下面概述了我目前尝试实现的内容：https://pastebin.com/Mjk7gyqH

如果可以使用纯python或anytree给出答案，那将是很棒的，但是任何答案总比没有好。

最佳答案

您可以使用简单的递归：

tree = {'name': '1', 'children': [{'name': '2', 'children': [{'name': '2.1', 'children': [{'name': '3'}]}, {'name': '2.2', 'children': [{'name': '2.2.1', 'children': [{'name': '3'}]}]}]}]}
def in_tree(d, node):
   return d['name'] == node or any(in_tree(i, node) for i in d.get('children', []))

def lookup(tree, a, b, flag=False):
   if tree['name'] == b and flag:
     return True
   return any(lookup(j, a, b, tree['name'] == a) for j in tree.get('children', []))

test = [['3', '1'], ['3', '2'], ['2.2.1', '2.2'], ['2.2.1', '3'], ['60', '70']]
for a, b in test:
   if not in_tree(tree, a) or not in_tree(tree, b):
      raise AttributeError('Node(s) missing in tree')
   print(any([lookup(tree, a, b), lookup(tree, b, a)]))

输出：

False
False
True
True
Traceback (most recent call last):
  File "<stdin>", line 3, in <module>
AttributeError: Node(s) missing in tree