php 二叉树遍历算法与例子-PHP源码-php.cn

집

php教程

PHP源码

php 二叉树遍历算法与例子

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 08, 2016 pm 05:20 PM

gtnbsp

二叉树算法在小编大学时学数据结构时会学到的一个算法了，这个可以在搜索与排序中提高50%的搜索性能了，下面我们来看一些关于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(),

);

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

//前序遍历二叉树算法

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 "

";
?>

성명

본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

뜨거운 도구

VSCode Windows 64비트 다운로드

Microsoft에서 출시한 강력한 무료 IDE 편집기

맨티스BT

Mantis는 제품 결함 추적을 돕기 위해 설계된 배포하기 쉬운 웹 기반 결함 추적 도구입니다. PHP, MySQL 및 웹 서버가 필요합니다. 데모 및 호스팅 서비스를 확인해 보세요.

ZendStudio 13.5.1 맥

강력한 PHP 통합 개발 환경

Dreamweaver Mac版

시각적 웹 개발 도구

MinGW - Windows용 미니멀리스트 GNU

이 프로젝트는 osdn.net/projects/mingw로 마이그레이션되는 중입니다. 계속해서 그곳에서 우리를 팔로우할 수 있습니다. MinGW: GCC(GNU Compiler Collection)의 기본 Windows 포트로, 기본 Windows 애플리케이션을 구축하기 위한 무료 배포 가능 가져오기 라이브러리 및 헤더 파일로 C99 기능을 지원하는 MSVC 런타임에 대한 확장이 포함되어 있습니다. 모든 MinGW 소프트웨어는 64비트 Windows 플랫폼에서 실행될 수 있습니다.