Python 中嵌套字典的二叉树

Question

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

根据时间或 space 从嵌套字典构建树时，我不太关心效率，所以我不介意在此过程中使用其他数据结构。我的主要重点是全面而直观的解决方案。我现在不知道从哪里开始，所以非常感谢您的帮助。

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)

这是二叉树的样子：

Answer 1

您应该使 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 class 上定义 __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函数可以找到here.

Python 中嵌套字典的二叉树

Binary tree from nested dictionary in Python

python

tree

binary-tree

dictionary

data-structures