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

2024-09-29 23:41:19

本文实例讲述了PHP实现按之字形顺序打印二叉树的方法。分享给大家供大家参考，具体如下：

问题

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

解决思路

使用两个栈

实现代码

<?php
/*class TreeNode{
  var $val;
  var $left = NULL;
  var $right = NULL;
  function __construct($val){
    $this->val = $val;
  }
}*/
function MyPrint($pRoot)
{
  if($pRoot == NULL)
    return [];
  $current = 0;
  $next  = 1;
  $stack[0] = array();
  $stack[1] = array();
  $resultQueue = array();
  array_push($stack[0], $pRoot);
  $i = 0;
  $result = array();
  $result[0]= array();
  while(!empty($stack[0]) || !empty($stack[1])){
    $node = array_pop($stack[$current]);
    array_push($result[$i], $node->val);
    //var_dump($resultQueue);echo "</br>";
    if($current == 0){
      if($node->left != NULL)
        array_push($stack[$next], $node->left);
      if($node->right != NULL)
        array_push($stack[$next], $node->right);
    }else{
      if($node->right != NULL)
        array_push($stack[$next], $node->right);
      if($node->left != NULL)
        array_push($stack[$next], $node->left);
    }
    if(empty($stack[$current])){
      $current = 1-$current;
      $next  = 1-$next;
      if(!empty($stack[0]) || !empty($stack[1])){
        $i++;
        $result[$i] = array();
      }
    }
  }
  return $result;
}

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

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

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

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

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

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

本文实例讲述了PHP获取二叉树镜像的方法.分享给大家供大家参考,具体如下: 问题操作给定的二叉树,将其变换为源二叉树的镜像. 解决思路翻转二叉树,有递归和非递归两种方式,非递归就是使用队列. 实现代码 <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ function Mirror(&$
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基于非递归算法实现先序.中序及后序遍历二叉树操作.分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树. ABDHECFG 2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树. HDBEAFCG 3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点. HDEBFGCA 实现方法: 先序遍历:利用栈先进后出的特性,先访问根节点,再把右子树压入,再压入左子树.这样取出的
PHP完全二叉树定义与实现方法示例

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

本文实例讲述了C#使用前序遍历.中序遍历和后序遍历打印二叉树的方法.分享给大家供大家参考.具体实现方法如下: public class BinaryTreeNode { public BinaryTreeNode Left { get; set; } public BinaryTreeNode Right { get; set; } public int Data { get; set; } public BinaryTreeNode(int data) { this.Data = data;
Java实现打印二叉树所有路径的方法

本文实例讲述了Java实现打印二叉树所有路径的方法.分享给大家供大家参考,具体如下: 问题: 给一个二叉树,把所有的路径都打印出来. 比如,对于下面这个二叉树,它所有的路径为: 8 -> 3 -> 1 8 -> 2 -> 6 -> 4 8 -> 3 -> 6 -> 7 8 -> 10 -> 14 -> 13 思路: 从根节点开始,把自己的值放在一个数组里,然后把这个数组传给它的子节点,子节点同样把自己的值放在这个数组里,又传给自己的子节点,
C++基于先序、中序遍历结果重建二叉树的方法

本文实例讲述了C++基于先序.中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字.例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回. 实现代码: #include <iostream> #include <vector> #include <stack> using
通过先序遍历和中序遍历后的序列还原二叉树(实现方法)

当我们有一个先序遍历序列:1,3,7,9,5,11 中序遍历序列:9,7,3,1,5,11 我们可以很轻松的用笔写出对应的二叉树.但是用代码又该如何实现? 下面我们来简单谈谈基本思想. 首先,先序遍历的顺序是根据根-左孩子-右孩子的顺序遍历的,那么我们可以率先确认的是先序遍历序列的第一个数就是根节点,然后中序遍历是根据左孩子-根-右孩子的顺序遍历的.我们通过先序遍历确认了根节点,那么我们只需要在中序遍历中找到根节点的位置,然后就可以很好地区分出,那些属于左子树的节点,那些是属于右子树的
js利用递归与promise 按顺序请求数据的方法

问题:项目中有一个需求,一个tabBar下面如果没有内容就不让该tabBar显示,当然至于有没有内容,需要我们通过请求的来判断,但是由于请求是异步的,如何让请求按照tabBar的顺序进行? 方案:我们可以将promise变成下一个请求,可以利用递归来实现实施: //定义初始数据 requestlist就像tabBar列表 let requestlist = [1, 2, 3, 4, 5, 6, 7,8,9]; //每个tabBar的返回数据使用reslist装起来 let reslist =
Python利用前序和中序遍历结果重建二叉树的方法

本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 这道题比较容易,前序遍历的结果中,第一个结点一定是根结点,然后在中序遍历的结果中查找这个根结点,根结点左边的就是左子树,根结点右边的就是右子树,递归构造出左.右子树即可.示意图如图所示: 利用前序和中序遍历的结果重建二叉树 Python代码: # coding: utf-8 ''
Python编程实现双链表，栈，队列及二叉树的方法示例

本文实例讲述了Python编程实现双链表,栈,队列及二叉树的方法.分享给大家供大家参考,具体如下: 1.双链表 class Node(object): def __init__(self, value=None): self._prev = None self.data = value self._next = None def __str__(self): return "Node(%s)"%self.data class DoubleLinkedList(object): def
PHP实现的线索二叉树及二叉树遍历方法详解

本文实例讲述了PHP实现的线索二叉树及二叉树遍历方法.分享给大家供大家参考,具体如下: <?php require 'biTree.php'; $str = 'ko#be8#tr####acy#####'; $tree = new BiTree($str); $tree->createThreadTree(); echo $tree->threadList() . "\n";从第一个结点开始遍历线索二叉树 echo $tree->threadListReserv

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

相关推荐

随机推荐