从Python字典构建二叉树

Question

字典有经理员工关系的键和值对，经理键可以有多个员工，这些员工可以有自己的员工，如下所示

data = {
    "Amy": ["Alice", "Charlie"],
    "Alice": ["Akon", "Eve"],
    "Eve": ["Frank", None],
    "Charlie": ["Bob", "Grace"]
}

虽然我可以看到所有节点都已添加到下面的打印语句中，但我无法正确打印树。

这是代码

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def construct_binary_tree(data, root_key):
    if root_key not in data:
        return None
    
    print("Constructing node:", root_key)
    root = TreeNode(root_key)
    if root_key in data:
        children = data[root_key]
        left_child_key = children[0] if children and len(children) > 0 else None
        right_child_key = children[1] if children and len(children) > 1 else None
        print("Left child of", root_key, ":", left_child_key)
        print("Right child of", root_key, ":", right_child_key)
        if left_child_key:
            root.left = construct_binary_tree(data, left_child_key)
        if right_child_key:
            root.right = construct_binary_tree(data, right_child_key)
    
    return root

def print_tree(root, depth=0):
    if root:
        print("   " * depth + f"|-- {root.key}")
        print_tree(root.left, depth + 1)
        print_tree(root.right, depth + 1)

# Given data
data = {
    "Amy": ["Alice", "Charlie"],
    "Alice": ["Akon", "Eve"],
    "Eve": ["Frank", None],
    "Charlie": ["Bob", "Grace"]
}

# Construct binary tree
root_key = next(iter(data))
root = construct_binary_tree(data, root_key)

# Print binary tree in tree format
print_tree(root)

这是我看到的输出

Constructing node: Amy
Left child of Amy : Alice
Right child of Amy : Charlie
Constructing node: Alice
Left child of Alice : Akon
Right child of Alice : Eve
Constructing node: Eve
Left child of Eve : Frank
Right child of Eve : None
Constructing node: Charlie
Left child of Charlie : Bob
Right child of Charlie : Grace
|-- Amy
   |-- Alice
      |-- Eve
   |-- Charlie

Answer 1

您正在测试字符串是否位于

data

开头的

construct_binary_tree

键中，如果不存在则返回

None

。这意味着当您传入像

"Bob"

这样的名称时，它会立即返回

None

而不是树节点。当你去打印它时，没有提到

"Bob"

，只有

None

。考虑返回一个树节点而不是 None。

def construct_binary_tree(data, root_key):
    if root_key not in data:
        return TreeNode(root_key)
    

这样做将打印：

|-- Amy
   |-- Alice
      |-- Akon
      |-- Eve
         |-- Frank
   |-- Charlie
      |-- Bob
      |-- Grace

还有很多其他问题，因为此方法似乎依赖于数据顺序来工作，但它应该可以帮助您解决当前的问题。