php遍历树的常用方法汇总

这篇文章主要介绍了php遍历树的常用方法,实例分析了php常用的三种遍历树的技巧,需要的朋友可以参考下

本文实例讲述了php遍历树的常用方法。分享给大家供大家参考。具体如下：

一、递归的深度优先的算法：

1. <?php 
2. define('DS', DIRECTORY_SEPARATOR); 
3. function rec_list_files($from = '.') 
4. { 
5. if(!is_dir($from)) { 
6. return array(); 
7. } 
8. $files = array(); 
9. if($dh = opendir($from)) 
10. { 
11. while(false !== ($file = readdir($dh))) { 
12. if($file == '.' || $file == '..') { 
13. continue; 
14. } 
15. $path = $from . DS . $file; 
16.  
17. if (is_file($path)) { 
18. $files[] = $path; 
19. } 
20. $files = array_merge($files, rec_list_files($path)); 
21. } 
22. closedir($dh); 
23. } 
24. return $files; 
25. } 
26. function profile($func, $trydir) 
27. { 
28. $mem1 = memory_get_usage(); 
29. echo '<pre>----------------------- Test run for '.$func.'() '; 
30. flush(); 
31. $time_start = microtime(true); 
32. $list = $func($trydir); 
33. //print_r($list); 
34. $time = microtime(true) - $time_start; 
35. echo 'Finished : '.count($list).' files</pre>'; 
36. $mem2 = memory_get_peak_usage(); 
37. printf('<pre>Max memory for '.$func.'() : %0.2f kbytes Running time for '.$func.'() : %0.f s</pre>', 
38. ($mem2-$mem1)/1024.0, $time); 
39. return $list; 
40. } 
41. profile('rec_list_files', "D:/www/server"); 
42. ?> 

二、递归的深度优先的算法(用了一个栈来实现)

1. <?php 
2. define('DS', DIRECTORY_SEPARATOR); 
3. function deep_first_list_files($from = '.') 
4. { 
5. if(!is_dir($from)) { 
6. return false; 
7. } 
8. $files = array(); 
9. $dirs = array($from); 
10. while(NULL !== ($dir = array_pop($dirs))) { 
11. if( $dh = opendir($dir)) { 
12. while( false !== ($file = readdir($dh))) { 
13. if($file == '.' || $file == '..') { 
14. continue; 
15. } 
16. $path = $dir . DS . $file; 
17. if(is_dir($path)) { 
18. $dirs[] = $path; 
19. } else { 
20. $files[] = $path; 
21. } 
22. } 
23. closedir($dh); 
24. } 
25. } 
26. return $files; 
27. } 
28. function profile($func, $trydir) 
29. { 
30. $mem1 = memory_get_usage(); 
31. echo '<pre>----------------------- Test run for '.$func.'() '; 
32. flush(); 
33. $time_start = microtime(true); 
34. $list = $func($trydir); 
35. //print_r($list); 
36. $time = microtime(true) - $time_start; 
37. echo 'Finished : '.count($list).' files</pre>'; 
38. $mem2 = memory_get_peak_usage(); 
39. printf('<pre>Max memory for '.$func.'() : %0.2f kbytes Running time for '.$func.'() : %0.f s</pre>', 
40. ($mem2-$mem1)/1024.0, $time); 
41. return $list; 
42. } 
43. profile('deep_first_list_files', "D:/www/server"); 
44. ?> 

三、非递归的广度优先算法(用了一个队列来实现)

1. <?php 
2. define('DS', DIRECTORY_SEPARATOR); 
3. function breadth_first_files($from = '.') { 
4. $queue = array(rtrim($from, DS).DS);// normalize all paths 
5. $files = array(); 
6. while($base = array_shift($queue )) { 
7. if (($handle = opendir($base))) { 
8. while (($child = readdir($handle)) !== false) { 
9. if( $child == '.' || $child == '..') { 
10. continue; 
11. } 
12. if (is_dir($base.$child)) { 
13. $combined_path = $base.$child.DS; 
14. array_push($queue, $combined_path); 
15. } else { 
16. $files[] = $base.$child; 
17. } 
18. } 
19. closedir($handle); 
20. } // else unable to open directory => NEXT CHILD 
21. } 
22. return $files; // end of tree, file not found 
23. } 
24. function profile($func, $trydir) 
25. { 
26. $mem1 = memory_get_usage(); 
27. echo '<pre>----------------------- Test run for '.$func.'() '; 
28. flush(); 
29. $time_start = microtime(true); 
30. $list = $func($trydir); 
31. //print_r($list); 
32. $time = microtime(true) - $time_start; 
33. echo 'Finished : '.count($list).' files</pre>'; 
34. $mem2 = memory_get_peak_usage(); 
35. printf('<pre>Max memory for '.$func.'() : %0.2f kbytes Running time for '.$func.'() : %0.f s</pre>', 
36. ($mem2-$mem1)/1024.0, $time); 
37. return $list; 
38. } 
39. profile('breadth_first_files', "D:/www/server"); 
40. ?> 

希望本文所述对大家的php程序设计有所帮助。