讲师中心 微信公众号
首页
文章
后端开发 web前端 数据库 开发工具 php框架 常见问题 人工智能 Java 系统教程 电脑教程 硬件教程 手机教程 软件教程 游戏教程 自媒体 新闻
专题
后端开发 web前端 数据库 开发工具 php框架 人工智能 Java 系统教程 电脑教程 硬件教程 手机教程 软件教程 游戏教程 新闻
AI工具
AI 聊天问答 Agent智能体 AI 文本写作 AI 绘画作图 AI 设计工具 AI 视频创作 AI 音频制作 AI 办公学习 AI 编程开发 AI 提示词
学习
大前端 后端开发 数据库 移动端 运维开发 计算机基础
编程手册
大前端 后端开发 数据库 移动端 运维开发 计算机基础
下载
js特效 网站源码 工具下载 类库下载 网站素材 学习资源 插件扩展 手机游戏
最近更新
当前位置：首页 > php教程 > PHP源码 >

正文

0

0

php 二叉树遍历算法与例子

php中文网

php中文网

发布时间：2016-06-08 17:20:43

|

1783人浏览过

|

来源于php中文网

原创

二叉树算法在小编大学时学数据结构时会学到的一个算法了，这个可以在搜索与排序中提高50%的搜索性能了，下面我们来看一些关于php 二叉树遍历算法与例子吧。

  二叉树遍历，是值从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问依

tupan062.gif

 

图是百度搜的。。。谢谢提供图的英雄。。

    前序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则先遍历左树，再遍历右树，遍历顺序为ABCDEGF。

立即学习“PHP免费学习笔记（深入）”；

    中序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从根节点开始，中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树，遍历顺序为CBEGDFA。

    后序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从左到右先叶子后节点的访问遍历访问左右子树，最后是访问根节点。访问顺序为CGEFDBA。

    层序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按照从左到右的顺序对节点逐个访问。访问顺序为ABCDEFG。

 

    现在，我们用PHP代码，来遍历二叉树结构。二叉树是放一个大数组，每一个节点都有三个字段，data表示这个节点的值，lChild表示这个节点的左边子节点，rChild表示这个节点的右边子节点。二叉树的结构我们用上面那张图。

 

二叉树结构代码如下：

//二叉树

$arr = array(

    'data' => 'A',

    'lChild' => array(

        'data' => 'B',

        'lChild' => array(

            'data' => 'C',

            'lChild' => array(),

            'rChild' => array(),

        ),

        'rChild' => array(

            'data' => 'D',

            'lChild' => array(

                'data' => 'E',

                'lChild' => array(),

                'rChild' => array(

                    'data' => 'G',

                    'lChild' => array(),

                    'rChild' => array(),

                ),

            ),

            'rChild' => array(

                'data' => 'F',

                'lChild' => array(),

                'rChild' => array(),

            ),

        ),

    ),

    'rChild' => array(),

);

 

遍历算法一：前序遍历二叉树

//前序遍历二叉树算法

echo '前序遍历二叉树算法：';

PreOrderTraverse($arr);

拍我AI
拍我AI

AI视频生成平台PixVerse的国内版本

下载

echo '
';

function PreOrderTraverse($node){

    if(empty($node)){

        return;

    }

    //输出值

    print_r($node['data']);

    //左节点

    PreOrderTraverse($node['lChild']);

    //右节点

    PreOrderTraverse($node['rChild']);

}

 

遍历算法二：中序遍历二叉树

//中序遍历二叉树算法

echo '中序遍历二叉树算法：';

inOrderTraverse($arr);

echo '
';

function inOrderTraverse($node){

    if(empty($node)){

        return;

    }

    //左节点

    inOrderTraverse($node['lChild']);

    //输出值

    print_r($node['data']);

    //右节点

    inOrderTraverse($node['rChild']);

}

 

遍历算法三：后序遍历二叉树

//后序遍历二叉树算法

echo '后序遍历二叉树算法：';

postOrderTraverse($arr);

echo '
';

function postOrderTraverse($node){

    if(empty($node)){

        return;

    }

    //左节点

    postOrderTraverse($node['lChild']);

    //右节点

    postOrderTraverse($node['rChild']);

    //输出值

    print_r($node['data']);

}


