如何将Python递归实现的目录树生成改为迭代方式？

核心解决思路 #

递归转迭代的核心是用栈模拟递归调用栈，同时严格对齐递归版本的两个关键逻辑，就能保证输出顺序完全一致：

1. 子项排序规则一致：迭代时必须和递归版本使用相同的子项排序逻辑（比如先目录后文件，同类型按名称字典序排序），这是顺序正确的基础。
2. 栈的入栈顺序控制：利用栈「后进先出」的特性，将子项逆序压入栈，这样弹出处理时就能和递归的正序遍历保持一致。
3. 前缀状态传递：每个子项的树形前缀（├──、└──、│ 等）依赖父项是否为最后一个子项，需要在压栈时准确传递该状态，保证树形结构的线条正确。

对比代码示例 #

递归版本的tree_body函数 #

import os
import hashlib

def calculate_md5(file_path, chunk_size=4096):
    md5 = hashlib.md5()
    with open(file_path, 'rb') as f:
        for chunk in iter(lambda: f.read(chunk_size), b''):
            md5.update(chunk)
    return md5.hexdigest()

def tree_body(path, prefix="", is_last=False):
    # 排序规则：先目录（not isdir为False，排序权重低），后文件；同类型按名称字典序
    items = sorted(os.listdir(path), key=lambda x: (not os.path.isdir(os.path.join(path, x)), x))
    for i, item in enumerate(items):
        item_path = os.path.join(path, item)
        is_last_item = (i == len(items) - 1)
        current_prefix = prefix + ("└── " if is_last_item else "├── ")
        
        if os.path.isdir(item_path):
            print(f"{current_prefix}{item}/")
            # 更新子目录的前缀：父项是最后一个则用空格填充，否则用竖线连接
            new_prefix = prefix + ("    " if is_last_item else "│   ")
            tree_body(item_path, new_prefix, is_last_item)
        else:
            md5 = calculate_md5(item_path)
            print(f"{current_prefix}{item} [{md5}]")

# 调用示例
if __name__ == "__main__":
    root = "./test_dir"
    print(f"{os.path.basename(root)}/")
    tree_body(root)

迭代版本的tree_body函数 #

def tree_body_iterative(root_path):
    # 栈元素格式：(文件/目录路径, 父级前缀, 是否是父项的最后一个子项, 类型标记)
    # 类型标记："dir_unprocessed"（未处理的目录，需先输出目录名再处理子项）、"file"（文件，直接输出）
    stack = []
    
    # 初始化：输出根目录，将根目录的子项逆序压入栈
    print(f"{os.path.basename(root_path)}/")
    root_items = sorted(os.listdir(root_path), key=lambda x: (not os.path.isdir(os.path.join(root_path, x)), x))
    for i in reversed(range(len(root_items))):
        item_path = os.path.join(root_path, root_items[i])
        is_last = (i == len(root_items) - 1)
        stack.append(
            (item_path, "", is_last, "dir_unprocessed") 
            if os.path.isdir(item_path) 
            else (item_path, "", is_last, "file")
        )
    
    while stack:
        path, parent_prefix, is_last_item, item_type = stack.pop()
        
        if item_type == "dir_unprocessed":
            # 输出当前目录
            dir_prefix = parent_prefix + ("└── " if is_last_item else "├── ")
            print(f"{dir_prefix}{os.path.basename(path)}/")
            # 生成子项的前缀
            new_parent_prefix = parent_prefix + ("    " if is_last_item else "│   ")
            # 获取并排序子项，逆序压入栈保证处理顺序和递归一致
            items = sorted(os.listdir(path), key=lambda x: (not os.path.isdir(os.path.join(path, x)), x))
            for i in reversed(range(len(items))):
                item_sub_path = os.path.join(path, items[i])
                sub_is_last = (i == len(items) - 1)
                stack.append(
                    (item_sub_path, new_parent_prefix, sub_is_last, "dir_unprocessed")
                    if os.path.isdir(item_sub_path)
                    else (item_sub_path, new_parent_prefix, sub_is_last, "file")
                )
        elif item_type == "file":
            # 计算MD5并输出文件项
            md5 = calculate_md5(path)
            file_prefix = parent_prefix + ("└── " if is_last_item else "├── ")
            print(f"{file_prefix}{os.path.basename(path)} [{md5}]")

# 调用示例
if __name__ == "__main__":
    root = "./test_dir"
    tree_body_iterative(root)

关键细节说明 #

1. 排序逻辑对齐：迭代版本的items排序规则和递归版本完全一致，确保目录和文件的相对顺序不变。
2. 逆序压栈：将子项从最后一个到第一个依次压入栈，弹出时就会按照递归的顺序（第一个到最后一个）处理，保证输出顺序完全匹配。
3. 前缀状态传递：每个栈元素携带「是否是父项最后一个子项」的状态，用于生成正确的树形线条，避免出现错乱的连接线。

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