开发者社区> php的小菜鸟> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例

简介: 本文实例讲述了PHP基于非递归算法实现先序、中序及后序遍历二叉树操作。分享给大家供大家参考,具体如下 概述: 二叉树遍历原理如下: image 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树。
+关注继续查看

本文实例讲述了PHP基于非递归算法实现先序、中序及后序遍历二叉树操作。分享给大家供大家参考,具体如下

概述:

二叉树遍历原理如下:

img_9840a808b5a4a89430e2ea8bd9ed351c.jpe
image

针对上图所示二叉树遍历:

1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树。

ABDHECFG

2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树。

HDBEAFCG

3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点。

HDEBFGCA

实现方法:

先序遍历:利用栈先进后出的特性,先访问根节点,再把右子树压入,再压入左子树。这样取出的时候是先取出左子树,最后取出右子树。

function preorder($root){
 $stack = array();
 array_push($stack, $root);
 while(!empty($stack)){
  $center_node = array_pop($stack);
  echo $center_node->value; // 根节点
  if($center_node->right != null)
   array_push($stack, $center_node->right); // 压入右子树
  if($center_node->left != null)
   array_push($stack, $center_node->left); // 压入左子树
 }
}

中序:需要从下向上遍历,所以先把左子树压入栈,然后逐个访问根节点和右子树。

function inorder($root){
 $stack = array();
 $center_node = $root;
 while(!empty($stack) || $center_node != null){
  while($center_node != null){
   array_push($stack, $center_node);
   $center_node = $center_node->left;
  }
  $center_node = array_pop($stack);
  echo $center_node->value;
  $center_node = $center_node->right;
 }
}

后序:先把根节点存起来,然后依次储存左子树和右子树。然后输出。

function tailorder($root){
 $stack = array();
 $outstack = array();
 array_push($$stack, $root);
 while($empty($stack)){
  $center_node = array_pop($stack);
  array_push($outstack, $center_node);
  if($center_node->right != null)
   array_push($stack, $center_node->right);
  if($center_node->left != null)
   array_push($stack, $center_node->left);
 }
 while($empty($outstack)){
  $center_node = array_pop($outstack);
  echo $center_node->value;
 }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
php操作mysql防止sql注入(合集)
php操作mysql防止sql注入(合集)
0 0
PHP操作文件上传
PHP操作文件上传
0 0
头歌php mysql操作答案
头歌php mysql操作答案
0 0
Java存储数据库中时间戳和php操作数据库时间戳的关系
Java存储数据库中时间戳和php操作数据库时间戳的关系
0 0
PHP: MongoDB的CRUD操作
PHP: MongoDB的CRUD操作
0 0
PHP中MySQL操作
本次使用的demo是MySQL的示例数据库employees,点击下载地址,注意在导入的时候,在employees.sql文件中,将source改成你当前的目录。
0 0
三分钟掌握PHP操作数据库
三分钟掌握PHP操作数据库
0 0
PHP之大数据加减乘除操作函数
PHP之大数据加减乘除操作函数
0 0
PHP:array数组的增、删、改、查操作
PHP:array数组的增、删、改、查操作
0 0
+关注
php的小菜鸟
热爱编程,忠于开源的小码农
文章
问答
文章排行榜
最热
最新
相关电子书
更多
PHP安全开发_从白帽角度做安全
立即下载
PHP在机器学习上的应用及云深度学习平台的架构设计与实现
立即下载
PHP与APM_技术内幕和最佳实践
立即下载