例子

/**
 *二叉树的创建及基本操作
 *
 *1.构造方法,初始化建立二叉树
 *2.按先序遍历方式建立二叉树
 *3.按先序遍历二叉树
 *4.先序遍历的非递归算法
 *5.中序遍历二叉树
 *6.中序遍历的非递归算法
 *7.后序遍历二叉树
 *8.后序遍历非递归算法
 *9.层次遍历二叉树
 *10.求二叉树叶子结点的个数
 *11.求二叉树的深度
 *12.判断二叉树是否为空树
 *13.置空二叉树
 *
 *@author xudianyang
 *@version $Id:BinaryTree.class.php,v 1.0 2011/02/13 13:33:00 uw Exp
 *@copyright ©2011,xudianyang
 */
header('content-type:text/html;charset=gb2312');

//在PHP数据结构之五 栈的PHP的实现和栈的基本操作 可以找到该类
include_once("./StackLinked.class.php");

//在 PHP数据结构之七 队列的链式存储和队列的基本操作 可以找到该类
include_once('./QueueLinked.class.php');
class BTNode{
 //左子树“指针”
 public $mLchild=null;
 //右子树“指针”
 public $mRchild=null;
 //结点数据域
 public $mData=null; //左标志域，为1时表示mLchild“指向”结点左孩子，为2表示“指向”结点直接前驱
 public $intLeftTag=null;
 //右标志域，为1时表示mRchild“指向”结点右孩子，为2表示“指向”结点直接后继
 public $intRightTag=null;
}
class BinaryTree{
 //根结点
 public $mRoot;
 //根据先序遍历录入的二叉树数据
 public $mPBTdata=null;
 /**
  *构造方法,初始化建立二叉树
  *
  *@param array $btdata 根据先序遍历录入的二叉树的数据，一维数组，每一个元素代表二叉树一个结点值,扩充结点值为''[长度为0的字符串]
  *@return void
  */
 public function __construct($btdata=array()){
  $this->mPBTdata=$btdata;
  $this->mRoot=null;
  $this->getPreorderTraversalCreate($this->mRoot);
 }
 /**
  *按先序遍历方式建立二叉树
  *
  *@param BTNode 二叉树结点，按引用方式传递
  *@return void
  */
 public function getPreorderTraversalCreate(&$btnode){
  $elem=array_shift($this->mPBTdata);
  if($elem === ''){
   $btnode=null;
  }else if($elem === null){
   return;
  }else{
   $btnode=new BTNode();
   $btnode->mData=$elem;
   $this->getPreorderTraversalCreate($btnode->mLchild);
   $this->getPreorderTraversalCreate($btnode->mRchild);
  }
 }
 /**
  *判断二叉树是否为空
  *
  *@return boolean 如果二叉树不空返回true,否则返回false
  **/
 public function getIsEmpty(){
  if($this->mRoot instanceof BTNode){
   return false;
  }else{
   return true;
  }
 }
 /**
  *将二叉树置空
  *
  *@return void
  */
 public function setBinaryTreeNull(){
  $this->mRoot=null;
 }
 /**
  *按先序遍历二叉树
  *
  *@param BTNode $rootnode 遍历过程中的根结点
  *@param array $btarr 接收值的数组变量，按引用方式传递
  *@return void
  */
 public function getPreorderTraversal($rootnode,&$btarr){
  if($rootnode!=null){
   $btarr[]=$rootnode->mData;
   $this->getPreorderTraversal($rootnode->mLchild,$btarr);
   $this->getPreorderTraversal($rootnode->mRchild,$btarr);
  }
 }
 /**
  *先序遍历的非递归算法
  *
  *@param BTNode $objRootNode 二叉树根节点
  *@param array $arrBTdata 接收值的数组变量，按引用方式传递
  *@return void
  */
 public function getPreorderTraversalNoRecursion($objRootNode,&$arrBTdata){
  if($objRootNode instanceof BTNode){
   $objNode=$objRootNode;
   $objStack=new StackLinked();
   do{
    $arrBTdata[]=$objNode->mData;
    $objRNode=$objNode->mRchild;
    if($objRNode !=null){
     $objStack->getPushStack($objRNode);
    }
    $objNode=$objNode->mLchild;
    if($objNode==null){
     $objStack->getPopStack($objNode);
    }
   }while($objNode!=null);
  }else{
   $arrBTdata=array();
  }
 }
 /**
  *中序遍历二叉树
  *
  *@param BTNode $objRootNode 过程中的根节点
  *@param array $arrBTdata 接收值的数组变量,按引用方式传递
  *@return void
  */
 public function getInorderTraversal($objRootNode,&$arrBTdata){
  if($objRootNode!=null){
   $this->getInorderTraversal($objRootNode->mLchild,$arrBTdata);
   $arrBTdata[]=$objRootNode->mData;
   $this->getInorderTraversal($objRootNode->mRchild,$arrBTdata);
  }
 }
 /**
  *中序遍历的非递归算法
  *
  *@param BTNode $objRootNode 二叉树根结点
  *@param array $arrBTdata 接收值的数组变量，按引用方式传递
  *@return void
  */
 public function getInorderTraversalNoRecursion($objRootNode,&$arrBTdata){
  if($objRootNode instanceof BTNode){
   $objNode=$objRootNode;
   $objStack=new StackLinked();
   //中序遍历左子树及访问根节点
   do{
    while($objNode!=null){
     $objStack->getPushStack($objNode);
     $objNode=$objNode->mLchild;
    }
    $objStack->getPopStack($objNode);
    $arrBTdata[]=$objNode->mData;
    $objNode=$objNode->mRchild;
   }while(!$objStack->getIsEmpty());
   //中序遍历右子树
   do{
    while($objNode!=null){
     $objStack->getPushStack($objNode);
     $objNode=$objNode->mLchild;
    }
    $objStack->getPopStack($objNode);
    $arrBTdata[]=$objNode->mData;
    $objNode=$objNode->mRchild;
   }while(!$objStack->getIsEmpty());
  }else{
   $arrBTdata=array();
  }
 }
 /**
  *后序遍历二叉树
  *
  *@param BTNode $objRootNode  遍历过程中的根结点
  *@param array $arrBTdata 接收值的数组变量，引用方式传递
  *@return void
  */
 public function getPostorderTraversal($objRootNode,&$arrBTdata){
  if($objRootNode!=null){
   $this->getPostorderTraversal($objRootNode->mLchild,$arrBTdata);
   $this->getPostorderTraversal($objRootNode->mRchild,$arrBTdata);
   $arrBTdata[]=$objRootNode->mData;
  }
 }
 /**
  *后序遍历非递归算法
  *
 BTNode $objRootNode 二叉树根节点
 array $arrBTdata 接收值的数组变量，按引用方式传递
 void
  */
 public function getPostorderTraversalNoRecursion($objRootNode,&$arrBTdata){
  if($objRootNode instanceof BTNode){
   $objNode=$objRootNode;
   $objStack=new StackLinked();
   $objTagStack=new StackLinked();
   $tag=1;
   do{
    while($objNode!=null){
     $objStack->getPushStack($objNode);
     $objTagStack->getPushStack(1);
     $objNode=$objNode->mLchild;
    }
    $objTagStack->getPopStack($tag);
    $objTagStack->getPushStack($tag);
    if($tag == 1){
     $objStack->getPopStack($objNode);
     $objStack->getPushStack($objNode);
     $objNode=$objNode->mRchild;
     $objTagStack->getPopStack($tag);
     $objTagStack->getPushStack(2);

    }else{
     $objStack->getPopStack($objNode);
     $arrBTdata[]=$objNode->mData;
     $objTagStack->getPopStack($tag);
     $objNode=null;
    }
   }while(!$objStack->getIsEmpty());
  }else{
   $arrBTdata=array();
  }
 }
 /**
  *层次遍历二叉树
  *
  *@param BTNode $objRootNode二叉树根节点
  *@param array $arrBTdata 接收值的数组变量，按引用方式传递
  *@return void
  */
 public function getLevelorderTraversal($objRootNode,&$arrBTdata){
  if($objRootNode instanceof BTNode){
   $objNode=$objRootNode;
   $objQueue=new QueueLinked();
   $objQueue->getInsertElem($objNode);
   while(!$objQueue->getIsEmpty()){
    $objQueue->getDeleteElem($objNode);
    $arrBTdata[]=$objNode->mData;
    if($objNode->mLchild != null){
     $objQueue->getInsertElem($objNode->mLchild);
    }
    if($objNode->mRchild != null){
     $objQueue->getInsertElem($objNode->mRchild);
    }
   }
  }else{
   $arrBTdata=array();
  }
 }
 /**
  *求二叉树叶子结点的个数
  *
  *@param BTNode $objRootNode 二叉树根节点
  *@return int 参数传递错误返回-1
  **/
 public function getLeafNodeCount($objRootNode){
  if($objRootNode instanceof BTNode){
   $intLeafNodeCount=0;
   $objNode=$objRootNode;
   $objStack=new StackLinked();
   do{
    if($objNode->mLchild == null && $objNode->mRchild == null){
     $intLeafNodeCount++;
    }
    $objRNode=$objNode->mRchild;
    if($objRNode != null){
     $objStack->getPushStack($objRNode);
    }
    $objNode=$objNode->mLchild;
    if($objNode == null){
     $objStack->getPopStack($objNode);
    }
   }while($objNode != null);
   return $intLeafNodeCount;
  }else{
   return -1;
  }
 }
 /**
  *求二叉树的深度
  *
  *@param BTNode $objRootNode 二叉树根节点
  *@return int 参数传递错误返回-1
  */
 public function getBinaryTreeDepth($objRootNode){
  if($objRootNode instanceof BTNode){
   $objNode=$objRootNode;
   $objQueue=new QueueLinked();
   $intBinaryTreeDepth=0;
   $objQueue->getInsertElem($objNode);
   $objLevel=$objNode;
   while(!$objQueue->getIsEmpty()){
    $objQueue->getDeleteElem($objNode);
    if($objNode->mLchild != null){
     $objQueue->getInsertElem($objNode->mLchild);
    }
    if($objNode->mRchild != null){
     $objQueue->getInsertElem($objNode->mRchild);
    }
    if($objLevel == $objNode){
     $intBinaryTreeDepth++;
     $objLevel=@$objQueue->mRear->mElem;
    }
   }
   return $intBinaryTreeDepth;
  }else{
   return -1;
  }
 }
}
echo "

