三种遍历树的方法

夏雪君_4729

夏雪君_4729

2016-05-25

1415人浏览

原创

树的概念在开发里面是很重要的一部分,xml的文档对象模型(dom)就是一棵树,文件夹文件的结构也是一棵树。遍历树是开发中经常要遇到的一个问题,比如,要找出dom里面的img 标签的个数,就要遍历一棵dom树。要在一个目录里面查找是否有一个文件也要用到遍历这个目录。在这里我们以遍历文件为例,说明遍历树的三种基本的方法:
递归深度优先算法,非递归深度优先算法,非递归广度优先算法。
    这些算法是我们在项目中经常重复的一些算法,我感觉我写程序以来,我做的大多数算法都用了大二学的那本数据结构,有些时候,只是改装一些一些算法,有些时候也只是把几种算法合并一下,也许这是为什么数据结构这本书这样重要的原因。
先看代码:

<?php define('DS', DIRECTORY_SEPARATOR);

function rec_list_files($from = '.')

{

    if(!is_dir($from)) {

        return array();

    }

    $files = array();

    if($dh = opendir($from))

    {

        while(false !== ($file = readdir($dh))) {

            

            if($file == '.' || $file == '..') {

                continue;

            }

            $path = $from . DS . $file;

            

            if (is_file($path)) {

                $files[] = $path;

            }

            $files = array_merge($files, rec_list_files($path));

        }

        closedir($dh);

    }

    return $files;

}



function deep_first_list_files($from = '.')

{

    if(!is_dir($from)) {

        return false;

    }

    $files = array();

    $dirs = array($from);

    while(NULL !== ($dir = array_pop($dirs))) {

        if( $dh = opendir($dir)) {

            while( false !== ($file = readdir($dh))) {

                if($file == '.' || $file == '..') {

                    continue;

                }

                $path = $dir . DS . $file;

                if(is_dir($path)) {

                    $dirs[] = $path;

                } else {

                    $files[] = $path;

                }

            }

            closedir($dh);

        }

    }

    return $files;

}



function breadth_first_files($from = '.') {

    $queue = array(rtrim($from, DS).DS);// normalize all paths

    $files = array();

    while($base = array_shift($queue )) {

        if (($handle = opendir($base))) {

            while (($child = readdir($handle)) !== false) {

               if( $child == '.' || $child == '..') {

                    continue;

                }

                if (is_dir($base.$child)) {

                    $combined_path = $base.$child.DS;

                    array_push($queue, $combined_path);

                } else {

                    $files[] = $base.$child;

                }

            }

            closedir($handle);

        } // else unable to open directory => NEXT CHILD

    }

    return $files; // end of tree, file not found

}



function profile($func, $trydir)

{

    $mem1 = memory_get_usage();

    echo '<pre class="brush:php;toolbar:false;">----------------------- Test run for '.$func.'() ';

    flush();

    $time_start = microtime(true);

    $list = $func($trydir);

    //print_r($list);

    $time = microtime(true) - $time_start;

    echo 'Finished : '.count($list).' files
';     $mem2 = memory_get_peak_usage();     printf('
Max memory for '.$func.'() : %0.2f kbytes Running time for '.$func.'() : %0.f s
',     ($mem2-$mem1)/1024.0, $time);     return $list; } profile('rec_list_files', "D:\www\server"); profile('deep_first_list_files', "D:\www\server"); profile('breadth_first_files', "D:\www\server"); ?>

rec_list_files 是递归的深度优先的算法,这个是用一个简单的函数递归来实现,用array_merge 来合并数组
deep_first_list_files 是非递归的深度优先的算法,用了一个栈来实现。
breadth_first_files 是非递归的广度优先算法,用了一个队列来实现。
顺便说一句,php中的数组,可以做为hashtable,queue,stack,普通数组,甚至做树也是可以的。运行的结果:
-----------------------
Test run for rec_list_files() ...Finished : 1868 files
Max memory for rec_list_files() : 496.93 kbytes Running time for rec_list_files() : 9.231678 s
-----------------------
Test run for deep_first_list_files() ...Finished : 1868 files
Max memory for deep_first_list_files() : 432.41 kbytes Running time for deep_first_list_files() : 3.940216 s
-----------------------
Test run for breadth_first_files() ...Finished : 1868 files
Max memory for breadth_first_files() : 432.55 kbytes Running time for breadth_first_files() : 3.749125 s
第二种和第三种方法的效率和内存消耗差别不大,但是第一种递归调用消耗的内存和时间都要大很多,有时候为了效率,可能采用非递归的实现方式比较的好。

btpanel phpsite 宝塔面板PHP网站
btpanel phpsite 宝塔面板PHP网站

宝塔面板 PHP 网站管理:站点创建、删除、启停、PHP 版本切换、域名管理、SSL证书管理、伪静态管理、数据库管理

下载

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

php

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

2026.11.20

20

7

Navicat入门教程大全
Navicat入门教程大全

本专题整理Navicat入门教程,从认识软件界面到开展数据库操作,介绍初次使用需要了解的知识和方法。内容兼顾连接配置、数据管理及日常使用中的疑问,方便用户按学习进度查阅,为后续实践和独立操作打好基础。

2026.11.20

20

17

Navicat数据库连接配置指南
Navicat数据库连接配置指南

从确认数据库信息到建立可用连接,本专题串联Navicat连接数据库的相关知识和操作方法。既有初次配置时需要了解的基础内容,也有连接后的检查思路,方便用户按实际需求查阅教程,逐步熟悉数据库连接的设置流程。

2026.11.20

0

10

PHP8.6数组与数据处理教程
PHP8.6数组与数据处理教程

本专题汇总PHP8.6数组与数据处理教程,涵盖CSV读取和导出、引用遍历删除、array_filter回调模式、配置键名冲突、pathinfo文件名校验、GMP大整数进制转换及UTF-8正则筛选,说明升级兼容变化、输入范围和失败处理方法。

2026.11.20

60

8

PHP8.6升级迁移教程
PHP8.6升级迁移教程

本专题汇总PHP8.6升级迁移与弃用接口改造教程,涵盖反射调用、对象属性赋值、标识符更名、构造函数与__debugInfo调整,以及插件类名检查、常量导出、ArrayIterator排序、SPL和DTO查询参数转换,帮助梳理弃用提示并完成代码兼容改造。

2026.11.20

0

10

PHP8.6安装配置与FPM运维教程
PHP8.6安装配置与FPM运维教程

本专题汇总PHP8.6正式版安装部署与FPM运维教程,涵盖Linux并存安装、独立ini配置、扩展重新编译、Nginx切换与回滚、FPM状态监控和慢日志排查,以及环境变量、请求超时、OPcache刷新和预加载配置。

2026.11.20

40

10

Nginx CVE-2026-123007排查与防护指南
Nginx CVE-2026-123007排查与防护指南

Nginx HTTP/2漏洞该怎么修复?本专题围绕CVE-2026-123007,介绍安全版本升级、模块兼容检查和配置恢复方法,以及日志排查、权限设置等后续加固操作,方便你按实际部署情况查找对应教程。

2026.11.20

40

8

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

80

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

100

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
墨刀帮助中心
墨刀帮助中心

共0课时 | 0人学习

MyEclipse学习中心
MyEclipse学习中心

共0课时 | 0人学习