PHP实现二叉树的深度优先与广度优先遍历方法
本文实例讲述了PHP实现二叉树的深度优先与广度优先遍历方法。分享给大家供大家参考。具体如下：
#二叉树的广度优先遍历
#使用一个队列实现
classNode{
public$data=null;
public$left=null;
public$right=null;
}
#@param$btree二叉树根节点
functionbreadth_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;
}
#深度优先遍历,使用一个栈实现
functiondepth_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=newNode();
$node1=newNode();
$node2=newNode();
$node3=newNode();
$node4=newNode();
$node5=newNode();
$node6=newNode();
$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程序设计有所帮助。