php 二叉树遍历算法与例子
二叉树算法在小编大学时学数据结构时会学到的一个算法了,这个可以在搜索与排序中提高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(),
),
),
),
'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 "
?>

핫 AI 도구

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

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

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

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

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

뜨거운 주제











로그인 화면에 "귀하의 조직에서 PIN 변경을 요구합니다"라는 메시지가 나타납니다. 이는 개인 장치를 제어할 수 있는 조직 기반 계정 설정을 사용하는 컴퓨터에서 PIN 만료 제한에 도달한 경우 발생합니다. 그러나 개인 계정을 사용하여 Windows를 설정하는 경우 이상적으로는 오류 메시지가 나타나지 않습니다. 항상 그런 것은 아니지만. 오류가 발생한 대부분의 사용자는 개인 계정을 사용하여 신고합니다. 조직에서 Windows 11에서 PIN을 변경하도록 요청하는 이유는 무엇입니까? 귀하의 계정이 조직과 연결되어 있을 수 있으므로 이를 확인하는 것이 기본 접근 방식입니다. 도메인 관리자에게 문의하면 도움이 될 수 있습니다! 또한 잘못 구성된 로컬 정책 설정이나 잘못된 레지스트리 키로 인해 오류가 발생할 수 있습니다. 지금 바로

Windows 11은 신선하고 우아한 디자인을 전면에 내세웠습니다. 현대적인 인터페이스를 통해 창 테두리와 같은 미세한 세부 사항을 개인화하고 변경할 수 있습니다. 이 가이드에서는 Windows 운영 체제에서 자신의 스타일을 반영하는 환경을 만드는 데 도움이 되는 단계별 지침을 설명합니다. 창 테두리 설정을 변경하는 방법은 무엇입니까? +를 눌러 설정 앱을 엽니다. Windows개인 설정으로 이동하여 색상 설정을 클릭합니다. 색상 변경 창 테두리 설정 창 11" Width="643" Height="500" > 제목 표시줄 및 창 테두리에 강조 색상 표시 옵션을 찾아 옆에 있는 스위치를 토글합니다. 시작 메뉴 및 작업 표시줄에 강조 색상을 표시하려면 시작 메뉴와 작업 표시줄에 테마 색상을 표시하려면 시작 메뉴와 작업 표시줄에 테마 표시를 켭니다.

기본적으로 Windows 11의 제목 표시줄 색상은 선택한 어두운/밝은 테마에 따라 다릅니다. 그러나 원하는 색상으로 변경할 수 있습니다. 이 가이드에서는 이를 변경하고 데스크톱 환경을 개인화하여 시각적으로 매력적으로 만드는 세 가지 방법에 대한 단계별 지침을 논의합니다. 활성 창과 비활성 창의 제목 표시줄 색상을 변경할 수 있습니까? 예, 설정 앱을 사용하여 활성 창의 제목 표시줄 색상을 변경하거나 레지스트리 편집기를 사용하여 비활성 창의 제목 표시줄 색상을 변경할 수 있습니다. 이러한 단계를 알아보려면 다음 섹션으로 이동하세요. Windows 11에서 제목 표시줄 색상을 변경하는 방법은 무엇입니까? 1. 설정 앱을 사용하여 +를 눌러 설정 창을 엽니다. Windows"개인 설정"으로 이동한 다음

Windows Installer 페이지에 "OOBELANGUAGE" 문과 함께 "문제가 발생했습니다."가 표시됩니까? 이러한 오류로 인해 Windows 설치가 중단되는 경우가 있습니다. OOBE는 즉시 사용 가능한 경험을 의미합니다. 오류 메시지에서 알 수 있듯이 이는 OOBE 언어 선택과 관련된 문제입니다. 걱정할 필요가 없습니다. OOBE 화면 자체에서 레지스트리를 편집하면 이 문제를 해결할 수 있습니다. 빠른 수정 – 1. OOBE 앱 하단에 있는 “다시 시도” 버튼을 클릭하세요. 그러면 더 이상의 문제 없이 프로세스가 계속됩니다. 2. 전원 버튼을 사용하여 시스템을 강제 종료합니다. 시스템이 다시 시작된 후 OOBE가 계속되어야 합니다. 3. 인터넷에서 시스템 연결을 끊습니다. 오프라인 모드에서 OOBE의 모든 측면을 완료하세요.

