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

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

2020-11-23 15:01风雨征途2012 PHP教程

这篇文章主要介绍了PHP实现二叉树的深度优先与广度优先遍历方法,涉及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);