Home>
#Binary tree breadth-first traversal
#Using a queue implementation
class node {
 public $data=null;
 public $left=null;
 public $right=null;
}
#@param $btree binary tree root node
function breadth_first_traverse ($btree) {
 $traverse_data=array ();
 $queue=array ();
 array_unshift ($queue, $btree);#Enqueue the root node
 while (! empty ($queue)) {#continuously output nodes,Until the queue is empty
   $cnode=array_pop ($queue);#Team tail element out of the team
   $traverse_data []=$cnode->data;
   #Left node enqueue first,Then the right node enqueues
   if ($cnode-&left;= null) array_unshift ($queue, $cnode-&left;left);
   if ($cnode->right!=null) array_unshift ($queue, $cnode->right);
 }
 return $traverse_data;
}
#Depth-first traversal,Use a stack implementation
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;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
  • Previous JS phone number verification method
  • Next JS dynamic date and time acquisition method