Python 從字典構造多叉樹

題目要求

構造一個樹節點類，每個節點都有一個int類型的值（val），和0個或多個子節點childs。
給定一個字典，其中字典的key為當前節點的val，value對應列表對應當前節點的childs的val值。

請將該字典的構造為多叉樹結構，使用root表示數的根節點，並打印每個節點的值及其子節點的值。（這裡確保OrderDict字典的第一個key為樹的根節點）。

代碼實現

from collections import defaultdict
class TreeNode(object):
def __init__(self, val=None) -> None:
self.val = val
self.childs = []
def add_childs(self, child: "TreeNode"):
self.childs.append(child)
def __repr__(self) -> str:
return str(self.val)
@classmethod
def build_tree(cls, input_dict: dict):
# 深度優先遍歷構造多叉樹結構
def dfs(node, input_dict):
if node.val in input_dict: # 當前節點還有子節點時，繼續對每個child向下構造
for val in input_dict[node.val]:
cur_node = TreeNode(val)
dfs(cur_node, input_dict)
node.add_childs(cur_node)
else: # 當前節點沒有子節點，直接返回
return
# 獲取字典的第一個key，並以此為根節點構造多叉樹
root = TreeNode(list(input_dict.keys())[0])
dfs(root, input_dict)
return root
@classmethod
def print_tree(cls, root: "TreeNode"):
"""按照字典輸入形式打印輸出"""
if root:
if root.childs:
print(root.val, ": ", end="")
print('[%s]' % (' '.join([str(_.val) for _ in root.childs])))
for node in root.childs:
cls.print_tree(node)
else:
print(root.val, ": []")
@classmethod
def print_tree_graph(cls, root: "TreeNode"):
"""按照樹的層級打印輸出"""
node_with_level = defaultdict(list)
node_with_level[0].append([root])
cur_level = 0
while node_with_level:
# 打印當前層節點
cur_nodes_lists = node_with_level.pop(cur_level)
for nodes_list in cur_nodes_lists:
print(nodes_list, end=" ")
for node in nodes_list: # 如果還有子節點，將其添加到下一層
if node.childs:
node_with_level[cur_level + 1].append(node.childs)
else: # 沒有子節點的話，使用[]占位
node_with_level[cur_level + 1].append([])
cur_level += 1
print()
input_dict = {

1: [2, 3, 4],
2: [5, 6],
3: [7],
7: [8, 9, 10],
}
tree = TreeNode.build_tree(input_dict)
TreeNode.print_tree(tree)
TreeNode.print_tree_graph(tree)

運行結果：

# print_tree方法輸出字典格式結果：
1 : [2 3 4]
2 : [5 6]
5 : []
6 : []
3 : [7]
7 : [8 9 10]
8 : []
9 : []
10 : []
4 : []
# print_tree_graph方法輸出類似數層級結構格式的結果：
[1]
[2, 3, 4]
[5, 6] [7] []
[] [] [8, 9, 10]
[] [] []

對於第二種輸出格式，其關系為：

 +---+
| 1 |
+-+-+
|
|
+---+-v-+---+
+----+ 2 | 3 | 4 +--+
| +---+-+-+---+ |
| | |
| | |
+-v-+---+ +v--+ +-v+
| 5 | 6 | | 7 | | |
+-+-+--++ +-+-+ +--+
| | |
| | |
+-v+ +v-+ +-v-+---+---+
| | | | | 8 | 9 | 10|
+--+ +--+ ++--+-+-+--++
| | |
| | |
+v-+ +v-+ +v-+
| | | | | |
+--+ +--+ +--+