php無序樹實現(xiàn)方法
更新時間：2015年07月28日 11:28:39 作者：梅開源
這篇文章主要介紹了php無序樹實現(xiàn)方法,實例分析了php無序樹的實現(xiàn)技巧,具有一定參考借鑒價值,需要的朋友可以參考下
本文實例講述了php無序樹實現(xiàn)方法。分享給大家供大家參考。具體如下：
運行效果如下圖所示：
php代碼如下：
<?php
/*
用php寫的無序樹
*/
class unorderedTree{
// 節(jié)點id計數(shù)器
protected $nodeId=0;
// 樹的深度
protected $depth=0;
// 樹的節(jié)點數(shù),
protected $nodesCount=0;
// 樹的度 @todo: 使其發(fā)揮作用
public $degree=" to be implent";
// 根節(jié)點id
// 由于樹有多種從根節(jié)點開始操作，不想每次遍歷樹到頂找root，用一個變量始終指向根節(jié)點
protected $rootid=null;
// 子節(jié)點集合, k-v 為 nodeid=>(stdclass)node
// 一些樹的實現(xiàn)常常是采用節(jié)點和樹同一class，這里節(jié)點是使用 stdclass{ data, parent, id , childrenIds} ，因我認為節(jié)點和樹應(yīng)為兩種對象，且stdclass要輕于樹的class
// 節(jié)點格式說明: $this->nodes[nodeId] = new stdclass{ id ,parentId, childrenIds, data }
// id: 節(jié)點id
// parentId: 節(jié)點父節(jié)點id
// childrenIds: 子節(jié)點的id 不想每次遍歷樹確定層次關(guān)系
// 注意: 節(jié)點中, #只保存其自身數(shù)據(jù)和其子節(jié)點id的集合#, 子節(jié)點的數(shù)據(jù)通過從樹 $tree->nodes[ $node->childrenIds[a_child_id] ] 訪問
// data: 節(jié)點中包含的數(shù)據(jù)，如節(jié)點名稱等屬性數(shù)據(jù)
protected $nodes=array();
// 用戶自定義訪問節(jié)點
protected $userVisitFunction=null;
/* 分組: 類的基本函數(shù) */
// @todo: 構(gòu)造樹
public function __construct(){
}
// @todo: 銷毀樹
public function __destruct(){
unset($this->nodes) ;
}
//------------ 獲取數(shù)據(jù)類函數(shù)---------------
// 獲取樹的深度,
public function getTreeDepth(){
return $this->depth;
}
// 獲取樹的節(jié)點數(shù)目
public function getCount(){
return $this->NodesCount;
}
// 獲取樹的度
public function getDegree(){
// @todo: 獲取樹的度（因為對度暫時沒什么需要就不實現(xiàn)了 )
return $this->degree;
}
//獲取指定節(jié)點
public function getNode($nodeId){
if(isset($this->Nodes[$nodeId])){
return $this->Nodes[$nodeId];
}
else{
return false;
}
}
// 獲取最新id
public function getId(){
return $this->nodeId;
}
//獲取指定節(jié)點高度
public function getNodeHeight($nodeId){
if( array_key_exists($nodeId, $this->nodes) ){
// 此節(jié)點已在樹里，高度至少為1，每找到一個父節(jié)點+1
$height=1;
// 記錄此樹中已經(jīng)訪問過的節(jié)點, 用于防止節(jié)點構(gòu)造時互相parent導(dǎo)致此函數(shù)死循環(huán)且及時結(jié)束查找
$visitedNodesIds=array();
// 記錄當前操作節(jié)點的id
$cid=$nodeId;
// 當前節(jié)點的父節(jié)點必須存在于此樹中
// 不用遞歸
while( isset($cid) ) {
if( !in_array($cid,$visitedNodesIds ) ){
if( $this->rootid===$cid){ //到頂,返回
return $height;
}
$visitedNodesIds[]=$cid;
$cid= $this->nodes[ $cid ]->parentId;
$height++;
}
else{
return false;
}
}
return false;
}
else{
return false;
}
}
//獲取根節(jié)點
public function getRoot(){
return (!is_null($this->rootid) ) && $this->nodes[$this->rootid];
}
//獲取指定節(jié)點和其所有子節(jié)點構(gòu)成的數(shù)組
//這是用于獲取子樹的一個關(guān)鍵基礎(chǔ)操作
public function getSubNodes($nodeId){
if(isset($this->nodes[$nodeId])){
$result=array();
$toVisitNodeIds=array();
$toVisitedNodeIds[]=$nodeId;
$result[]=$this->nodes[$nodeId]->id;
array_shift($toVisitedNodeIds);
$toVisitedNodeIds=array_merge( $toVisitedNodeIds, $this->nodes[$nodeId]->childrenIds);
while(!empty($toVisitedNodeIds)){
$toVisitNodeId=array_shift($toVisitedNodeIds);
$result[]=$this->nodes[$toVisitNodeId]->id;
$toVisitedNodeIds=array_merge( $toVisitedNodeIds, $this->nodes[$toVisitNodeId]->childrenIds);
}
return $result ;
}
else{
return false;
}
}
//@todo: 獲取由指定節(jié)點和其所有子節(jié)點構(gòu)建的子樹
public function getSubTree($nodeid){
}
//---------------- 數(shù)據(jù)更新 -----------------
public function setId($nodeId){
$this->nodeId=$nodeId;
return $this;
}
// 創(chuàng)建不重復(fù)的(樹中未被使用的) 新id
public function seekId(){
$this->nodeId++;
return $this->nodeId;
}
public function setVisitFunction($userFunction){
$this->userVisitFunction=$userFunction;
}
//插入子節(jié)點，默認為插在根節(jié)點下
public function insertNode($parent_id=null , $data=null){
//注意node不是class tree
$node = new stdclass;
$node->data = $data;
//樹的節(jié)點數(shù)增加
$this->nodeCount++;
// 分配節(jié)點id
$this->seekId();
$node->id =$this->getId();
//插入根節(jié)點
if( (is_null($parent_id)) && is_null($this->rootid)){
$node->parentId = null;
$node->childrenIds = array();
$this->depth=1;
$this->rootid=$node->id;
$this->nodes [$node->id]=$node;
return $this;
}
elseif( isset($this->nodes[$parent_id]) || is_null($parent_id) ){
// 插在此樹已有節(jié)點下
if(is_null($parent_id)){
$parent_id=$this->rootid;
}
$node->parentId = $parent_id;
$node->childrenIds = array();
//更新樹的最大深度
$depth=$this->getNodeHeight($parent_id);
$this->depth=max($depth+1, $this->depth);
$this->nodes[$parent_id]->childrenIds []= $node->id;
$this->nodes [$node->id]=$node;
return $this;
}
else{
return $this;
}
}
//insert node 的別名
public function append($parent_id=null , $data=null){
return $this->insertNode($parent_id,$data);
}
// --------------- 數(shù)據(jù)訪問 -----
//廣度優(yōu)先遍歷節(jié)點的別名, 全名太長了
public function b($nodeId=null){
return $this->breadthTraversal($nodeId);
}
// 廣度優(yōu)先遍歷節(jié)點
public function breadthTraversal($nodeId=null){
if(is_null($this->rootid)){
die("此樹為空樹，不可訪問");
}
else{
//全部遍歷
if(is_null($nodeId) || ( $this->rootid===$nodeId) ){
$nodeId=$this->rootid;
}
$toVisitNodeIds=array();
$toVisitedNodeIds[]=$nodeId;
$this->visit( $this->nodes[$nodeId]);
array_shift($toVisitedNodeIds);
$toVisitedNodeIds=array_merge( $toVisitedNodeIds, $this->nodes[$nodeId]->childrenIds);
while(!empty($toVisitedNodeIds)){
$toVisitNodeId=array_shift($toVisitedNodeIds);
$this->visit( $this->nodes[$toVisitNodeId]);
$toVisitedNodeIds=array_merge( $toVisitedNodeIds, $this->nodes[$toVisitNodeId]->childrenIds);
}
}
return $this;
}
//深度優(yōu)先的別名
public function d($nodeId=null){
return $this->depthTraversall($nodeId);
}
// 深度優(yōu)先遍歷
// 和廣度優(yōu)先的不同實現(xiàn)只在于array_merge的順序不同而已 ( php array 忒好用啊忒好用 )
public function depthTraversall($nodeId=null){
if(is_null($this->rootid)){
die("此樹為空樹，不可訪問");
}
else{
//全部遍歷
if(is_null($nodeId)){
$nodeId=$this->rootid;
}
$toVisitNodeIds=array();
$toVisitedNodeIds[]=$nodeId;
$this->visit( $this->nodes[$nodeId]);
array_shift($toVisitedNodeIds);
$toVisitedNodeIds=array_merge( $this->nodes[$nodeId]->childrenIds, $toVisitedNodeIds );
while(!empty($toVisitedNodeIds)){
$toVisitNodeId=array_shift($toVisitedNodeIds);
$this->visit( $this->nodes[$toVisitNodeId]);
$toVisitedNodeIds=array_merge( $this->nodes[$toVisitNodeId]->childrenIds, $toVisitedNodeIds );
}
}
return $this;
}
//訪問單個節(jié)點
public function visit($node){
if(is_null($this->userVisitFunction )){
return $node->id;
}
else{
return call_user_func($this->userVisitFunction,$node,$this);
}
}
}
?>
希望本文所述對大家的php程序設(shè)計有所幫助。
相關(guān)文章
以前沒學(xué)過PHP,最近剛好一個項目需要用到,我就決定一邊學(xué)一邊做PHP2012-08-08
這篇文章主要介紹了PHP+MySQL實現(xiàn)無極限分類欄目的方法,涉及php操作數(shù)據(jù)庫查詢及結(jié)果集遞歸遍歷的技巧,需要的朋友可以參考下2015-12-12
PHP自4.3版本開始,捆綁了自己的GD2庫,用戶可以自己下載并設(shè)置.如果要查看自己的php版本是否支持gd模塊(支持JPEG,PNG,WBMP但不再支持GIF)2009-06-06
php關(guān)鍵字僅替換一次的實現(xiàn)函數(shù)
這篇文章主要介紹了php實現(xiàn)每個關(guān)鍵字僅需要替換一次，有時一個項目里面涉及到批量替換關(guān)鍵字的問題，本文針對控制替換次數(shù)進行研究，感興趣的小伙伴們可以參考一下2015-10-10
這篇文章主要介紹了PHP實現(xiàn)求解最長公共子串問題的方法,簡單描述了求解最長公共子串問題算法原理,并結(jié)合實例形式分析了PHP實現(xiàn)求解最長公共子串的具體操作技巧,需要的朋友可以參考下2017-11-11
關(guān)于使用key/value數(shù)據(jù)庫redis和TTSERVER的心得體會
本篇文章是對使用key/value數(shù)據(jù)庫redis和TTSERVER的心得體會進行了詳細的分析介紹，需要的朋友參考下2013-06-06
這篇文章主要介紹了PHP生成網(wǎng)站桌面快捷方式代碼分享,代碼很簡單,復(fù)制改一下域名即可使用,需要的朋友可以參考下2014-10-10
讓php處理圖片變得簡單 基于gb庫的圖片處理類附實例代碼下載
讓php處理圖片變得簡單 基于gb庫的圖片處理類附實例代碼下載，需要的朋友可以參考下。2011-05-05
開啟了url_alter后，將實現(xiàn)兩個HOOK，hook_url_inbound_alter與hook_url_outbound_alter，作用是重寫URL，第三方URL重寫模塊都需要實現(xiàn)它。2011-05-05
是對一個接收自由提交表單數(shù)據(jù)的文件進行安全性分析，希望對各位有幫助。首先說明一下，代碼中的error（）和succeed（）是我自定義的函數(shù)2008-07-07