PHP实现二叉树的深度优先与广度优先遍历方法_PHP
程序员文章站
2022-06-11 14:11:45
...
本文实例讲述了PHP实现二叉树的深度优先与广度优先遍历方法。分享给大家供大家参考。具体如下:
#二叉树的广度优先遍历 #使用一个队列实现 class Node { public $data = null; public $left = null; public $right = null; } #@param $btree 二叉树根节点 function breadth_first_traverse($btree) { $traverse_data = array(); $queue = array(); array_unshift($queue, $btree); #根节点入队 while (!empty($queue)) { #持续输出节点,直到队列为空 $cnode = array_pop($queue); #队尾元素出队 $traverse_data[] = $cnode->data; #左节点先入队,然后右节点入队 if ($cnode->left != null) array_unshift($queue, $cnode->left); if ($cnode->right != null) array_unshift($queue, $cnode->right); } return $traverse_data; } #深度优先遍历,使用一个栈实现 function depth_first_traverse($btree) { $traverse_data = array(); $stack = array(); array_push($stack, $btree); while (!empty($stack)) { $cnode = array_pop($stack); $traverse_data[] = $cnode->data; if ($cnode->right != null) array_push($stack, $cnode->right); if ($cnode->left != null) array_push($stack, $cnode->left); } return $traverse_data; } $root = new Node(); $node1 = new Node(); $node2 = new Node(); $node3 = new Node(); $node4 = new Node(); $node5 = new Node(); $node6 = new Node(); $root->data = 1; $node1->data = 2; $node2->data = 3; $node3->data = 4; $node4->data = 5; $node5->data = 6; $node6->data = 7; $root->left = $node1; $root->right = $node2; $node1->left = $node3; $node1->right = $node4; $node2->left = $node5; $node2->right = $node6; $traverse = breadth_first_traverse($root); print_r($traverse); echo ""; $traverse = depth_first_traverse($root); print_r($traverse);
希望本文所述对大家的php程序设计有所帮助。
推荐阅读
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
PHP实现二叉树的深度优先与广度优先遍历方法
-
深度优先遍历,广度优先遍历实现对象的深拷贝
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索
-
java数据结构与算法之二叉树深度优先和广度优先遍历
-
JavaScript实现树的遍历算法示例【广度优先与深度优先】
-
PHP实现基于图的深度优先遍历输出1,2,3...n的全排列功能
-
[PHP] 算法-邻接矩阵图的广度和深度优先遍历的PHP实现
-
go语言编程学习实现图的广度与深度优先搜索