Python中嵌套字典中的二叉树

Question

如何构建给定嵌套字典的二叉树?理想情况下，我希望访问根，然后以常规的深度优先或宽度优先的方式遍历树。

在时间或空间方面，当从嵌套字典构建树时，我不太关心效率，所以我不介意在这个过程中使用额外的数据结构。我主要关注的是一个全面和直观的解决方案。我现在不知道从哪里开始，所以请帮助我，我将不胜感激。

class Vertex:
"""Vertex object in a binary tree."""
def __init__(self):
"""Initialize Vertex object.
Fields
----------
value : int
The value of node v
left : None
The left child of node v
right : None
The right child of node v
"""
self.value = None
self.left = None
self.right = None

def dict_to_binary_tree(data):
"""Implementation here."""
return root

if __name__ == '__main__':
t = {
"value": 1,
"left": {
"value": 2,
"left": {
"value": 3,
"left": None,
"right": None
},
"right": {
"value": 4,
"left": None,
"right": None
}
},
"right": {
"value": 2,
"left": {
"value": 4,
"left": None,
"right": None
},
"right": {
"value": 3,
"left": None,
"right": None
}
}
}
root = dict_to_binary_tree(t)
# traverse tree i.e. dfs(root), bfs(root)

二叉树是这样的:

1
/ 
2   2
/  / 
3  4 4  3

Answer 1

遍历字典的递归函数应该可以很好地完成这项工作:

def VertexFromDict(d):
if not d: return None
v       = Vertex()
v.value = d['value']
v.left  = VertexFromDict(d.get('left'))
v.right = VertexFromDict(d.get('right'))
return v

输出:

root = VertexFromDict(t)
printBTree(root,lambda v:(str(v.value),v.left,v.right))
1
__/ _
2      2
/     / 
3   4  4   3

注意:我用来打印树的printBTree函数可以在这里找到。

Answer 2

你应该让你的Vertex构造函数更通用一点，这样它就可以使用参数来初始化属性。

:

class Vertex:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

那么你的函数可以是递归的，像这样:

def dict_to_binary_tree(data):
return data and Vertex(
data["value"], 
dict_to_binary_tree(data["left"]), 
dict_to_binary_tree(data["right"])
)

要有一个简单的深度优先迭代，在Node类上定义__iter__:

class Vertex:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def __iter__(self):
yield self.value
if self.left:
yield from self.left
if self.right:
yield from self.right

现在你的主代码可以这样做:

root = dict_to_binary_tree(t)
print(*root)  # will print values in depth-first, pre-order