Maison 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"); ?>
Copier après la connexion

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
第二种和第三种方法的效率和内存消耗差别不大,但是第一种递归调用消耗的内存和时间都要大很多,有时候为了效率,可能采用非递归的实现方式比较的好。

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Guide d'installation et de mise à niveau de PHP 8.4 pour Ubuntu et Debian Guide d'installation et de mise à niveau de PHP 8.4 pour Ubuntu et Debian Dec 24, 2024 pm 04:42 PM

Guide d'installation et de mise à niveau de PHP 8.4 pour Ubuntu et Debian

Configuration du projet CakePHP Configuration du projet CakePHP Sep 10, 2024 pm 05:25 PM

Configuration du projet CakePHP

Date et heure de CakePHP Date et heure de CakePHP Sep 10, 2024 pm 05:27 PM

Date et heure de CakePHP

Téléchargement de fichiers CakePHP Téléchargement de fichiers CakePHP Sep 10, 2024 pm 05:27 PM

Téléchargement de fichiers CakePHP

Routage CakePHP Routage CakePHP Sep 10, 2024 pm 05:25 PM

Routage CakePHP

Discuter de CakePHP Discuter de CakePHP Sep 10, 2024 pm 05:28 PM

Discuter de CakePHP

Comment configurer Visual Studio Code (VS Code) pour le développement PHP Comment configurer Visual Studio Code (VS Code) pour le développement PHP Dec 20, 2024 am 11:31 AM

Comment configurer Visual Studio Code (VS Code) pour le développement PHP

Guide rapide CakePHP Guide rapide CakePHP Sep 10, 2024 pm 05:27 PM

Guide rapide CakePHP

See all articles