Python案例如何构建树形数据？

本文目录导读：

1. 使用字典构建树
2. 使用类构建树
3. 实际案例：文件系统树
4. 通用树构建工具
5. 树的遍历方法
6. 推荐使用场景

我来详细介绍几种在Python中构建树形数据的常用方法。

使用字典构建树

基础树结构

# 简单的树形字典结构
tree = {
    'id': 1,
    'name': '根节点',
    'children': [
        {
            'id': 2,
            'name': '子节点1',
            'children': [
                {'id': 4, 'name': '叶子节点1', 'children': []},
                {'id': 5, 'name': '叶子节点2', 'children': []}
            ]
        },
        {
            'id': 3,
            'name': '子节点2',
            'children': [
                {'id': 6, 'name': '叶子节点3', 'children': []}
            ]
        }
    ]
}

从列表数据构建树

def build_tree_from_list(data, parent_id=None):
    """
    从平面数据列表构建树形结构
    data: [{'id': 1, 'parent_id': None, 'name': 'root'}, ...]
    """
    tree = []
    for item in data:
        if item['parent_id'] == parent_id:
            children = build_tree_from_list(data, item['id'])
            if children:
                item['children'] = children
            else:
                item['children'] = []
            tree.append(item)
    return tree
# 示例数据
flat_data = [
    {'id': 1, 'parent_id': None, 'name': '根节点'},
    {'id': 2, 'parent_id': 1, 'name': '子节点1'},
    {'id': 3, 'parent_id': 1, 'name': '子节点2'},
    {'id': 4, 'parent_id': 2, 'name': '叶子节点1'},
    {'id': 5, 'parent_id': 2, 'name': '叶子节点2'},
    {'id': 6, 'parent_id': 3, 'name': '叶子节点3'}
]
tree = build_tree_from_list(flat_data)
print(tree)

使用类构建树

节点类定义

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
        self.parent = None
    def add_child(self, child):
        child.parent = self
        self.children.append(child)
    def get_depth(self):
        depth = 0
        parent = self.parent
        while parent:
            depth += 1
            parent = parent.parent
        return depth
    def print_tree(self):
        spaces = ' ' * self.get_depth() * 3
        prefix = spaces + '|__' if self.parent else ''
        print(prefix + self.data)
        if self.children:
            for child in self.children:
                child.print_tree()
# 构建树
root = TreeNode('根节点')
child1 = TreeNode('子节点1')
child2 = TreeNode('子节点2')
root.add_child(child1)
root.add_child(child2)
grandchild1 = TreeNode('叶子节点1')
grandchild2 = TreeNode('叶子节点2')
child1.add_child(grandchild1)
child1.add_child(grandchild2)
root.print_tree()

实际案例：文件系统树

import os
from pathlib import Path
class FileTreeNode:
    def __init__(self, path):
        self.path = Path(path)
        self.name = self.path.name
        self.is_dir = self.path.is_dir()
        self.children = []
        self.size = self.path.stat().st_size if self.path.is_file() else 0
    def build(self):
        """递归构建文件树"""
        if not self.is_dir:
            return self
        try:
            for item in self.path.iterdir():
                node = FileTreeNode(item)
                if item.is_dir():
                    node.build()
                self.children.append(node)
        except PermissionError:
            pass
        return self
    def print_tree(self, indent=''):
        """打印文件树"""
        if self.is_dir:
            print(f"{indent}📁 {self.name}/")
            new_indent = indent + '    '
            for child in self.children:
                child.print_tree(new_indent)
        else:
            size_str = f" ({self.size/1024:.1f}KB)" if self.size > 0 else ""
            print(f"{indent}📄 {self.name}{size_str}")
    def get_size(self):
        """获取目录总大小"""
        if not self.is_dir:
            return self.size
        return sum(child.get_size() for child in self.children)
# 使用示例
def show_directory_tree(directory_path):
    root = FileTreeNode(directory_path)
    root.build()
    print(f"目录树: {directory_path}")
    root.print_tree()
    if root.is_dir:
        total_size = root.get_size()
        print(f"\n总大小: {total_size/1024:.2f} KB")
# 查看当前目录的文件树
show_directory_tree('.')

通用树构建工具

