php 二叉树遍历算法与例子

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

 

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

    前序遍历二叉树：如果二叉树为空则返回，若二叉树非空，则先遍历左树，再遍历右树，遍历顺序为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 "

";

$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 "

";
?>