在 Python 中实施 Euler Tour
Implementing Euler Tour in Python
我正在尝试在 Python 中实现以下 Euler Tour。
但是,我坚持存储最高值。我的代码实现是:
def rmq(root, level, prev=None):
if not root:
return True
euler.append(root.data)
levels.append(level)
ret = rmq(root.left, level+1, (root.data, level))
ret = rmq(root.right, level+1, (root.data, level))
if not (root.left or root.right):
euler.append(prev[0])
levels.append(prev[1])
return True
if ret:
euler.append(root.data)
levels.append(level)
levels = []
euler = []
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.right.left = Node(8)
root.left.right.right = Node(9)
rmq(root, 0)
print(euler)
print(levels)
我从上面的代码中得到的输出,对于列表 Euler 和是:
[1, 2, 4, 2, 5, 8, 5, 9, 5, 5, 3, 6, 3, 7, 3, 3]
[0, 1, 2, 1, 2, 3, 2, 3, 2, 2, 1, 2, 1, 2, 1, 1]
最终目标是实施this,但采用更简单的方式。
请帮助我实现最终目标。
无需将当前元素传递到下一个递归级别。在它们自己的递归级别上处理每个元素值的存储更容易,就像这样(我确实重写了树的存储,以避免必须显式调用左右元素):
nodeChildren = {
1: [2, 3],
2: [4, 5],
5: [8, 9],
3: [6, 7]
}
elements = []
levels = []
def traverseNode(node, level=0):
elements.append(node)
levels.append(level)
if node in nodeChildren:
for child in nodeChildren[node]:
traverseNode(child, level+1)
elements.append(node)
levels.append(level)
traverseNode(1)
print(f"node elements: {elements}")
# output: node elements: [1, 2, 4, 2, 5, 8, 5, 9, 5, 2, 1, 3, 6, 3, 7, 3, 1]
print(f"levels: {levels}")
# output: levels: [0, 1, 2, 1, 2, 3, 2, 3, 2, 1, 0, 1, 2, 1, 2, 1, 0]
说明:
- nodeChildren object 是一个映射:对于每个具有 children 的节点号,给出一个 children 的列表。这适用于任何类型的树(请注意,我没有预见到检测循环的机制 - 在这种情况下你会得到堆栈溢出 :))
- traversnode 会将其编号和级别添加到相应的列表中
- 检查当前节点是否有children。如果是这样,它将递归遍历这些 children 和 re-append 本身到数字和级别列表。
我正在尝试在 Python 中实现以下 Euler Tour。
但是,我坚持存储最高值。我的代码实现是:
def rmq(root, level, prev=None):
if not root:
return True
euler.append(root.data)
levels.append(level)
ret = rmq(root.left, level+1, (root.data, level))
ret = rmq(root.right, level+1, (root.data, level))
if not (root.left or root.right):
euler.append(prev[0])
levels.append(prev[1])
return True
if ret:
euler.append(root.data)
levels.append(level)
levels = []
euler = []
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.right.left = Node(8)
root.left.right.right = Node(9)
rmq(root, 0)
print(euler)
print(levels)
我从上面的代码中得到的输出,对于列表 Euler 和是:
[1, 2, 4, 2, 5, 8, 5, 9, 5, 5, 3, 6, 3, 7, 3, 3]
[0, 1, 2, 1, 2, 3, 2, 3, 2, 2, 1, 2, 1, 2, 1, 1]
最终目标是实施this,但采用更简单的方式。
请帮助我实现最终目标。
无需将当前元素传递到下一个递归级别。在它们自己的递归级别上处理每个元素值的存储更容易,就像这样(我确实重写了树的存储,以避免必须显式调用左右元素):
nodeChildren = {
1: [2, 3],
2: [4, 5],
5: [8, 9],
3: [6, 7]
}
elements = []
levels = []
def traverseNode(node, level=0):
elements.append(node)
levels.append(level)
if node in nodeChildren:
for child in nodeChildren[node]:
traverseNode(child, level+1)
elements.append(node)
levels.append(level)
traverseNode(1)
print(f"node elements: {elements}")
# output: node elements: [1, 2, 4, 2, 5, 8, 5, 9, 5, 2, 1, 3, 6, 3, 7, 3, 1]
print(f"levels: {levels}")
# output: levels: [0, 1, 2, 1, 2, 3, 2, 3, 2, 1, 0, 1, 2, 1, 2, 1, 0]
说明:
- nodeChildren object 是一个映射:对于每个具有 children 的节点号,给出一个 children 的列表。这适用于任何类型的树(请注意,我没有预见到检测循环的机制 - 在这种情况下你会得到堆栈溢出 :))
- traversnode 会将其编号和级别添加到相应的列表中
- 检查当前节点是否有children。如果是这样,它将递归遍历这些 children 和 re-append 本身到数字和级别列表。