PHP實(shí)現(xiàn)的線索二叉樹及二叉樹遍歷方法詳解
更新時(shí)間：2016年04月25日 09:23:23 作者：z32556601
這篇文章主要介紹了PHP實(shí)現(xiàn)的線索二叉樹及二叉樹遍歷方法,結(jié)合實(shí)例形式較為詳細(xì)的分析了線索二叉樹的定義,創(chuàng)建,判斷與遍歷等技巧,需要的朋友可以參考下
本文實(shí)例講述了PHP實(shí)現(xiàn)的線索二叉樹及二叉樹遍歷方法。分享給大家供大家參考，具體如下：
<?php require 'biTree.php'; $str = 'ko#be8#tr####acy#####'; $tree = new BiTree($str); $tree->createThreadTree(); echo $tree->threadList() . "\n";從第一個(gè)結(jié)點(diǎn)開始遍歷線索二叉樹 echo $tree->threadListReserv();從最后一個(gè)結(jié)點(diǎn)開始反向遍歷 ?>
biTree.php：
<?
/**
* PHP實(shí)現(xiàn)二叉樹
*
* @author zhaojiangwei
* @since 2011/10/25 10:32
*/
//結(jié)點(diǎn)類
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;
}
//我不喜歡使用魔術(shù)方法
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;//要導(dǎo)入的字符串;
private $root = NULL; //根結(jié)點(diǎn)
private $leafCount = 0;//葉子結(jié)點(diǎn)個(gè)數(shù)
private $headNode = NULL; //線索二叉樹的頭結(jié)點(diǎn)
private $preNode = NULL;//遍歷線索化二叉樹時(shí)保存前一個(gè)遍歷的結(jié)點(diǎn)
public function BiTree($datas){
is_array($datas) || $datas = str_split($datas);
$this->datas = $datas;
$this->backupData = $this->datas;
$this->createTree(TRUE);
}
//前序遍歷創(chuàng)建樹
//$root 判斷是不是要?jiǎng)?chuàng)建根結(jié)點(diǎn)
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;
}
}
//返回二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)
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());
}
}
//判斷結(jié)點(diǎn)是不是葉子結(jié)點(diǎn)
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;
}
//返回遍歷結(jié)果,以字符串的形式
//$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);
}
//創(chuàng)建線索二叉樹
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());
}
}
//從第一個(gè)結(jié)點(diǎn)遍歷中序線索二叉樹
public function threadList(){
$arr = array();
for($node = $this->getFirstThreadNode($this->root); $node != $this->headNode; $node = $this->getNextNode($node)){
$arr[] = $node->getData();
}
return implode($arr);
}
//從尾結(jié)點(diǎn)反向遍歷中序線索二叉樹
public function threadListReserv(){
$arr = array();
for($node = $this->headNode->getRight(); $node != $this->headNode; $node = $this->getPreNode($node)){
$arr[] = $node->getData();
}
return implode($arr);
}
//返回某個(gè)結(jié)點(diǎn)的前驅(qū)
public function getPreNode($node){
if($node->getLTag() == 1){
return $node->getLeft();
}else{
return $this->getLastThreadNode($node->getLeft());
}
}
//返回某個(gè)結(jié)點(diǎn)的后繼
public function getNextNode($node){
if($node->getRTag() == 1){
return $node->getRight();
}else{
return $this->getFirstThreadNode($node->getRight());
}
}
//返回中序線索二叉樹的第一個(gè)結(jié)點(diǎn)
public function getFirstThreadNode($node){
while($node->getLTag() == 0){
$node = $node->getLeft();
}
return $node;
}
//返回中序線索二叉樹的最后一個(gè)結(jié)點(diǎn)
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;
}
}
?>
更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《PHP運(yùn)算與運(yùn)算符用法總結(jié)》、《PHP網(wǎng)絡(luò)編程技巧總結(jié)》、《PHP基本語法入門教程》、《php操作office文檔技巧總結(jié)(包括word,excel,access,ppt)》、《php日期與時(shí)間用法總結(jié)》、《php面向?qū)ο蟪绦蛟O(shè)計(jì)入門教程》、《php字符串(string)用法總結(jié)》、《php+mysql數(shù)據(jù)庫操作入門教程》及《php常見數(shù)據(jù)庫操作技巧匯總》
希望本文所述對大家PHP程序設(shè)計(jì)有所幫助。
您可能感興趣的文章:
- PHP Class&Object -- PHP 自排序二叉樹的深入解析
- PHP實(shí)現(xiàn)二叉樹的深度優(yōu)先與廣度優(yōu)先遍歷方法
- php實(shí)現(xiàn)的二叉樹遍歷算法示例
- PHP構(gòu)造二叉樹算法示例
- PHP實(shí)現(xiàn)繪制二叉樹圖形顯示功能詳解【包括二叉搜索樹、平衡樹及紅黑樹】
- PHP實(shí)現(xiàn)從上往下打印二叉樹的方法
- PHP基于非遞歸算法實(shí)現(xiàn)先序、中序及后序遍歷二叉樹操作示例
- PHP獲取二叉樹鏡像的方法
- PHP實(shí)現(xiàn)判斷二叉樹是否對稱的方法
- PHP實(shí)現(xiàn)二叉樹深度優(yōu)先遍歷(前序、中序、后序)和廣度優(yōu)先遍歷(層次)實(shí)例詳解
- PHP排序二叉樹基本功能實(shí)現(xiàn)方法示例
相關(guān)文章
PHP中遇到BOM、<feff>編碼導(dǎo)致json_decode函數(shù)無法解析問題
這篇文章主要介紹了PHP中遇到BOM、<feff>編碼導(dǎo)致json_decode函數(shù)無法解析問題,json無法正常解析的同學(xué)可以看一下,是不是看不見的BOM編碼導(dǎo)致的問題,需要的朋友可以參考下2014-07-07
這篇文章主要介紹了PHP文件上傳類,結(jié)合實(shí)例形式詳細(xì)分析了PHP上傳文件類的實(shí)現(xiàn)代碼與相關(guān)使用技巧,需要的朋友可以參考下2016-04-04
php array_walk array_map array_filter區(qū)別案例詳解
這篇文章主要介紹了php array_walk array_map array_filter區(qū)別案例詳解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-09-09
這篇文章主要介紹了PHP使用SOAP調(diào)用API操作,結(jié)合實(shí)例形式分析了php基于SOAP調(diào)用API的常見操作技巧及相關(guān)問題解決方法,需要的朋友可以參考下2018-12-12
這篇文章主要介紹了php如何實(shí)現(xiàn)只替換一次或只替換N次，通過一個(gè)簡單的例子引入主題，感性的朋友可以參考一下2015-10-10
iis6手工創(chuàng)建網(wǎng)站后無法運(yùn)行php腳本的解決方法
下面小編就為大家?guī)硪黄猧is6手工創(chuàng)建網(wǎng)站后無法運(yùn)行php腳本的解決方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-06-06
PHP中經(jīng)緯度坐標(biāo)相關(guān)計(jì)算方法小結(jié)
這篇文章主要為大家詳細(xì)介紹了PHP中經(jīng)緯度坐標(biāo)相關(guān)計(jì)算方法的相關(guān)知識,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-04-04
這篇文章主要介紹了PHP偽協(xié)議，php中有很多封裝協(xié)議，最常見的如file協(xié)議，php協(xié)議，data協(xié)議，zip和phar協(xié)議等等2022-11-11
這篇文章主要為大家詳細(xì)介紹了php微信開發(fā)自定義菜單，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-08-08
數(shù)組是最基本的數(shù)據(jù)結(jié)構(gòu)，關(guān)于數(shù)組的操作是程序員最經(jīng)常用到的。這里將一些常用的操作寫成函數(shù)。2011-07-07