";

$bt=new BinaryTree(array('A','B','D','','','E','','G','','','C','F','','',''));

echo "二叉树结构：＼r＼n";

var_dump($bt);

$btarr=array();

echo "先序递归遍历二叉树：＼r＼n";

$bt->getPreorderTraversal($bt->mRoot,$btarr);

var_dump($btarr);

echo "先序非递归遍历二叉树：＼r＼n";

$arrBTdata=array();

$bt->getPreorderTraversalNoRecursion($bt->mRoot,$arrBTdata);

var_dump($arrBTdata);

echo "中序递归遍历二叉树：＼r＼n";

$arrBTdata=array();

$bt->getInorderTraversal($bt->mRoot,$arrBTdata);

var_dump($arrBTdata);

echo "中序非递归遍历二叉树：＼r＼n";

$arrBTdata=array();

$bt->getInorderTraversalNoRecursion($bt->mRoot,$arrBTdata);

var_dump($arrBTdata);

echo "后序递归遍历二叉树：＼r＼n";

$arrBTdata=array();

$bt->getPostorderTraversal($bt->mRoot,$arrBTdata);

var_dump($arrBTdata);

echo "后序非递归遍历二叉树:＼r＼n";

$arrBTdata=array();

$bt->getPostorderTraversalNoRecursion($bt->mRoot,$arrBTdata);

