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

您应该使您的< code>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

Answer 2

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

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函数可以在这里找到。