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

Heiße KI -Werkzeuge

Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool
Ausziehbilder kostenlos

Clothoff.io
KI-Kleiderentferner

AI Hentai Generator
Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

Heiße Werkzeuge

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen

In diesem Kapitel werden wir die Umgebungsvariablen, die allgemeine Konfiguration, die Datenbankkonfiguration und die E-Mail-Konfiguration in CakePHP verstehen.

PHP 8.4 bringt mehrere neue Funktionen, Sicherheitsverbesserungen und Leistungsverbesserungen mit einer beträchtlichen Menge an veralteten und entfernten Funktionen. In dieser Anleitung wird erklärt, wie Sie PHP 8.4 installieren oder auf PHP 8.4 auf Ubuntu, Debian oder deren Derivaten aktualisieren. Obwohl es möglich ist, PHP aus dem Quellcode zu kompilieren, ist die Installation aus einem APT-Repository wie unten erläutert oft schneller und sicherer, da diese Repositorys in Zukunft die neuesten Fehlerbehebungen und Sicherheitsupdates bereitstellen.

Um in cakephp4 mit Datum und Uhrzeit zu arbeiten, verwenden wir die verfügbare FrozenTime-Klasse.

Um am Datei-Upload zu arbeiten, verwenden wir den Formular-Helfer. Hier ist ein Beispiel für den Datei-Upload.

In diesem Kapitel lernen wir die folgenden Themen im Zusammenhang mit dem Routing kennen.

CakePHP ist ein Open-Source-Framework für PHP. Es soll die Entwicklung, Bereitstellung und Wartung von Anwendungen erheblich vereinfachen. CakePHP basiert auf einer MVC-ähnlichen Architektur, die sowohl leistungsstark als auch leicht zu verstehen ist. Modelle, Ansichten und Controller gu

Visual Studio Code, auch bekannt als VS Code, ist ein kostenloser Quellcode-Editor – oder eine integrierte Entwicklungsumgebung (IDE) –, die für alle gängigen Betriebssysteme verfügbar ist. Mit einer großen Sammlung von Erweiterungen für viele Programmiersprachen kann VS Code c

Der Validator kann durch Hinzufügen der folgenden zwei Zeilen im Controller erstellt werden.