var_dump($arrBTdata);

echo "按层次遍历二叉树：＼r＼n";

$arrBTdata=array();

$bt->getLevelorderTraversal($bt->mRoot,$arrBTdata);

var_dump($arrBTdata);

echo "叶子结点的个数为：".$bt->getLeafNodeCount($bt->mRoot);

echo "＼r＼n";

echo "二叉树深度为:".$bt->getBinaryTreeDepth($bt->mRoot);

echo "＼r＼n";

echo "判断二叉树是否为空：";

var_dump($bt->getIsEmpty());

echo "将二叉树置空后：";

$bt->setBinaryTreeNull();

var_dump($bt);

echo "
";
?>

PHP速学教程(入门到精通)
PHP速学教程(入门到精通)

PHP怎么学习？PHP怎么入门？PHP在哪学？PHP怎么学才快？不用担心，这里为大家提供了PHP速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：php抓取google hosts的程序代码 下一篇：php中autoload的实现例子介绍

热门AI工具

更多
DeepSeek
DeepSeek

幻方量化公司旗下的开源大模型平台

AI 编程开发AI 聊天问答
豆包大模型
豆包大模型

字节跳动自主研发的一系列大型语言模型

AI 编程开发AI大模型
通义千问
通义千问

阿里巴巴推出的全能AI助手

