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 (empty($node)) {
return;
}
//输出值
print_r($node['data']);
//左节点
PreOrderTraverse($node['lChild']);
//右节点
PreOrderTraverse($node['rChild']);
}遍历算法二：中序遍历二叉树
<?php
//中序遍历二叉树算法
echo '中序遍历二叉树算法：';
inOrderTraverse($arr);
echo '<Br>';
function inOrderTraverse($node) {
if (empty($node)) {
return;
}
//左节点
inOrderTraverse($node['lChild']);
//输出值
print_r($node['data']);
//右节点
inOrderTraverse($node['rChild']);
}遍历算法三：后序遍历二叉树
<?php
//后序遍历二叉树算法
echo '后序遍历二叉树算法：';
postOrderTraverse($arr);
echo '<Br>';
function postOrderTraverse($node) {
if (empty($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/code/78085.html
转载随意！带上文章地址吧。