Python如何将嵌套字典转换为二叉树并支持DFS/BFS遍历

核心逻辑说明 #

你给出的嵌套字典结构和二叉树节点结构完全匹配，递归是最容易理解的实现方式，不需要复杂的额外数据结构，逻辑链路完全和字典的嵌套层级对应：

• 遇到空值（None）直接返回，对应二叉树的空节点
• 每一层只处理当前字典对应的节点，子节点交给递归逻辑处理，最后返回当前构造完成的节点即可

完整代码实现 #

class Vertex:
    """二叉树的节点对象"""

    def __init__(self):
        """初始化节点对象
        属性
        ----------
        value : int
            节点存储的值
        left : None | Vertex
            节点的左孩子
        right : None | Vertex
            节点的右孩子
        """
        self.value = None
        self.left = None
        self.right = None


def dict_to_binary_tree(data):
    # 递归终止条件：当前传入的是None，对应空孩子节点
    if not data:
        return None
    # 构造当前节点
    current_node = Vertex()
    current_node.value = data["value"]
    # 递归构造左右子树
    current_node.left = dict_to_binary_tree(data["left"])
    current_node.right = dict_to_binary_tree(data["right"])
    # 返回构造好的当前节点
    return current_node


# 测试用的前序DFS遍历，验证构造结果是否正确
def dfs_preorder(node):
    if not node:
        return
    print(node.value, end=" ")
    dfs_preorder(node.left)
    dfs_preorder(node.right)


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)
    # 前序遍历输出：1 2 3 4 2 4 3 和预期结构匹配
    print("前序DFS遍历结果：")
    dfs_preorder(root)

输出验证 #

运行上述代码会输出前序遍历结果 1 2 3 4 2 4 3，和你给出的目标二叉树结构完全匹配。你也可以替换成BFS或者其他遍历方式验证构造结果。

内容的提问来源于stack exchange，提问作者Gonzo