【IO编程】深度优先遍历

深度优先遍历目录（Depth-First Traversal） 是一种递归或栈式的目录遍历方法，优先深入到子目录中，再回溯到父目录继续遍历其他子目录。这是一种常见的文件系统操作，适用于查找文件、统计目录大小等场景。

深度优先遍历完整思路

1. 递归式遍历：优先进入子目录，完成当前目录所有子目录的遍历后再返回上一层。
2. 适合处理嵌套结构：目录树是一个递归结构，深度优先遍历特别适用于这种嵌套结构。
3. 有序性：
   • 由上至下：先访问父目录，再依次深入子目录。
   • 从左至右：每层目录按照特定顺序（如字母顺序）排列。

代码详情具体实现深度优先遍历目录的过程（通过代码的编程思路直观的理解深度优先的编程思路）

在 C语言 中，可以使用 dirent.h 提供的函数（如 opendir() 和 readdir()）来遍历目录。同时可以使用递归来实现深度优先遍历。

#include <stdio.h>
#include <stdlib.h>
#include <dirent.h>
#include <sys/stat.h>
#include <string.h>

// 深度优先遍历目录
void dfs_directory(const char *path, int depth) {
    DIR *dir = opendir(path);
    if (dir == NULL) {
        perror("opendir");
        return;
    }

    struct dirent *entry;
    while ((entry = readdir(dir)) != NULL) {
        // 跳过当前目录和父目录
        if (strcmp(entry->d_name, ".") == 0 || strcmp(entry->d_name, "..") == 0) {
            continue;
        }

        // 构造完整路径
        char full_path[1024];
        snprintf(full_path, sizeof(full_path), "%s/%s", path, entry->d_name);

        // 判断是否为目录
        struct stat st;
        if (stat(full_path, &st) == 0 && S_ISDIR(st.st_mode)) {
            // 打印目录并递归进入
            printf("%*s[DIR] %s\n", depth * 2, "", full_path);
            dfs_directory(full_path, depth + 1);
        } else {
            // 打印文件
            printf("%*s[FILE] %s\n", depth * 2, "", entry->d_name);
        }
    }

    closedir(dir);
}

int main(int argc, char *argv[]) {
    const char *start_path = argc > 1 ? argv[1] : ".";
    dfs_directory(start_path, 0);
    return 0;
}

再使用 Python 实现，因为 python 轻量级语言，实现过程更为简洁：
Python 的标准库 os 和 os.path 提供了文件和目录操作的相关工具，可以轻松实现深度优先遍历目录。
代码逻辑（递归实现）：

import os

def dfs_directory(path, depth=0):
    # 打印当前目录
    print("  " * depth + f"[DIR] {path}")

    # 遍历当前目录的所有文件和子目录
    for entry in os.listdir(path):
        full_path = os.path.join(path, entry)
        # 如果是目录，则递归遍历
        if os.path.isdir(full_path):
            dfs_directory(full_path, depth + 1)
        else:
            # 如果是文件，则打印文件路径
            print("  " * (depth + 1) + f"[FILE] {entry}")

# 调用函数
start_path = "./test_directory"  # 替换为需要遍历的目录
dfs_directory(start_path)

我们先假设目录结构如下：

test_directory/
├── file1.txt
├── subdir1/
│   ├── file2.txt
│   └── file3.txt
└── subdir2/
    └── subsubdir/
        └── file4.txt

输出：

[DIR] ./test_directory
  [FILE] file1.txt
  [DIR] ./test_directory/subdir1
    [FILE] file2.txt
    [FILE] file3.txt
  [DIR] ./test_directory/subdir2
    [DIR] ./test_directory/subdir2/subsubdir
      [FILE] file4.txt

另一种实现方式：栈实现（非递归）：
深度优先遍历也可以通过栈来实现，避免递归调用的栈深度限制。

import os

def dfs_directory_stack(path):
    # 使用栈实现深度优先遍历
    stack = [path]

    while stack:
        current_path = stack.pop()
        if os.path.isdir(current_path):
            print(f"[DIR] {current_path}")
            # 将当前目录的内容加入栈
            for entry in sorted(os.listdir(current_path), reverse=True):
                stack.append(os.path.join(current_path, entry))
        else:
            print(f"[FILE] {current_path}")

# 调用函数
start_path = "./test_directory"  # 替换为需要遍历的目录
dfs_directory_stack(start_path)

也可以直接使用 Shell 实现，不用写代码，Shell 脚本中可以使用 find 命令来实现深度优先遍历：

find ./test_directory

输出：

./test_directory
./test_directory/file1.txt
./test_directory/subdir1
./test_directory/subdir1/file2.txt
./test_directory/subdir1/file3.txt
./test_directory/subdir2
./test_directory/subdir2/subsubdir
./test_directory/subdir2/subsubdir/file4.txt

深度优先遍历的应用场景

• 文件搜索：
  • 在复杂的目录树中查找特定文件或文件类型。
  • 示例：查找所有 .txt 文件：

import os

def find_txt_files(path):
    for root, dirs, files in os.walk(path):
        for file in files:
            if file.endswith(".txt"):
                print(os.path.join(root, file))

find_txt_files("./test_directory")

• 目录大小统计：
  • 统计目录及其子目录的总大小。
  • 示例代码：

import os

def calculate_directory_size(path):
    total_size = 0
    for root, dirs, files in os.walk(path):
        for file in files:
            file_path = os.path.join(root, file)
            total_size += os.path.getsize(file_path)
    return total_size

print(f"Total size: {calculate_directory_size('./test_directory')} bytes")

• 备份工具：遍历目录树并复制文件到备份位置。
• 文件清理：删除某些特定类型的文件或空文件夹。
• 目录树展示：以树状结构展示目录层级。

使用深度优先遍历具有诸多好处：递归实现方式与目录树结构天然契合，代码思路简单直观；适合嵌套结构，能深入到子目录，适合操作深层嵌套的目录；占用资源少：在处理大目录时，深度优先遍历通常比广度优先遍历占用内存更少。不过，在应用过程中也需要注意一些可能会出现的问题：① 可能导致栈溢出：如果目录嵌套过深，递归实现可能导致栈溢出。② 目录顺序不固定：由于深度优先的遍历顺序，无法保证目录按字母顺序排列。

深度优先遍历目录是一种高效、灵活的目录操作方法，尤其适用于嵌套结构的文件系统。通过递归或栈实现深度优先遍历，可以方便地完成文件搜索、目录统计等任务。我们以上提供了三种不同的实现方式（但代码思路是一致的），综上。希望该内容能对你有帮助，感谢您的阅读！

以上。仅供学习与分享交流，请勿用于商业用途！转载需提前说明。

我是一个十分热爱技术的程序员，希望这篇文章能够对您有帮助，也希望认识更多热爱程序开发的小伙伴。
感谢！