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

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

概述：

二叉树遍历原理如下：

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

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相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

赞 (0)

相关推荐

  • PHP实现按之字形顺序打印二叉树的方法

    本文实例讲述了PHP实现按之字形顺序打印二叉树的方法.分享给大家供大家参考,具体如下: 问题 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推. 解决思路 使用两个栈 实现代码 <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $

  • PHP获取二叉树镜像的方法

    本文实例讲述了PHP获取二叉树镜像的方法.分享给大家供大家参考,具体如下: 问题 操作给定的二叉树,将其变换为源二叉树的镜像. 解决思路 翻转二叉树,有递归和非递归两种方式,非递归就是使用队列. 实现代码 <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ function Mirror(&$

  • PHP完全二叉树定义与实现方法示例

    PHP完全二叉树定义与实现方法示例

    本文实例讲述了PHP完全二叉树定义与实现方法.分享给大家供大家参考,具体如下: 若设二叉树的深度为h,除第 h 层外,其它各层 (1-h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树. PHP代码实现(暂时实现添加节点.层次遍历节点,删除节点后续更新) <?php class Node{ public $value; public $leftNode; public $rightNode; } /* 找到空节点 */ function findEmpyt

  • PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 广度优先遍历:又叫层次遍历,从上往下对每一层依

  • PHP排序二叉树基本功能实现方法示例

    本文实例讲述了PHP排序二叉树基本功能实现方法.分享给大家供大家参考,具体如下: 这里演示了排序二叉树节点的插入,中序遍历,极值的查找和特定值的查找的功能. 基本没有提供什么概念和定义.建议先简单了解一下本文提供的几个概念在来看本文. 实际上,只是简单的提供了代码,注释也很少,各位辛苦了. 二叉树:在计算机科学中,二叉树是每个节点最多有两个子树的树结构. 排序二叉树: 左孩子节点的值小于父节点的值,右孩子节点的值大于父节点的值. 几个概念: 根节点 叶子节点 左子树 右子树 中序遍历 前序遍历

  • PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】

    PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】

    本文实例讲述了PHP实现绘制二叉树图形显示功能.分享给大家供大家参考,具体如下: 前言: 最近老师布置了一个作业:理解并实现平衡二叉树和红黑树,本来老师是说用C#写的,但是我学的C#基本都还给老师了,怎么办?那就用现在最熟悉的语言PHP来写吧! 有一个问题来了,书上在讲解树的时候基本上会给出形象的树形图.但是当我们自己试着实现某种树,在调试.输出的时候确只能以字符的形式顺序地输出.这给调试等方面带来了很大的不便.然后在各种百度之后,我发现利用PHP实现二叉树的图形显示的资源几乎是零!好吧,那我就

  • php实现二叉树中和为某一值的路径方法

    二叉树中和为某一值的路径: 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径.(注意: 在返回值的list中,数组长度大的数组靠前) 思路: 1.二叉树的前序遍历,中左右顺序 2.把目标值target传进去,target-=val 3.target为0并且left和right都为null,达到叶结点 4.函数外部两个数组,list数组存一条路径,listAll数组存所有路径 FindPath(roo

  • PHP实现从上往下打印二叉树的方法

    本文实例讲述了PHP实现从上往下打印二叉树的方法.分享给大家供大家参考,具体如下: 问题 从上往下打印出二叉树的每个节点,同层节点从左至右打印. 解决思路 每层树从左到右打印,所以需要将节点的左右子树存起来,因为先进先出,所以用队列. 实现代码 /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ function

  • PHP实现判断二叉树是否对称的方法

    本文实例讲述了PHP实现判断二叉树是否对称的方法.分享给大家供大家参考,具体如下: 问题 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 题解 递归判断二叉树两侧. 实现代码: <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ func

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

    本文实例讲述了PHP基于非递归算法实现先序.中序及后序遍历二叉树操作.分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树. ABDHECFG 2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树. HDBEAFCG 3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点. HDEBFGCA 实现方法: 先序遍历:利用栈先进后出的特性,先访问根节点,再把右子树压入,再压入左子树.这样取出的

  • JavaScript实现多叉树的递归遍历和非递归遍历算法操作示例

    本文实例讲述了JavaScript实现多叉树的递归遍历和非递归遍历算法操作.分享给大家供大家参考,具体如下: 演示之前的准备工作 演示项目的文件结构: index.html jsonData.js recurrenceTree.js noRecurrenceTree.js 解释一下各个文件: index.html 是用来演示的 HTML 文件. jsonData.js 里面存储着多叉树的JSON数据. recurrenceTree.js 递归算法遍历树. noRecurrenceTree.js

  • PHP框架Laravel中使用UUID实现数据分表操作示例

    本文实例讲述了PHP框架Laravel中使用UUID实现数据分表操作.分享给大家供大家参考,具体如下: UUID UUID是指在一台机器上生成的数字,它保证对在同一时空中的所有机器都是唯一的. 说的简单点,它就是通过一个规则(如:业务标识号+年月日+当日自增数字格式化)生成的一个具有唯一性的辨识资讯.用于关联我们的一些额数据和资讯. 实例 之前在做一个项目的时候用到这个东西,现在我就用Laravel框架写一个简单的demo 前端form表单 <!DOCTYPE html> <html&g

  • php中10个不同等级压缩优化图片操作示例

    本文实例分析了php中10个不同等级压缩优化图片操作.分享给大家供大家参考,具体如下: 今天找到一个php写的压缩图片程序,可以分10个等级(0-9)来压缩,0等级时压缩比率不是很大,图片不会失真:随着压缩等级不断增大,图片会变得越来越不清晰,通常压缩后图片大小可以减少到原来的50%,压缩比还是挺大的. 如下是php压缩图片程序 <?php Header("Content-type: image/PNG");/*告诉IE浏览器你做的程序是张图片*/ $image = @image

  • Python实现读取txt文件中的数据并绘制出图形操作示例

    Python实现读取txt文件中的数据并绘制出图形操作示例

    本文实例讲述了Python实现读取txt文件中的数据并绘制出图形操作.分享给大家供大家参考,具体如下: 下面的是某一文本文件中的数据. 6.1101,17.592 5.5277,9.1302 8.5186,13.662 7.0032,11.854 5.8598,6.8233 8.3829,11.886 7.4764,4.3483 8.5781,12 6.4862,6.5987 5.0546,3.8166 5.7107,3.2522 14.164,15.505 5.734,3.1551 8.408

  • jquery 遍历hash操作示例【基于ajax交互】

    jquery 遍历hash操作示例【基于ajax交互】

    本文实例讲述了jquery 遍历hash操作.分享给大家供大家参考,具体如下: <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <meta http-equiv="X-UA-Co

  • Java中父类和子类之间的转换操作示例

    本文实例讲述了Java中父类和子类之间的转换操作.分享给大家供大家参考,具体如下: 一.父类引用强转成为子类引用 package learn20180720; public class People { private String name; private Integer age; private Double height; public People(){ this.name = ""; this.age = 0 ; this.height = 0.0; } public Pe

  • MySQL存储过程中游标循环的跳出和继续操作示例

    最近遇到这样的问题,在MySQL的存储过程中,游标操作时,需要执行一个conitnue的操作.众所周知,MySQL中的游标循环操作常用的有三种,LOOP,REPEAT,WHILE.三种循环,方式大同小异.以前从没用过,所以记下来,方便以后查阅. 1.REPEAT 复制代码 代码如下: REPEAT     Statements;   UNTIL expression END REPEAT demo DECLARE num INT; DECLARE my_string  VARCHAR(255);

  • PHP中的按位与和按位或操作示例

    按位与主要是对二进制数操作. 代码如下: 复制代码 代码如下: <?php $a = 1; $b = 2; $c = $a^b; echo $c // 3 ?> 这里不是单纯的相加关系 十进制 1换算成二进制 00000001 十进制 2换算成二进制 00000010 按位^ 00000011 // 就是不相同的都算成1 啦 ^_^ 然后, 复制代码 代码如下: <?php $a = 1; $b = 2; echo $a & $c; // 1 ?> 十进制 3换算成二进制

随机推荐