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判断是否连接上网络的方法

本文实例讲述了PHP判断是否连接上网络的方法。分享给大家供大家参考。具体实现方法如下: 首先写个函数 function varify_url($url){ $check = @fo...

PHP设计模式之工厂方法设计模式实例分析

本文实例讲述了PHP设计模式之工厂方法设计模式。分享给大家供大家参考,具体如下: 一、什么是工厂方法模式 作为一种创建型设计模式,工厂方法模式就是要创建“某种东西”。对于工厂方法,要创建...

PHP使用finfo_file()函数检测上传图片类型的实现方法

本文实例讲述了PHP使用finfo_file()函数检测上传图片类型的实现方法。分享给大家供大家参考,具体如下: 在输入输出中,文件的交互必不可少,比如文件的上传什么的。这里我们来解决一...

PHP中4个加速、缓存扩展的区别和选用建议

折腾VPS的朋友,在安装好LNMP等Web运行环境后都会选择一些缓存扩展安装以提高PHP运行速度,常被人介绍的有eAccelerator、memcached、xcache、Alterna...

php获取QQ头像并显示的方法

本文实例讲述了php获取QQ头像并显示的方法。分享给大家供大家参考。具体分析如下: 最近看到博客留言的头像有点别扭,因为游客的头像都是同一个头像,看着不是很舒服。虽然现在绝大多数的主题集...