当前位置:首页 > PHP教程 > php应用 > 列表

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

发布:smiling 来源: PHP粉丝网  添加日期:2021-06-19 20:51:43 浏览: 评论:0 

这篇文章主要介绍了PHP实现二叉树的深度优先与广度优先遍历方法,涉及php针对二叉树进行遍历的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下。

本文实例讲述了PHP实现二叉树的深度优先与广度优先遍历方法,分享给大家供大家参考,具体如下:

  1. #二叉树的广度优先遍历 
  2. #使用一个队列实现 
  3. class Node { 
  4.  public $data = null; 
  5.  public $left = null; 
  6.  public $right = null; 
  7. #@param $btree 二叉树根节点 
  8. function breadth_first_traverse($btree) { 
  9.  $traverse_data = array(); 
  10.  $queue = array(); 
  11.  array_unshift($queue$btree); #根节点入队 
  12.  while (!emptyempty($queue)) { #持续输出节点,直到队列为空 
  13.    $cnode = array_pop($queue); #队尾元素出队 
  14.    $traverse_data[] = $cnode->data; 
  15.    #左节点先入队,然后右节点入队 
  16.    if ($cnode->left != null) array_unshift($queue$cnode->left); 
  17.    if ($cnode->right != null) array_unshift($queue$cnode->right); 
  18.  } 
  19.  return $traverse_data
  20. #深度优先遍历,使用一个栈实现 
  21. function depth_first_traverse($btree) { 
  22. $traverse_data = array(); 
  23. $stack = array(); 
  24. array_push($stack$btree); 
  25. while (!emptyempty($stack)) { 
  26.   $cnode = array_pop($stack); 
  27.   $traverse_data[] = $cnode->data; 
  28.   if ($cnode->right != null) array_push($stack$cnode->right); 
  29.   if ($cnode->left != null) array_push($stack$cnode->left); 
  30. return $traverse_data
  31. $root = new Node(); 
  32. $node1 = new Node(); 
  33. $node2 = new Node(); 
  34. $node3 = new Node(); 
  35. $node4 = new Node(); 
  36. $node5 = new Node(); 
  37. $node6 = new Node(); 
  38. $root->data = 1; 
  39. $node1->data = 2; 
  40. $node2->data = 3; 
  41. $node3->data = 4; 
  42. $node4->data = 5; 
  43. $node5->data = 6; 
  44. $node6->data = 7; 
  45. $root->left = $node1
  46. $root->right = $node2
  47. $node1->left = $node3
  48. $node1->right = $node4
  49. $node2->left = $node5
  50. $node2->right = $node6
  51. $traverse = breadth_first_traverse($root); 
  52. print_r($traverse); 
  53. echo ""
  54. $traverse = depth_first_traverse($root); 
  55. print_r($traverse);

Tags: PHP二叉树 PHP遍历

分享到: