PHP实现的线索二叉树及二叉树遍历方法详解
本文实例讲述了PHP实现的线索二叉树及二叉树遍历方法。分享给大家供大家参考，具体如下：
<?php require'biTree.php'; $str='ko#be8#tr####acy#####'; $tree=newBiTree($str); $tree->createThreadTree(); echo$tree->threadList()."\n";从第一个结点开始遍历线索二叉树 echo$tree->threadListReserv();从最后一个结点开始反向遍历 ?>
biTree.php：
<?
/**
*PHP实现二叉树
*
*@authorzhaojiangwei
*@since2011/10/2510:32
*/
//结点类
classNode{
private$data=NULL;
private$left=NULL;
private$right=NULL;
private$lTag=0;
private$rTag=0;
publicfunctionNode($data=false){
$this->data=$data;
}
//我不喜欢使用魔术方法
publicfunctiongetData(){
return$this->data;
}
publicfunctionsetData($data){
$this->data=$data;
}
publicfunctiongetLeft(){
return$this->left;
}
publicfunctionsetLeft($left){
$this->left=$left;
}
publicfunctiongetRight(){
return$this->right;
}
publicfunctionsetRight($right){
$this->right=$right;
}
publicfunctiongetLTag(){
return$this->lTag;
}
publicfunctionsetLTag($tag){
$this->lTag=$tag;
}
publicfunctiongetRTag(){
return$this->rTag;
}
publicfunctionsetRTag($tag){
$this->rTag=$tag;
}
}
//线索二叉树类
classBiTree{
private$datas=NULL;//要导入的字符串;
private$root=NULL;//根结点
private$leafCount=0;//叶子结点个数
private$headNode=NULL;//线索二叉树的头结点
private$preNode=NULL;//遍历线索化二叉树时保存前一个遍历的结点
publicfunctionBiTree($datas){
is_array($datas)||$datas=str_split($datas);
$this->datas=$datas;
$this->backupData=$this->datas;
$this->createTree(TRUE);
}
//前序遍历创建树
//$root判断是不是要创建根结点
publicfunctioncreateTree($root=FALSE){
if(emptyempty($this->datas))returnNULL;
$first=array_shift($this->datas);
if($first=='#'){
returnNULL;
}else{
$node=newNode($first);
$root&&$this->root=$node;
$node->setLeft($this->createTree());
$node->setRight($this->createTree());
return$node;
}
}
//返回二叉树叶子结点的个数
publicfunctiongetLeafCount(){
$this->figureLeafCount($this->root);
return$this->leafCount;
}
privatefunctionfigureLeafCount($node){
if($node==NULL)
returnfalse;
if($this->checkEmpty($node)){
$this->leafCount++;
}else{
$this->figureLeafCount($node->getLeft());
$this->figureLeafCount($node->getRight());
}
}
//判断结点是不是叶子结点
privatefunctioncheckEmpty($node){
if($node->getLeft()==NULL&&$node->getRight()==NULL){
returntrue;
}
returnfalse;
}
//返回二叉树深度
publicfunctiongetDepth(){
return$this->traversDepth($this->root);
}
//遍历求二叉树深度
publicfunctiontraversDepth($node){
if($node==NULL){
return0;
}
$u=$this->traversDepth($node->getLeft())+1;
$v=$this->traversDepth($node->getRight())+1;
return$u>$v?$u:$v;
}
//返回遍历结果,以字符串的形式
//$order按遍历形式返回,前中后
publicfunctiongetList($order='front'){
if($this->root==NULL)returnNULL;
$nodeList=array();
switch($order){
case"front":
$this->frontList($this->root,$nodeList);
break;
case"middle":
$this->middleList($this->root,$nodeList);
break;
case"last":
$this->lastList($this->root,$nodeList);
break;
default:
$this->frontList($this->root,$nodeList);
break;
}
returnimplode($nodeList);
}
//创建线索二叉树
publicfunctioncreateThreadTree(){
$this->headNode=newNode();
$this->preNode=&$this->headNode;
$this->headNode->setLTag(0);
$this->headNode->setLeft($this->root);
$this->headNode->setRTag(1);
$this->threadTraverse($this->root);
$this->preNode->setRight($this->headNode);
$this->preNode->setRTag(1);
$this->headNode->setRight($this->preNode);
}
//线索化二叉树
privatefunctionthreadTraverse($node){
if($node!=NULL){
if($node->getLeft()==NULL){
$node->setLTag(1);
$node->setLeft($this->preNode);
}else{
$this->threadTraverse($node->getLeft());
}
if($this->preNode!=$this->headNode&&$this->preNode->getRight()==NULL){
$this->preNode->setRTag(1);
$this->preNode->setRight($node);
}
$this->preNode=&$node;//注意传引用
$this->threadTraverse($node->getRight());
}
}
//从第一个结点遍历中序线索二叉树
publicfunctionthreadList(){
$arr=array();
for($node=$this->getFirstThreadNode($this->root);$node!=$this->headNode;$node=$this->getNextNode($node)){
$arr[]=$node->getData();
}
returnimplode($arr);
}
//从尾结点反向遍历中序线索二叉树
publicfunctionthreadListReserv(){
$arr=array();
for($node=$this->headNode->getRight();$node!=$this->headNode;$node=$this->getPreNode($node)){
$arr[]=$node->getData();
}
returnimplode($arr);
}
//返回某个结点的前驱
publicfunctiongetPreNode($node){
if($node->getLTag()==1){
return$node->getLeft();
}else{
return$this->getLastThreadNode($node->getLeft());
}
}
//返回某个结点的后继
publicfunctiongetNextNode($node){
if($node->getRTag()==1){
return$node->getRight();
}else{
return$this->getFirstThreadNode($node->getRight());
}
}
//返回中序线索二叉树的第一个结点
publicfunctiongetFirstThreadNode($node){
while($node->getLTag()==0){
$node=$node->getLeft();
}
return$node;
}
//返回中序线索二叉树的最后一个结点
publicfunctiongetLastThreadNode($node){
while($node->getRTag()==0){
$node=$node->getRight();
}
return$node;
}
//前序遍历
privatefunctionfrontList($node,&$nodeList){
if($node!==NULL){
$nodeList[]=$node->getData();
$this->frontList($node->getLeft(),$nodeList);
$this->frontList($node->getRight(),$nodeList);
}
}
//中序遍历
privatefunctionmiddleList($node,&$nodeList){
if($node!=NULL){
$this->middleList($node->getLeft(),$nodeList);
$nodeList[]=$node->getData();
$this->middleList($node->getRight(),$nodeList);
}
}
//后序遍历
privatefunctionlastList($node,&$nodeList){
if($node!=NULL){
$this->lastList($node->getLeft(),$nodeList);
$this->lastList($node->getRight(),$nodeList);
$nodeList[]=$node->getData();
}
}
publicfunctiongetData(){
return$this->data;
}
publicfunctiongetRoot(){
return$this->root;
}
}
?>
更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《PHP运算与运算符用法总结》、《PHP网络编程技巧总结》、《PHP基本语法入门教程》、《php操作office文档技巧总结(包括word,excel,access,ppt)》、《php日期与时间用法总结》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》、《php+mysql数据库操作入门教程》及《php常见数据库操作技巧汇总》
希望本文所述对大家PHP程序设计有所帮助。