这篇文章主要介绍了php无序树实现方法,实例分析了php无序树的实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
本文实例讲述了php无序树实现方法。分享给大家供大家参考。具体如下：
运行效果如下图所示：
php代码如下：
(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程序设计有所帮助。