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

php  /  管理员 发布于 7年前   275

本文实例讲述了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 Class&Object -- PHP 自排序二叉树的深入解析
• PHP实现的线索二叉树及二叉树遍历方法详解
• php实现的二叉树遍历算法示例
• PHP构造二叉树算法示例
• PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】
• PHP实现从上往下打印二叉树的方法
• PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
• PHP获取二叉树镜像的方法
• PHP实现判断二叉树是否对称的方法
• PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
• PHP排序二叉树基本功能实现方法示例