树结构的遍历算法(文件目录的遍历)

文章目录

一、递归遍历

1.代码
2.遍历结果

二、栈模拟遍历

1.代码
2.遍历结果

三、队列模拟遍历

1.代码
2.遍历结果

四、深度遍历

1.理解
2.示意图

五、广度遍历

1.理解
2.示意图

这是一个树结构，需要遍历它！

一、递归遍历

1.代码

#Authors:xiaobei

import os
#递归遍历，其实也是深度遍历
def GetAllDir(path,tag = ""):                           #tag用作层次标记
    fileList = os.listdir(path)
    for filename in fileList:
        file_abs_path = os.path.join(path,filename)     #合成绝对路径
        if os.path.isdir(file_abs_path):                #判断是否为目录。若是调用自身递归遍历，递归的出口是“该路径为文件”
            print(tag+"<目录>:",filename)
            GetAllDir(file_abs_path,tag = tag+"     ")  #递归调用
        else:
            print(tag+"<文件>:",filename)
path = r"F:untitledDir1"
GetAllDir(path)

2.遍历结果

递归遍历
（说明：递归处理，优先处理目录，向深处延伸。从输出结果可以看出，错落有致的层级关系。)

二、栈模拟遍历

1.代码

#Authors:xiaobei

import os
#用栈模拟递归遍历
def GetAllDir(path):
    stack = []                              #创建空栈
    stack.append(path)                      #当栈为空的时候，结束循环
    while(len(stack)!=0):                   #循环从栈中取出文件路径（出栈）
        dirPath = stack.pop()               #stack。pop()默认把栈中最后一个元素删除，并返回第一个元素值,符合栈的“先进后出原则
        if(os.path.isfile(dirPath)):
            print("<文件>:",os.path.basename(dirPath))
        else:
            print("<目录>:",os.path.basename(dirPath))
            fileList = os.listdir(dirPath)
            for filename in fileList:       #循环找到路径下的文件，并压入栈中（文件入栈）
                file_abs_path = os.path.join(dirPath,filename)      #使用绝对路径
                if(os.path.isfile(file_abs_path)):
                    stack.append(file_abs_path)                     #如果是文件就等待稍后处理
            for filename in fileList:       #循环找到路径下的目录，并在文件之后压如栈中（由于栈“先进后出”的性质，优先处理目录）
                file_abs_path = os.path.join(dirPath,filename)      #使用绝对路径
                if(os.path.isdir(file_abs_path)):
                    stack.append(file_abs_path)
path = r"F:untitledDir1"
GetAllDir(path)

2.遍历结果

栈模拟递归
(说明：根据栈的特性，文件的出栈顺序是正确的，优先处理目录，向深处延伸。有于没有加层级区分，所以输出并齐。）

三、队列模拟遍历

1.代码

#Authors:xiaobei

import os,collections
#用队列遍历目录
def GetAllDir(path,tag = ""):
    queue = collections.deque()             #创建空队列
    queue.append(path)
    while(len(queue)!=0):                   #当队列为空，结束循环
        dirPath = queue.popleft()           #出队
        fileList = os.listdir(dirPath)      #获取路径文件列表 
        for filename in fileList:
            file_abs_path = os.path.join(dirPath,filename)  #使用绝对路径
            if(os.path.isdir(file_abs_path)):
                print(tag+"<目录>:",filename)                #如果是目录则（入队）
                queue.append(file_abs_path)
            else:
                print(tag+"<文件>:",filename)                #如果是文件则进行操做
        tag += "      "
path = r"F:untitledDir1"
GetAllDir(path)