작업 표시줄 축소판은 재미있을 수도 있지만 주의를 산만하게 하거나 짜증나게 할 수도 있습니다. 이 영역 위로 얼마나 자주 마우스를 가져가는지 고려하면 실수로 중요한 창을 몇 번 닫았을 수도 있습니다. 또 다른 단점은 더 많은 시스템 리소스를 사용한다는 것입니다. 따라서 리소스 효율성을 높일 수 있는 방법을 찾고 있다면 비활성화하는 방법을 알려드리겠습니다. 그러나 하드웨어 사양이 이를 처리할 수 있고 미리 보기가 마음에 들면 활성화할 수 있습니다. Windows 11에서 작업 표시줄 축소판 미리 보기를 활성화하는 방법은 무엇입니까? 1. 설정 앱을 사용하여 키를 탭하고 설정을 클릭합니다. Windows에서는 시스템을 클릭하고 정보를 선택합니다. 고급 시스템 설정을 클릭합니다. 고급 탭으로 이동하여 성능 아래에서 설정을 선택합니다. "시각 효과"를 선택하세요.

많은 사용자들이 스마트 시계를 선택할 때 Huawei 브랜드를 선택하게 됩니다. 그 중 Huawei GT3pro와 GT4가 가장 인기 있는 선택입니다. 두 제품의 차이점을 궁금해하는 사용자가 많습니다. Huawei GT3pro와 GT4의 차이점은 무엇입니까? 1. 외관 GT4: 46mm와 41mm, 재질은 유리 거울 + 스테인레스 스틸 본체 + 고해상도 섬유 후면 쉘입니다. GT3pro: 46.6mm 및 42.9mm, 재질은 사파이어 유리 + 티타늄 본체/세라믹 본체 + 세라믹 백 쉘입니다. 2. 건강한 GT4: 최신 Huawei Truseen5.5+ 알고리즘을 사용하면 결과가 더 정확해집니다. GT3pro: ECG 심전도, 혈관 및 안전성 추가

Windows 11의 디스플레이 크기 조정과 관련하여 우리 모두는 서로 다른 선호도를 가지고 있습니다. 큰 아이콘을 좋아하는 사람도 있고, 작은 아이콘을 좋아하는 사람도 있습니다. 그러나 올바른 크기 조정이 중요하다는 점에는 모두가 동의합니다. 잘못된 글꼴 크기 조정이나 이미지의 과도한 크기 조정은 작업 시 생산성을 저하시킬 수 있으므로 시스템 기능을 최대한 활용하려면 이를 사용자 정의하는 방법을 알아야 합니다. Custom Zoom의 장점: 화면의 텍스트를 읽기 어려운 사람들에게 유용한 기능입니다. 한 번에 화면에서 더 많은 것을 볼 수 있도록 도와줍니다. 특정 모니터 및 응용 프로그램에만 적용되는 사용자 정의 확장 프로필을 생성할 수 있습니다. 저사양 하드웨어의 성능을 향상시키는 데 도움이 될 수 있습니다. 이를 통해 화면의 내용을 더 효과적으로 제어할 수 있습니다. 윈도우 11을 사용하는 방법

화면 밝기는 최신 컴퓨팅 장치를 사용할 때 필수적인 부분이며, 특히 화면을 장시간 볼 때 더욱 그렇습니다. 눈의 피로를 줄이고, 가독성을 높이며, 콘텐츠를 쉽고 효율적으로 보는 데 도움이 됩니다. 그러나 설정에 따라 밝기 관리가 어려울 수 있으며, 특히 새로운 UI 변경이 적용된 Windows 11에서는 더욱 그렇습니다. 밝기를 조정하는 데 문제가 있는 경우 Windows 11에서 밝기를 관리하는 모든 방법은 다음과 같습니다. Windows 11에서 밝기를 변경하는 방법 [10가지 설명] 단일 모니터 사용자는 다음 방법을 사용하여 Windows 11에서 밝기를 조정할 수 있습니다. 여기에는 단일 모니터를 사용하는 데스크탑 시스템과 노트북이 포함됩니다. 시작하자. 방법 1: 알림 센터 사용 알림 센터에 액세스할 수 있습니다.