from typing import Any, Dict, List, Optional
class TreeBuilder:
    """通用树构建器"""
    @staticmethod
    def build_from_parent_id(
        items: List[Dict[str, Any]],
        id_field: str = 'id',
        parent_field: str = 'parent_id',
        children_field: str = 'children'
    ) -> List[Dict[str, Any]]:
        """
        从包含parent_id的列表构建树
        """
        # 创建id到节点的映射
        item_map = {item[id_field]: {**item, children_field: []} for item in items}
        tree = []
        for item in item_map.values():
            parent_id = item.get(parent_field)
            if parent_id is None or parent_id not in item_map:
                tree.append(item)
            else:
                item_map[parent_id][children_field].append(item)
        return tree
    @staticmethod
    def flatten_tree(
        tree: List[Dict[str, Any]],
        children_field: str = 'children'
    ) -> List[Dict[str, Any]]:
        """将树形结构扁平化"""
        flat_list = []
        def flatten(node):
            node_copy = {k: v for k, v in node.items() if k != children_field}
            flat_list.append(node_copy)
            for child in node.get(children_field, []):
                flatten(child)
        for node in tree:
            flatten(node)
        return flat_list
    @staticmethod
    def find_node(
        tree: List[Dict[str, Any]],
        predicate: callable,
        children_field: str = 'children'
    ) -> Optional[Dict[str, Any]]:
        """在树中查找节点"""
        for node in tree:
            if predicate(node):
                return node
            if children_field in node:
                result = TreeBuilder.find_node(
                    node[children_field], predicate, children_field
                )
                if result:
                    return result
        return None
# 使用示例
data = [
    {'id': 1, 'parent_id': None, 'name': '研发部'},
    {'id': 2, 'parent_id': 1, 'name': '前端组'},
    {'id': 3, 'parent_id': 1, 'name': '后端组'},
    {'id': 4, 'parent_id': 2, 'name': '张三'},
    {'id': 5, 'parent_id': 2, 'name': '李四'},
    {'id': 6, 'parent_id': 3, 'name': '王五'}
]
# 构建树
tree = TreeBuilder.build_from_parent_id(data)
print("构建的树:", tree)
# 扁平化
flat = TreeBuilder.flatten_tree(tree)
print("扁平化后:", flat)
# 查找节点
found = TreeBuilder.find_node(tree, lambda n: n['name'] == '张三')
print("查找到的节点:", found)

树的遍历方法

class TreeTraversal:
    """树的遍历方法"""
    @staticmethod
    def dfs_preorder(node, visit_func):
        """深度优先-前序遍历"""
        visit_func(node)
        if 'children' in node and node['children']:
            for child in node['children']:
                TreeTraversal.dfs_preorder(child, visit_func)
    @staticmethod
    def dfs_postorder(node, visit_func):
        """深度优先-后序遍历"""
        if 'children' in node and node['children']:
            for child in node['children']:
                TreeTraversal.dfs_postorder(child, visit_func)
        visit_func(node)
    @staticmethod
    def bfs(node, visit_func):
        """广度优先遍历"""
        queue = [node]
        while queue:
            current = queue.pop(0)
            visit_func(current)
            if 'children' in current and current['children']:
                queue.extend(current['children'])
# 使用示例
def print_name(node):
    print(node['name'])
# 构建简单的树
sample_tree = {
    'id': 1, 'name': 'A',
    'children': [
        {'id': 2, 'name': 'B', 'children': [
            {'id': 4, 'name': 'D', 'children': []},
            {'id': 5, 'name': 'E', 'children': []}
        ]},
        {'id': 3, 'name': 'C', 'children': [
            {'id': 6, 'name': 'F', 'children': []}
        ]}
    ]
}
print("前序遍历:")
TreeTraversal.dfs_preorder(sample_tree, print_name)
print("\n后序遍历:")
TreeTraversal.dfs_postorder(sample_tree, print_name)
print("\n广度优先遍历:")
TreeTraversal.bfs(sample_tree, print_name)

推荐使用场景

1. 简单的数据展示：使用字典结构
2. 需要方法和属性：使用类结构
3. 大量数据转换：使用函数式方法
4. 文件系统操作：使用Pathlib结合自定义类
5. 需要序列化：使用字典结构，方便JSON转换

选择哪种方法取决于你的具体需求,但核心思想都是通过递归来构建和操作树形结构。