本文实例讲述了php实现的线索二叉树及二叉树遍历方法。分享给大家供大家参考，具体如下：
<?php require 'bitree.php'; $str = 'ko#be8#tr####acy#####'; $tree = new bitree($str); $tree->createthreadtree(); echo $tree->threadlist() . "\n";从第一个结点开始遍历线索二叉树 echo $tree->threadlistreserv();从最后一个结点开始反向遍历 ?>
bitree.php：
我要评论
<?
/**
* php实现二叉树
*
* @author zhaojiangwei
* @since 2011/10/25 10:32
*/
//结点类
class node{
private $data = null;
private $left = null;
private $right = null;
private $ltag = 0;
private $rtag = 0;
public function node($data = false){
$this->data = $data;
}
//我不喜欢使用魔术方法
public function getdata(){
return $this->data;
}
public function setdata($data){
$this->data = $data;
}
public function getleft(){
return $this->left;
}
public function setleft($left){
$this->left = $left;
}
public function getright(){
return $this->right;
}
public function setright($right){
$this->right = $right;
}
public function getltag(){
return $this->ltag;
}
public function setltag($tag){
$this->ltag = $tag;
}
public function getrtag(){
return $this->rtag;
}
public function setrtag($tag){
$this->rtag = $tag;
}
}
//线索二叉树类
class bitree{
private $datas = null;//要导入的字符串;
private $root = null; //根结点
private $leafcount = 0;//叶子结点个数
private $headnode = null; //线索二叉树的头结点
private $prenode = null;//遍历线索化二叉树时保存前一个遍历的结点
public function bitree($datas){
is_array($datas) || $datas = str_split($datas);
$this->datas = $datas;
$this->backupdata = $this->datas;
$this->createtree(true);
}
//前序遍历创建树
//$root 判断是不是要创建根结点
public function createtree($root = false){
if(emptyempty($this->datas)) return null;
$first = array_shift($this->datas);
if($first == '#'){
return null;
}else{
$node = new node($first);
$root && $this->root = $node;
$node->setleft($this->createtree());
$node->setright($this->createtree());
return $node;
}
}
//返回二叉树叶子结点的个数
public function getleafcount(){
$this->figureleafcount($this->root);
return $this->leafcount;
}
private function figureleafcount($node){
if($node == null)
return false;
if($this->checkempty($node)){
$this->leafcount ++;
}else{
$this->figureleafcount($node->getleft());
$this->figureleafcount($node->getright());
}
}
//判断结点是不是叶子结点
private function checkempty($node){
if($node->getleft() == null && $node->getright() == null){
return true;
}
return false;
}
//返回二叉树深度
public function getdepth(){
return $this->traversdepth($this->root);
}
//遍历求二叉树深度
public function traversdepth($node){
if($node == null){
return 0;
}
$u = $this->traversdepth($node->getleft()) + 1;
$v = $this->traversdepth($node->getright()) + 1;
return $u > $v ? $u : $v;
}
//返回遍历结果,以字符串的形式
//$order 按遍历形式返回,前中后
public function getlist($order = 'front'){
if($this->root == null) return null;
$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;
}
return implode($nodelist);
}
//创建线索二叉树
public function createthreadtree(){
$this->headnode = new node();
$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);
}
//线索化二叉树
private function threadtraverse($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());
}
}
//从第一个结点遍历中序线索二叉树
public function threadlist(){
$arr = array();
for($node = $this->getfirstthreadnode($this->root); $node != $this->headnode; $node = $this->getnextnode($node)){
$arr[] = $node->getdata();
}
return implode($arr);
}
//从尾结点反向遍历中序线索二叉树
public function threadlistreserv(){
$arr = array();
for($node = $this->headnode->getright(); $node != $this->headnode; $node = $this->getprenode($node)){
$arr[] = $node->getdata();
}
return implode($arr);
}
//返回某个结点的前驱
public function getprenode($node){
if($node->getltag() == 1){
return $node->getleft();
}else{
return $this->getlastthreadnode($node->getleft());
}
}
//返回某个结点的后继
public function getnextnode($node){
if($node->getrtag() == 1){
return $node->getright();
}else{
return $this->getfirstthreadnode($node->getright());
}
}
//返回中序线索二叉树的第一个结点
public function getfirstthreadnode($node){
while($node->getltag() == 0){
$node = $node->getleft();
}
return $node;
}
//返回中序线索二叉树的最后一个结点
public function getlastthreadnode($node){
while($node->getrtag() == 0){
$node = $node->getright();
}
return $node;
}
//前序遍历
private function frontlist($node, & $nodelist){
if($node !== null){
$nodelist[] = $node->getdata();
$this->frontlist($node->getleft(), $nodelist);
$this->frontlist($node->getright(), $nodelist);
}
}
//中序遍历
private function middlelist($node, & $nodelist){
if($node != null){
$this->middlelist($node->getleft(), $nodelist);
$nodelist[] = $node->getdata();
$this->middlelist($node->getright(), $nodelist);
}
}
//后序遍历
private function lastlist($node, & $nodelist){
if($node != null){
$this->lastlist($node->getleft(), $nodelist);
$this->lastlist($node->getright(), $nodelist);
$nodelist[] = $node->getdata();
}
}
public function getdata(){
return $this->data;
}
public function getroot(){
return $this->root;
}
}
?>
更多关于php相关内容感兴趣的读者可查看本站专题：《php数据结构与算法教程》、《php运算与运算符用法总结》、《php网络编程技巧总结》、《php基本语法入门教程》、《php操作office文档技巧总结(包括word,excel,access,ppt)》、《php日期与时间用法总结》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》、《php+mysql数据库操作入门教程》及《php常见数据库操作技巧汇总》
希望本文所述对大家php程序设计有所帮助。
如对本文有疑问， 点击进行留言回复！！
[ACTF2020 新生赛]Include 1【文件包含】【读取代码】
算法题解 - 牛客编程巅峰赛S1第6场 - 黄金&钻石&王者组
推荐一个程序员必备网站之一：Dev Hints ，非常实用！
网友评论