search

Home >php教程 >PHP源码 >php 二叉树遍历算法与例子

php 二叉树遍历算法与例子

WBOY
WBOYOriginal
2016-06-08 17:20:431677browse

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

<script>ec(2);</script>

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

tupan062.gif

 

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

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

    中序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则从根节点开始，中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树，遍历顺序为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);

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 "

";<br>
$bt=new BinaryTree(array('A','B','D','','','E','','G','','','C','F','','',''));<br>
echo "二叉树结构：＼r＼n";<br>
var_dump($bt);<br>
$btarr=array();<br>
echo "先序递归遍历二叉树：＼r＼n";<br>
$bt->getPreorderTraversal($bt->mRoot,$btarr);<br>
var_dump($btarr);<br>
echo "先序非递归遍历二叉树：＼r＼n";<br>
$arrBTdata=array();<br>
$bt->getPreorderTraversalNoRecursion($bt->mRoot,$arrBTdata);<br>
var_dump($arrBTdata);<br>
echo "中序递归遍历二叉树：＼r＼n";<br>
$arrBTdata=array();<br>
$bt->getInorderTraversal($bt->mRoot,$arrBTdata);<br>
var_dump($arrBTdata);<br>
echo "中序非递归遍历二叉树：＼r＼n";<br>
$arrBTdata=array();<br>
$bt->getInorderTraversalNoRecursion($bt->mRoot,$arrBTdata);<br>
var_dump($arrBTdata);<br>
echo "后序递归遍历二叉树：＼r＼n";<br>
$arrBTdata=array();<br>
$bt->getPostorderTraversal($bt->mRoot,$arrBTdata);<br>
var_dump($arrBTdata);<br>
echo "后序非递归遍历二叉树:＼r＼n";<br>
$arrBTdata=array();<br>
$bt->getPostorderTraversalNoRecursion($bt->mRoot,$arrBTdata);<br>
var_dump($arrBTdata);<br>
echo "按层次遍历二叉树：＼r＼n";<br>
$arrBTdata=array();<br>
$bt->getLevelorderTraversal($bt->mRoot,$arrBTdata);<br>
var_dump($arrBTdata);<br>
echo "叶子结点的个数为：".$bt->getLeafNodeCount($bt->mRoot);<br>
echo "＼r＼n";<br>
echo "二叉树深度为:".$bt->getBinaryTreeDepth($bt->mRoot);<br>
echo "＼r＼n";<br>
echo "判断二叉树是否为空：";<br>
var_dump($bt->getIsEmpty());<br>
echo "将二叉树置空后：";<br>
$bt->setBinaryTreeNull();<br>
var_dump($bt);<br>
echo "
";
?>
Statement：
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Previous article：php抓取google hosts的程序代码Next article：php中autoload的实现例子介绍

Related articles

See more