php 二叉树遍历算法与例子
二叉树算法在小编大学时学数据结构时会学到的一个算法了,这个可以在搜索与排序中提高50%的搜索性能了,下面我们来看一些关于php 二叉树遍历算法与例子吧.
二叉树遍历,是值从根节点出发,按照某种次序依次访问二叉树中的所有节点,使得每个节点被访问一次且仅被访问.
前序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则先遍历左树，再遍历右树，遍历顺序为ABCDEGF。
中序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从根节点开始，中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树，遍历顺序为CBEGDFA。
后序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从左到右先叶子后节点的访问遍历访问左右子树，最后是访问根节点。访问顺序为CGEFDBA。
层序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按照从左到右的顺序对节点逐个访问。访问顺序为ABCDEFG。
现在,我们用PHP代码,来遍历二叉树结构,二叉树是放一个大数组,每一个节点都有三个字段,data表示这个节点的值,lChild表示这个节点的左边子节点,rChild表示这个节点的右边子节点.
二叉树结构代码如下:
<?php //二叉树 $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(), );
遍历算法一:前序遍历二叉树
<?php
//前序遍历二叉树算法
echo '前序遍历二叉树算法：';
PreOrderTraverse($arr);
echo '<Br>';
function PreOrderTraverse($node){
if(emptyempty($node)){
return;
}
//输出值
print_r($node['data']);
//左节点
PreOrderTraverse($node['lChild']);
//右节点
PreOrderTraverse($node['rChild']);
}
遍历算法二:中序遍历二叉树
<?php
//中序遍历二叉树算法
echo '中序遍历二叉树算法：';
inOrderTraverse($arr);
echo '<Br>';
function inOrderTraverse($node){
if(emptyempty($node)){
return;
}
//左节点
inOrderTraverse($node['lChild']);
//输出值
print_r($node['data']);
//右节点
inOrderTraverse($node['rChild']);
}
遍历算法三:后序遍历二叉树
<?php
//后序遍历二叉树算法
echo '后序遍历二叉树算法：';
postOrderTraverse($arr);
echo '<Br>';
function postOrderTraverse($node){
if(emptyempty($node)){
return;
}
//左节点
postOrderTraverse($node['lChild']);
//右节点
postOrderTraverse($node['rChild']);
//输出值
print_r($node['data']);
}
例子:
<?php
/**
*二叉树的创建及基本操作
*
*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 "<pre>";
$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 "</pre>";
本文地址：http://www.phprm.com/develop/fs9054.html
转载随意，但请附上文章地址:-)