PHP实现的线索二叉树及二叉树遍历方法详解
作者:z32556601 发布时间:2023-11-13 11:28:06
标签:PHP,二叉树
本文实例讲述了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程序设计有所帮助。
0
投稿
猜你喜欢
- 为了应用方便,您可能需要给数据库的每条记录都添加日期/时间戳,以便确定各个记录添加到数据库的时间。在Access数据库应用中,使用Now()
- 有的同学会说,可以使用源代码搜索的办法。的确,对于一个相对简单的页面,这个方法时常奏效。但是,对于构成相对复杂的页面(比如页面嵌入很多脚本文
- 在计算机普及的现代设计领域,文字的设计的工作很大一部分由计算机代替人脑完成了(很多平面设计软件中都有制作艺术汉字的引导,以及提供了数十上百种
- 回顾面向对象编程让我们先用 30 秒钟来回顾一下 OOP 到底是什么。在面向对象编程语言中,可以定义 类,它们的用途是将相关的数据和行为捆绑
- 本文主要介绍 SQLServerExpress2008不用第三方工具调试T-SQL语句,经过本文的介绍,用SQLSERVER2008 Man
- 想要asp能连接mysql数据库需要安装MySQL ODBC 3.51 驱动 http://www.jb51.net/softs/19910
- 背景:pony是公司的首席体验官、首席产品经理。这次在产品峰会上pony将自己平时经验的积累与大家交流,体验较细。这次分享研发管理部,设计中
- MySQL中模式就是数据库SHOW DATABASES;show databases;罗列所有数据库名称CREATE DATABASE &l
- 在对跨多个表格的数据进行组合时,有时很难搞清楚要使用哪一个SQL句法。我将在这里对将多个表格中的查询合并至单一声明中的常用方式进行阐述。在这
- 使用SQL SERVER的[导入]功能,便可将access数据转换,但要注意原来的'自增字段'需要修改,将相应字段标识修改为
- 将进程挂起(Suspend) 而非 阻塞(Block)如果用sleep() 进程将阻塞假设进程下有两个线程 那么这两个线程会继续运行要使进程
- 用途:将UTF-8编码汉字转换为GB2312码,兼容英文和数字版权:虽说是原创,其实也参考了別人的部分算法asp源代码:<% 
- asp读取access数据库表名称的代码:<%strConn="DBQ="+server.mappath(&quo
- import time# time模块中包含了许多与时间相关的模块,其中通过time()函数可以获取当前的时间。count = 100pri
- 有几个原因促使我们使用自定义的select控件来代替原生的select控件:在ie6下select是一个窗口级的元素,绝对定位的层会被sel
- 最近正在做首页,处理很棘手的浏览器兼容的问题,主要调试的浏览器为 IE6 ,IE7 ,FF3 ,Opera9.5 ,Safari3.1.2兼
- 引文: 长期以来,多媒体信息在计算机中都是以文件形式存放,由操作系统管理的,但是随着计算机网络,分布式计算的发展,对多媒体信息进行高效的管理
- 本文实例讲述了PHP实现的XXTEA加密解密算法。分享给大家供大家参考,具体如下:<?php/** * Xxtea 加密实现类 */c
- 前言刚接触golang不久,有些环境无法融会贯通,现在针对开发过程中遇到的问题做个排查记录问题背景开发环境区分不同网段,同一个程序引入到另一
- 首先说明一下SQL Server内存占用由哪几部分组成。SQL Server占用的内存主要由三部分组成:数据缓存(Data Buffer)、