AI 编程开发Agent智能体
腾讯元宝
腾讯元宝

腾讯混元平台推出的AI助手

文档处理AI 聊天问答
文心一言
文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI 编程开发AI 文本写作
讯飞写作
讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

AI 文本写作中文写作
即梦AI
即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接
ChatGPT
ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI 编程开发AI 文本写作
智谱清言 - 免费全能的AI助手
智谱清言 - 免费全能的AI助手

智谱清言 - 免费全能的AI助手

AI 编程开发Agent智能体

相关专题

更多
java连接字符串方法汇总
java连接字符串方法汇总

本专题整合了java连接字符串教程合集，阅读专题下面的文章了解更多详细操作。

2

2026.02.05

java中fail含义
java中fail含义

本专题整合了java中fail的含义、作用相关内容，阅读专题下面的文章了解更多详细内容。

5

2026.02.05

控制反转和依赖注入区别
控制反转和依赖注入区别

本专题整合了控制反转和依赖注入区别、解释、实现方法相关内容。阅读专题下面的文章了解更多详细教程。

5

2026.02.05

钉钉脑图插图教程合集
钉钉脑图插图教程合集

本专题整合了钉钉脑图怎么插入图片、钉钉脑图怎么用相关教程，阅读专题下面的文章了解更多详细内容。

7

2026.02.05

python截取字符串方法汇总
python截取字符串方法汇总

本专题整合了python截取字符串方法相关合集，阅读专题下面的文章了解更多详细内容。

2

2026.02.05

Java截取字符串方法合集
Java截取字符串方法合集

本专题整合了Java截取字符串方法汇总，阅读专题下面的文章了解更多详细操作教程。

1

2026.02.05

java 抽象方法
java 抽象方法

本专题整合了java抽象方法定义、作用教程等内容，阅读专题下面的文章了解更多详细内容。

2

2026.02.05

Eclipse创建jsp文件教程合集
Eclipse创建jsp文件教程合集

本专题整合了Eclipse创建jsp文件、创建jsp项目等等内容，阅读专题下面的文章了解更多详细教程。

13

2026.02.05

java 字符串转数字
java 字符串转数字

本专题整合了java如何字符串转数字相关内容，阅读专题下面的文章了解更多详细教程。

3

2026.02.05

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

相关下载

更多
php商城系统
淘源码商城PHP淘宝查信誉
PHP房产程序[BBWPS]
PHP简约自动发卡平台个人版
ERMEB域名PHP离线网络授权系统
Difeye-敏捷的轻量级PHP框架
大泉州汽车网PHP整站程序

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
AngularJS教程
AngularJS教程

共24课时 | 3.4万人学习

CSS3实现按钮特效视频教程
CSS3实现按钮特效视频教程

共15课时 | 3.3万人学习

细说PHP第三季
细说PHP第三季

共58课时 | 11.4万人学习

最新文章

更多
phpmystudy2016版程序包下载-让天下没有难配的php环境
多城市选择器实现代码
微信接口php版本sdk的WxApi.class.php
php图片加水印类，支持文字水印、透明度设置、自定义水印类
php命名空间和动态语言特征
PHP弱类型安全问题总结
如何读懂并写出装逼的函数式代码
用 PHP 爬虫做旅游数据分析
C++从文件中按照单词读取内容
你所不知道的 PHP - 自动加载
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网：公益在线php培训，帮助PHP学习者快速成长！
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号

  • PHP学习

  • 技术支持

  • 返回顶部