假設我們有一棵樹，每個節點可以有多個子節點，而子節點可以有更多子節點等等。
以這棵樹為例：
- 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 的深度）
現在我可以做的是創建一個函式，它接受一個子樹并計數到最深的節點，并回傳深度值。但這需要為每個節點呼叫該函式，這在我看來效率很低。
我想一次性創建樹并計算最大深度。
我保持代碼非常簡單，因為我的函式還包含許多其他操作（例如在我從頭開始構建樹時生成新子級，但為了簡單起見，我省略了這些部分）。但基本上，我正在通過這樣的樹：
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)
uj5u.com熱心網友回復：
利用遞回的自相似性，這與任何其他單程 O(n) 深度/樹高演算法相同，除了在備份呼叫堆疊時為每個節點設定最大深度屬性：
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]
根據后續的評論，如果你想一次性制作樹并分配最大深度，一種方法是從孩子中挑選出最大深度并在備份呼叫堆疊的途中將其分配給每個節點.
這是一個與庫無關的概念證明，因為我沒有您在新示例中擁有的類：
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)，因此在一次傳遞中完成所有操作可能是過早的優化，除非您有真正的大型或性能關鍵代碼。
uj5u.com熱心網友回復：
您可以使用廣度優先搜索來獲取所有節點的深度以及從根到每個節點的路徑，然后迭代所有節點的結果，產生最大深度：
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}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/377845.html