php教程 PHP源码 三种遍历树的方法

三种遍历树的方法

May 25, 2016 pm 05:15 PM
php

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

<?php

define(&#39;DS&#39;, DIRECTORY_SEPARATOR);

function rec_list_files($from = &#39;.&#39;)

{

    if(!is_dir($from)) {

        return array();

    }

    $files = array();

    if($dh = opendir($from))

    {

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

            

            if($file == &#39;.&#39; || $file == &#39;..&#39;) {

                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 = &#39;.&#39;)

{

    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 == &#39;.&#39; || $file == &#39;..&#39;) {

                    continue;

                }

                $path = $dir . DS . $file;

                if(is_dir($path)) {

                    $dirs[] = $path;

                } else {

                    $files[] = $path;

                }

            }

            closedir($dh);

        }

    }

    return $files;

}



function breadth_first_files($from = &#39;.&#39;) {

    $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 == &#39;.&#39; || $child == &#39;..&#39;) {

                    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 &#39;<pre class="brush:php;toolbar:false">----------------------- Test run for &#39;.$func.&#39;() &#39;;

    flush();

    $time_start = microtime(true);

    $list = $func($trydir);

    //print_r($list);

    $time = microtime(true) - $time_start;

    echo &#39;Finished : &#39;.count($list).&#39; files
'; $mem2 = memory_get_peak_usage(); printf('
Max memory for &#39;.$func.&#39;() : %0.2f kbytes Running time for &#39;.$func.&#39;() : %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
第二种和第三种方法的效率和内存消耗差别不大,但是第一种递归调用消耗的内存和时间都要大很多,有时候为了效率,可能采用非递归的实现方式比较的好。

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Dec 24, 2024 pm 04:42 PM

Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드

CakePHP 프로젝트 구성 CakePHP 프로젝트 구성 Sep 10, 2024 pm 05:25 PM

CakePHP 프로젝트 구성

CakePHP 날짜 및 시간 CakePHP 날짜 및 시간 Sep 10, 2024 pm 05:27 PM

CakePHP 날짜 및 시간

CakePHP 파일 업로드 CakePHP 파일 업로드 Sep 10, 2024 pm 05:27 PM

CakePHP 파일 업로드

CakePHP 라우팅 CakePHP 라우팅 Sep 10, 2024 pm 05:25 PM

CakePHP 라우팅

CakePHP 토론 CakePHP 토론 Sep 10, 2024 pm 05:28 PM

CakePHP 토론

PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법 PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법 Dec 20, 2024 am 11:31 AM

PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법

CakePHP 빠른 가이드 CakePHP 빠른 가이드 Sep 10, 2024 pm 05:27 PM

CakePHP 빠른 가이드

See all articles