PHP实现二叉树的深度优先与广度优先遍历方法

yipeiwu_com5年前PHP代码库

本文实例讲述了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函数import_request_variables()用法分析

本文实例分析了PHP函数import_request_variables()用法。分享给大家供大家参考,具体如下: import_request_variables 函数可以在 regi...

使用PHP实现二分查找算法代码分享

第一种方法: 【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。    【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表...

php验证手机号码

大家都应该有这个常识,中国的手机号码都是以数字“1”开头,然后利用“0~9”10个数字组成的11位数字组合,那么我们的验证规则肯定要根据这个思路来写。 根据上面的简单思路,我们便可以写下...

PHP生成静态HTML文档实现代码

利用PHP,将数据库中的文章数据生成单个的HTML文档。首先,有利于搜索引擎的收录。其次,避免数据库中的字段暴露在地址栏上,更安全。 给出代码: <?php //引...

php 来访国内外IP判断代码并实现页面跳转

我大概构思了一下,有两个方案: 1. Javascript判断来访者的浏览器语言,如果是中文系统,自然使用者都是中国人,跳中文网站; 如果是非中文系统,默认使用者非中国人,跳英文网站。...