python递归存储树
时间: 2023-09-02 11:11:38 浏览: 49
递归存储树可以使用Python的字典来实现。首先,我们需要定义一个节点类来表示树中的每个节点,包括节点的值和子节点列表。然后,我们可以使用递归函数来构建树,并将其存储在字典中。下面是一个示例代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.children = []
def build_tree(node_dict, root_val):
root = TreeNode(root_val)
if root_val not in node_dict:
return root
for child_val in node_dict[root_val]:
child = build_tree(node_dict, child_val)
root.children.append(child)
return root
def store_tree(root):
if not root:
return {}
node_dict = {root.val: []}
for child in root.children:
child_dict = store_tree(child)
node_dict[root.val].append(child.val)
node_dict.update(child_dict)
return node_dict
# 示例使用
node_dict = {
1: [2, 3],
2: [4, 5],
3: [6],
4: [],
5: [7],
6: [8],
7: [],
8: []
}
root = build_tree(node_dict, 1)
tree_dict = store_tree(root)
print(tree_dict)
```
运行上述代码后,输出结果为:
```
{1: [2, 3], 2: [4, 5], 4: [], 5: [7], 7: [], 3: [6], 6: [8], 8: []}
```
这个字典表示的树的结构如下:
```
1
/ \
2 3
/ \ |
4 5 6
/ |
7 8
```
可以看出,树的每个节点都被存储在字典中,其键为节点值,值为该节点的子节点列表。如果一个节点没有子节点,那么在字典中它的值就是一个空列表。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)