本文实例讲述了php无序树实现方法。分享给大家供大家参考。具体如下：
运行效果如下图所示：
php代码如下：
<?php
/*
用php写的无序树
*/
class unorderedtree{
// 节点id计数器
protected $nodeid=0;
// 树的深度
protected $depth=0;
// 树的节点数,
protected $nodescount=0;
// 树的度 @todo: 使其发挥作用
public $degree=" to be implent";
// 根节点id
// 由于树有多种从根节点开始操作，不想每次遍历树到顶找root，用一个变量始终指向根节点
protected $rootid=null;
// 子节点集合, k-v 为 nodeid=>(stdclass)node
// 一些树的实现常常是采用节点和树同一class，这里节点是使用 stdclass{ data, parent, id , childrenids} ，因我认为节点和树应为两种对象，且stdclass要轻于树的class
// 节点格式说明: $this->nodes[nodeid] = new stdclass{ id ,parentid, childrenids, data }
// id: 节点id
// parentid: 节点父节点id
// childrenids: 子节点的id 不想每次遍历树确定层次关系
// 注意: 节点中, #只保存其自身数据和其子节点id的集合#, 子节点的数据通过从树 $tree->nodes[ $node->childrenids[a_child_id] ] 访问
// data: 节点中包含的数据，如节点名称等属性数据
protected $nodes=array();
// 用户自定义访问节点
protected $uservisitfunction=null;
/* 分组: 类的基本函数 */
// @todo: 构造树
public function __construct(){
}
// @todo: 销毁树
public function __destruct(){
unset($this->nodes) ;
}
//------------ 获取数据类函数---------------
// 获取树的深度,
public function gettreedepth(){
return $this->depth;
}
// 获取树的节点数目
public function getcount(){
return $this->nodescount;
}
// 获取树的度
public function getdegree(){
// @todo: 获取树的度（因为对度暂时没什么需要就不实现了 )
return $this->degree;
}
//获取指定节点
public function getnode($nodeid){
if(isset($this->nodes[$nodeid])){
return $this->nodes[$nodeid];
}
else{
return false;
}
}
// 获取最新id
public function getid(){
return $this->nodeid;
}
//获取指定节点高度
public function getnodeheight($nodeid){
if( array_key_exists($nodeid, $this->nodes) ){
// 此节点已在树里，高度至少为1，每找到一个父节点+1
$height=1;
// 记录此树中已经访问过的节点, 用于防止节点构造时互相parent导致此函数死循环且及时结束查找
$visitednodesids=array();
// 记录当前操作节点的id
$cid=$nodeid;
// 当前节点的父节点必须存在于此树中
// 不用递归
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;
}
}
//获取根节点
public function getroot(){
return (!is_null($this->rootid) ) && $this->nodes[$this->rootid];
}
//获取指定节点和其所有子节点构成的数组
//这是用于获取子树的一个关键基础操作
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: 获取由指定节点和其所有子节点构建的子树
public function getsubtree($nodeid){
}
//---------------- 数据更新 -----------------
public function setid($nodeid){
$this->nodeid=$nodeid;
return $this;
}
// 创建不重复的(树中未被使用的) 新id
public function seekid(){
$this->nodeid++;
return $this->nodeid;
}
public function setvisitfunction($userfunction){
$this->uservisitfunction=$userfunction;
}
//插入子节点，默认为插在根节点下
public function insertnode($parent_id=null , $data=null){
//注意node不是class tree
$node = new stdclass;
$node->data = $data;
//树的节点数增加
$this->nodecount++;
// 分配节点id
$this->seekid();
$node->id =$this->getid();
//插入根节点
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) ){
// 插在此树已有节点下
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);
}
// --------------- 数据访问 -----
//广度优先遍历节点的别名, 全名太长了
public function b($nodeid=null){
return $this->breadthtraversal($nodeid);
}
// 广度优先遍历节点
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;
}
//深度优先的别名
public function d($nodeid=null){
return $this->depthtraversall($nodeid);
}
// 深度优先遍历
// 和广度优先的不同实现只在于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;
}
//访问单个节点
public function visit($node){
if(is_null($this->uservisitfunction )){
return $node->id;
}
else{
return call_user_func($this->uservisitfunction,$node,$this);
}
}
}
?>
希望本文所述对大家的php程序设计有所帮助。
【说明】：本文章由站长整理发布，文章内容不代表本站观点，如文中有侵权行为，请与本站客服联系(QQ:)！