PHP实现二叉树的深度优先与广度优先遍历方法
发布:smiling 来源: PHP粉丝网 添加日期:2021-06-19 20:51:43 浏览: 评论:0
这篇文章主要介绍了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 (!emptyempty($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 (!emptyempty($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);
Tags: PHP二叉树 PHP遍历
- 上一篇:PHP+AJAX实现投票功能的方法
- 下一篇:四个PHP非常实用的功能
相关文章
- ·PHP实现判断二叉树是否对称的方法(2021-08-29)
- ·PHP实现按之字形顺序打印二叉树的方法(2021-08-30)
- ·PHP实现从上往下打印二叉树的方法(2021-08-30)
- ·PHP遍历解析XML成数组实现方法(2014-08-20)
- ·PHP glob函数遍历目录/文件夹方法介绍(2014-09-21)
- ·PHP使用glob函数遍历目录或文件夹的方法(2021-05-03)
- ·PHP遍历XML文档所有节点的方法(2021-05-16)
- ·php遍历树的常用方法汇总(2021-05-28)
- ·php通过前序遍历树实现无需递归的无限极分类(2021-06-11)
- ·PHP实现基于图的深度优先遍历输出1,2,3...n的全排列功能(2021-08-19)
- ·PHP实现图的邻接矩阵表示及几种简单遍历算法分析(2021-08-20)
- ·PHP实现的栈数据结构示例【入栈、出栈、遍历栈】(2021-08-23)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)