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

Question

给定一个搜索树，例如

"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

如果答案可以用纯蟒蛇或任何树给出，那就太棒了，但任何答案都比没有好。

Answer 1

您可以使用简单的递归：

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

Answer 2

如果我理解得很好，你"只是"要求没有任何中间节点的直接父子关系。 如果这不是您要找的，那么请提供另一个示例，显示以下代码失败的地方，我可以修复它。

代码使用 anytree 因为这是您建议的库

from anytree import Node, RenderTree
nodes = {} # a dict as a lookup to find nodes by name
def add_node(val, parentval=None):
if parentval is not None:
node = nodes[val] = Node(val, parent=nodes[parentval])
else:
node = nodes[val] = Node(val)
return node
def mk_tree():
top = add_node("1")
add_node("2", "1")
add_node("2.1", "2")
add_node("3", "2.1")
add_node("2.2", "2")
add_node("2.2.1", "2.2")
add_node("3", "2.2.1")
return top
def is_child_or_parent(n1, n2):
return n1.parent == n2 or n2.parent == n1
testpatterns = [
("3", "1", False),
("3", "2", False),
("2.2.1", "2.2", True),
("2.2.1", "3", True),
]
def run_test():
for name1, name2, expected in testpatterns:
node1 = nodes[name1]
node2 = nodes[name2]
rslt = is_child_or_parent(node1, node2)
print(node1, node2, expected, rslt)
assert rslt == expected
tree = mk_tree()
print(RenderTree(tree))
run_test()

Answer 3

>bigtree是一个Python树和图形实现，它与Python列表，字典和pandas DataFrame集成。

对于此方案，有一个内置的find_names和find_children方法可以为您执行此操作。这个想法是，我们可以使用find_name来查找父节点(或多个父节点(，并使用find_children来检查子节点是否与父节点相关。

import numpy as np
from bigtree import list_to_tree, print_tree, find_names, find_children
# Construct tree
path_list = ["1/2/2.1/3", "1/2/2.2/2.2.1/3"]
root = list_to_tree(path_list)
# Validate tree structure
print_tree(root)
1
└── 2
├── 2.1
│   └── 3
└── 2.2
└── 2.2.1
└── 3
# Function to compare
def is_related(a, b):
# Check if a is child of b
if np.any([find_children(node, a) for node in find_names(root, b)]):
return True
# Check if b is child of a
if np.any([find_children(node, b) for node in find_names(root, a)]):
return True
return False
is_related("3", "1")  # False
is_related("3", "2")  # False
is_related("2.2.1", "2.2")  # True
is_related("2.2.1", "3")  # True

来源/免责声明：我是大树;)的创造者