获取每个节点的最大树深度
Get maximum tree depth for each node
假设我们有一棵树，每个节点可以有多个children，而children可以有多个children等等
以这棵树为例：
- Node 1
- Node 1.1
- Node 1.2
- Node 1.2.1
- Node 1.2.1.1
- Node 1.2.1.2
- Node 1.2.2
- Node 1.3
- Node 1.3.1
节点 1 的深度 = 0（根）
节点 1.1、1.2、1.3 的深度为 1，依此类推
对于每个节点我想计算它可以达到的最大深度。
例如，节点 1 最大值。深度为 3（树与节点 1.2.1.1 一样深）。而节点 1.3 最大深度 = 1（子树达到节点 1.3.1 的深度）
现在我可以做的是创建一个函数，它接受一个子树并计算到最深的节点，returns 深度值。但这需要为每个节点调用该函数，这对我来说似乎效率很低。
我想一次性创建树并计算最大深度。
我保持代码非常简单，因为我的函数包含许多其他操作（例如生成新的 children，因为我从头开始构建树，但我省略了这些部分为简单起见）。
但基本上，我是这样遍历树的：
def create_behavior_tree(depth, max_depth, behavior_tree)
for child in behavior_tree.children:
if depth > max_depth:
max_depth = depth
if len(child) > 0: # Expanding node
max_depth = create_behavior_tree(depth + 1, max_depth, child)
child.max_depth = max_depth # problem: stores the values in "reverse"
else: # Single node without children
child.max_depth = depth
create_behavior_tree(1, 0, Tree)
然而，当我这样做时，我无法到达外部节点的最新 max_depth 值，它只能在最里面的节点内到达（因为这是递归）。
所以这将计算：节点 1 最大深度 = 0，节点 1.2 最大深度 = 1，节点 1.2.1 最大深度 = 2 等。它实际上是相反的。
所以，也许我需要在这里使用全局变量？
编辑——我的函数的更详细版本
def create_behavior_tree(depth, behavior_tree, children, max_tree_depth, node_count):
if depth <= max_tree_depth:
for child in children:
# add behavior node
if type(child) == Behaviour:
behavior_tree.add_children([child])
node_count += 1 # counting total nodes in tree
# add composite node
if type(child) == Composite:
# replace by behavior node (reached max tree depth)
if depth == max_tree_depth:
node = create_behaviour_node()
behavior_tree.add_children([node])
node_count += 1
else:
behavior_tree.add_children([child])
node_count += 1
# further expand behavior tree
children = create_random_children(size=3)
_, node_count = create_behavior_tree(depth + 1, node, children, max_tree_depth, node_count)
return behavior_tree, node_count
random_children = create_random_children(size=3) # Create 3 random children
root = py_trees.composites.Selector("Selector")
create_behavior_tree(1, root, random_children, 5, 0)
利用递归的self-similarity，这与任何其他one-pass O(n) depth/tree 高度算法相同，除了设置最大深度属性 为每个节点备份调用堆栈：
def set_all_depths(tree):
if not tree:
return 0
tree.max_depth = (
max(map(set_all_depths, tree.children))
if tree.children else 0
)
return tree.max_depth + 1
def print_tree(tree, depth=0):
if tree:
print(" " * depth +
f"{tree.val} [max_depth: {tree.max_depth}]")
for child in tree.children:
print_tree(child, depth + 1)
class TreeNode:
def __init__(self, val, children=None, max_depth=None):
self.val = val
self.children = children or []
self.max_depth = max_depth
if __name__ == "__main__":
tree = TreeNode(
"1",
[
TreeNode("1.1"),
TreeNode(
"1.2",
[
TreeNode(
"1.2.1",
[
TreeNode("1.2.1.1"),
TreeNode("1.2.1.2"),
],
),
TreeNode("1.2.2"),
],
),
TreeNode(
"1.3",
[
TreeNode("1.3.1"),
],
),
],
)
set_all_depths(tree)
print_tree(tree)
输出：
1 [max_depth: 3]
1.1 [max_depth: 0]
1.2 [max_depth: 2]
1.2.1 [max_depth: 1]
1.2.1.1 [max_depth: 0]
1.2.1.2 [max_depth: 0]
1.2.2 [max_depth: 0]
1.3 [max_depth: 1]
1.3.1 [max_depth: 0]
根据follow-up的评论，如果你想一次制作树并分配最大深度，一种方法是从children中挑选出最大深度并分配它到备份调用堆栈途中的每个节点。
这是一个 library-agnostic 概念证明，因为我没有你在新示例中的 类：
import random
from random import randint
def make_random_tree(max_depth=4):
if max_depth <= 0:
return TreeNode(Id.make(), max_depth=0)
node = TreeNode(Id.make())
node.children = [
make_random_tree(max_depth - 1) for _ in range(randint(0, 4))
]
node.max_depth = 1 + (
max([x.max_depth for x in node.children])
if node.children else 0
)
return node
def print_tree(tree, depth=0):
if tree:
print(" " * depth +
f"{tree.val} [max_depth: {tree.max_depth}]")
for child in tree.children:
print_tree(child, depth + 1)
class TreeNode:
def __init__(self, val, children=None, max_depth=None):
self.val = val
self.children = children or []
self.max_depth = max_depth
class Id:
identifier = 0
def make():
Id.identifier += 1
return Id.identifier
if __name__ == "__main__":
random.seed(1)
tree = make_random_tree()
print_tree(tree)
输出：
1 [max_depth: 4]
2 [max_depth: 3]
3 [max_depth: 1]
4 [max_depth: 2]
5 [max_depth: 1]
6 [max_depth: 1]
7 [max_depth: 0]
8 [max_depth: 0]
9 [max_depth: 0]
10 [max_depth: 2]
11 [max_depth: 1]
12 [max_depth: 0]
13 [max_depth: 0]
14 [max_depth: 0]
15 [max_depth: 1]
16 [max_depth: 0]
17 [max_depth: 0]
18 [max_depth: 0]
19 [max_depth: 1]
20 [max_depth: 0]
21 [max_depth: 1]
也就是说，在第二次传递中分配深度仍然是 O(n)，因此在一次传递中完成所有操作可能是不成熟的优化，除非您有真正大的或 performance-critical 代码。
您可以使用广度优先搜索获取所有节点的深度以及从根到每个节点的路径，然后迭代所有节点的结果，产生最大深度：
from collections import deque
tree = {'1': {'1': None, '2': {'1': {'1': None, '2': None}, '2': None}, '3': {'1': None}}}
def bfs(t):
d = deque([(a, [a], 0, b) for a, b in t.items()])
while d:
yield (n:=d.popleft())[:-1]
if n[-1] is not None:
d.extend([(a, n[1]+[a], n[2]+1, b) for a, b in n[-1].items()])
nodes = list(bfs(tree))
r = {'.'.join(b):max(y for _, x, y in nodes if a in x) - c for a, b, c in nodes}
输出：
{'1': 3, '1.1': 2, '1.2': 2, '1.3': 1, '1.2.1': 1, '1.2.2': 1, '1.3.1': 1, '1.2.1.1': 0, '1.2.1.2': 0}
如果有人还想添加有关节点当前深度以及节点包含多少个节点（计数节点）的信息，我扩展了@ggorlen 的回答
def create_depth_map(self, tree, depth, node_count):
results = list(zip(*map(lambda x: self.create_depth_map(*x), [[child, depth + 1, node_count] for child in tree.children])))
tree.max_depth = (max(results[0]) if tree.children else 0)
tree.current_depth = depth
node_count += (sum(results[1]) if tree.children else 0)
tree.node_count = node_count
return tree.max_depth + 1, node_count
所以它看起来像：
Selector [current_depth: 0] [max_depth: 5] [node_count: 17]
Action [current_depth: 1] [max_depth: 0] [node_count: 1]
Inverter [current_depth: 1] [max_depth: 3] [node_count: 7]
Sequence [current_depth: 2] [max_depth: 2] [node_count: 6]
Action [current_depth: 3] [max_depth: 0] [node_count: 1]
Sequence [current_depth: 3] [max_depth: 1] [node_count: 4]
Action [current_depth: 4] [max_depth: 0] [node_count: 1]
Condition [current_depth: 4] [max_depth: 0] [node_count: 1]
Condition [current_depth: 4] [max_depth: 0] [node_count: 1]
Inverter [current_depth: 1] [max_depth: 4] [node_count: 8]
Sequence [current_depth: 2] [max_depth: 3] [node_count: 7]
Sequence [current_depth: 3] [max_depth: 2] [node_count: 5]
Parallel [current_depth: 4] [max_depth: 1] [node_count: 3]
Action [current_depth: 5] [max_depth: 0] [node_count: 1]
Condition [current_depth: 5] [max_depth: 0] [node_count: 1]
Action [current_depth: 4] [max_depth: 0] [node_count: 1]
Action [current_depth: 3] [max_depth: 0] [node_count: 1]
非常感谢 ggorlen 这让我更进一步！
假设我们有一棵树，每个节点可以有多个children，而children可以有多个children等等
以这棵树为例：
- Node 1
- Node 1.1
- Node 1.2
- Node 1.2.1
- Node 1.2.1.1
- Node 1.2.1.2
- Node 1.2.2
- Node 1.3
- Node 1.3.1
节点 1 的深度 = 0（根）
节点 1.1、1.2、1.3 的深度为 1，依此类推
对于每个节点我想计算它可以达到的最大深度。 例如，节点 1 最大值。深度为 3（树与节点 1.2.1.1 一样深）。而节点 1.3 最大深度 = 1（子树达到节点 1.3.1 的深度）
现在我可以做的是创建一个函数，它接受一个子树并计算到最深的节点，returns 深度值。但这需要为每个节点调用该函数，这对我来说似乎效率很低。
我想一次性创建树并计算最大深度。
我保持代码非常简单，因为我的函数包含许多其他操作（例如生成新的 children，因为我从头开始构建树，但我省略了这些部分为简单起见）。 但基本上，我是这样遍历树的：
def create_behavior_tree(depth, max_depth, behavior_tree)
for child in behavior_tree.children:
if depth > max_depth:
max_depth = depth
if len(child) > 0: # Expanding node
max_depth = create_behavior_tree(depth + 1, max_depth, child)
child.max_depth = max_depth # problem: stores the values in "reverse"
else: # Single node without children
child.max_depth = depth
create_behavior_tree(1, 0, Tree)
然而，当我这样做时，我无法到达外部节点的最新 max_depth 值，它只能在最里面的节点内到达（因为这是递归）。 所以这将计算：节点 1 最大深度 = 0，节点 1.2 最大深度 = 1，节点 1.2.1 最大深度 = 2 等。它实际上是相反的。
所以，也许我需要在这里使用全局变量？
编辑——我的函数的更详细版本
def create_behavior_tree(depth, behavior_tree, children, max_tree_depth, node_count):
if depth <= max_tree_depth:
for child in children:
# add behavior node
if type(child) == Behaviour:
behavior_tree.add_children([child])
node_count += 1 # counting total nodes in tree
# add composite node
if type(child) == Composite:
# replace by behavior node (reached max tree depth)
if depth == max_tree_depth:
node = create_behaviour_node()
behavior_tree.add_children([node])
node_count += 1
else:
behavior_tree.add_children([child])
node_count += 1
# further expand behavior tree
children = create_random_children(size=3)
_, node_count = create_behavior_tree(depth + 1, node, children, max_tree_depth, node_count)
return behavior_tree, node_count
random_children = create_random_children(size=3) # Create 3 random children
root = py_trees.composites.Selector("Selector")
create_behavior_tree(1, root, random_children, 5, 0)
利用递归的self-similarity，这与任何其他one-pass O(n) depth/tree 高度算法相同，除了设置最大深度属性 为每个节点备份调用堆栈：
def set_all_depths(tree):
if not tree:
return 0
tree.max_depth = (
max(map(set_all_depths, tree.children))
if tree.children else 0
)
return tree.max_depth + 1
def print_tree(tree, depth=0):
if tree:
print(" " * depth +
f"{tree.val} [max_depth: {tree.max_depth}]")
for child in tree.children:
print_tree(child, depth + 1)
class TreeNode:
def __init__(self, val, children=None, max_depth=None):
self.val = val
self.children = children or []
self.max_depth = max_depth
if __name__ == "__main__":
tree = TreeNode(
"1",
[
TreeNode("1.1"),
TreeNode(
"1.2",
[
TreeNode(
"1.2.1",
[
TreeNode("1.2.1.1"),
TreeNode("1.2.1.2"),
],
),
TreeNode("1.2.2"),
],
),
TreeNode(
"1.3",
[
TreeNode("1.3.1"),
],
),
],
)
set_all_depths(tree)
print_tree(tree)
输出：
1 [max_depth: 3]
1.1 [max_depth: 0]
1.2 [max_depth: 2]
1.2.1 [max_depth: 1]
1.2.1.1 [max_depth: 0]
1.2.1.2 [max_depth: 0]
1.2.2 [max_depth: 0]
1.3 [max_depth: 1]
1.3.1 [max_depth: 0]
根据follow-up的评论，如果你想一次制作树并分配最大深度，一种方法是从children中挑选出最大深度并分配它到备份调用堆栈途中的每个节点。
这是一个 library-agnostic 概念证明，因为我没有你在新示例中的 类：
import random
from random import randint
def make_random_tree(max_depth=4):
if max_depth <= 0:
return TreeNode(Id.make(), max_depth=0)
node = TreeNode(Id.make())
node.children = [
make_random_tree(max_depth - 1) for _ in range(randint(0, 4))
]
node.max_depth = 1 + (
max([x.max_depth for x in node.children])
if node.children else 0
)
return node
def print_tree(tree, depth=0):
if tree:
print(" " * depth +
f"{tree.val} [max_depth: {tree.max_depth}]")
for child in tree.children:
print_tree(child, depth + 1)
class TreeNode:
def __init__(self, val, children=None, max_depth=None):
self.val = val
self.children = children or []
self.max_depth = max_depth
class Id:
identifier = 0
def make():
Id.identifier += 1
return Id.identifier
if __name__ == "__main__":
random.seed(1)
tree = make_random_tree()
print_tree(tree)
输出：
1 [max_depth: 4]
2 [max_depth: 3]
3 [max_depth: 1]
4 [max_depth: 2]
5 [max_depth: 1]
6 [max_depth: 1]
7 [max_depth: 0]
8 [max_depth: 0]
9 [max_depth: 0]
10 [max_depth: 2]
11 [max_depth: 1]
12 [max_depth: 0]
13 [max_depth: 0]
14 [max_depth: 0]
15 [max_depth: 1]
16 [max_depth: 0]
17 [max_depth: 0]
18 [max_depth: 0]
19 [max_depth: 1]
20 [max_depth: 0]
21 [max_depth: 1]
也就是说，在第二次传递中分配深度仍然是 O(n)，因此在一次传递中完成所有操作可能是不成熟的优化，除非您有真正大的或 performance-critical 代码。
您可以使用广度优先搜索获取所有节点的深度以及从根到每个节点的路径，然后迭代所有节点的结果，产生最大深度：
from collections import deque
tree = {'1': {'1': None, '2': {'1': {'1': None, '2': None}, '2': None}, '3': {'1': None}}}
def bfs(t):
d = deque([(a, [a], 0, b) for a, b in t.items()])
while d:
yield (n:=d.popleft())[:-1]
if n[-1] is not None:
d.extend([(a, n[1]+[a], n[2]+1, b) for a, b in n[-1].items()])
nodes = list(bfs(tree))
r = {'.'.join(b):max(y for _, x, y in nodes if a in x) - c for a, b, c in nodes}
输出：
{'1': 3, '1.1': 2, '1.2': 2, '1.3': 1, '1.2.1': 1, '1.2.2': 1, '1.3.1': 1, '1.2.1.1': 0, '1.2.1.2': 0}
如果有人还想添加有关节点当前深度以及节点包含多少个节点（计数节点）的信息，我扩展了@ggorlen 的回答
def create_depth_map(self, tree, depth, node_count):
results = list(zip(*map(lambda x: self.create_depth_map(*x), [[child, depth + 1, node_count] for child in tree.children])))
tree.max_depth = (max(results[0]) if tree.children else 0)
tree.current_depth = depth
node_count += (sum(results[1]) if tree.children else 0)
tree.node_count = node_count
return tree.max_depth + 1, node_count
所以它看起来像：
Selector [current_depth: 0] [max_depth: 5] [node_count: 17]
Action [current_depth: 1] [max_depth: 0] [node_count: 1]
Inverter [current_depth: 1] [max_depth: 3] [node_count: 7]
Sequence [current_depth: 2] [max_depth: 2] [node_count: 6]
Action [current_depth: 3] [max_depth: 0] [node_count: 1]
Sequence [current_depth: 3] [max_depth: 1] [node_count: 4]
Action [current_depth: 4] [max_depth: 0] [node_count: 1]
Condition [current_depth: 4] [max_depth: 0] [node_count: 1]
Condition [current_depth: 4] [max_depth: 0] [node_count: 1]
Inverter [current_depth: 1] [max_depth: 4] [node_count: 8]
Sequence [current_depth: 2] [max_depth: 3] [node_count: 7]
Sequence [current_depth: 3] [max_depth: 2] [node_count: 5]
Parallel [current_depth: 4] [max_depth: 1] [node_count: 3]
Action [current_depth: 5] [max_depth: 0] [node_count: 1]
Condition [current_depth: 5] [max_depth: 0] [node_count: 1]
Action [current_depth: 4] [max_depth: 0] [node_count: 1]
Action [current_depth: 3] [max_depth: 0] [node_count: 1]
非常感谢 ggorlen 这让我更进一步！