用php实现无序树

原创
2013/05/10 16:24
阅读数 670

近期琢磨着用php实现数据结构里的一些“树”,于是用php先写了个各类树中最简单的无序树,实现了插入节点,深度遍历,广度遍历,获取树的深度等操作。 暂未实现获取树的度,删除节点等操作。 这是无序树,所以prev,next之类排序有关的不在其中实现,以后在有序树里实现那些。

一些感想:

  1. 对“树”的主要应用领域而言,php天生就可能不是很适合。或者是因为已经太容易获取那些实现给php调用,所以其实没什么一般应用需用php去实现个树出来。php的数组天生就能够凑合当树用,所以很多框架也就直接用数组做树做的事情。所以,会不会用php写树其实不重要。前阵子看这里有个帖里面很多朋友挺纠结会不会用php写二叉树之类来着。
  2. 我的数据结构是04年左右大学学的,当时用pascal实现。时隔多年后我发现用php写很大不一样:
  • php的数组非常好用,可以看到这里很多操作用数组十分方便。特别广度优先和深度优先实现上的区别只是array_merge的参数顺序调整。。当年用C和Pascal的数组感觉很不便。
  • 为了快速清晰地定位节点,我给节点用id标示,但请注意这里id只是简单的++分配唯一id。对实际应用而言,此机制需要较大修改。
  • 节点的访问,php可以自定义函数,然后call_user_func,或者继承后重写visit方法。以节点存储数据和关系,再用不同函数去visit。这可以很灵活地将数据结构与应用逻辑分开。
  • 用php做演示效果,只是简单的几句php+html+css,快速轻松愉快,效果比当年用pascal控制台打印字符爽多。但不够华丽,下次弄点html5啥的。

    其实我在琢磨,怎样用几种树来做个web框架,欢迎讨论。有序树对实现快速查找,路由映射,流程控制,文件组织很有用。

demo图:

代码如下(类+demo),大量中文注释哦,希望对大家有帮助。


<?php
/* 
用php写的无序树
@author: mx  (http://my.oschina.net/meikaiyuan)
@version: 2013-05-10 v2.00
 */

 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);
		}
	 }
	 

 }


?>


demo:


<style>
div{
	margin: 4px 0 0 5px;
	padding: 5px;
	border: 1px solid #66f;
	font-size: 12px;
	
	text-align: left;
	float:left;
	clear: both;
}
</style>

<?php
require "../unorderedTreeV2.min.php";

$uTree=new unorderedTree(array());
//获取根id	
$rootid=$uTree->insertNode()->getId();
//在根下插入n个节点
$uTree->insertNode()->insertNode()->insertNode()->insertNode();
//获取最新插入节点id
$nid_x=$uTree->getId();
//在此节点下继续插
$uTree->insertNode($nid_x)->insertNode($nid_x)->insertNode();
// 在指定的节点下插(可以稍后从输出div看这些id的节点后面是否有相应数量的div)
$nid_x=2;
$uTree->insertNode($nid_x)->insertNode($nid_x)->insertNode($nid_x) ;
$nid_x=7;
$uTree->insertNode($nid_x);
$nid_x=11;
$uTree->insertNode($nid_x);
$nid_x=13;
$uTree->insertNode($nid_x);
$uTree->insertNode($nid_x);

//结合css,产生不同高度的节点不同缩进效果
function show($node,$tree){
	$marginleft= 20* ($tree->getNodeHeight($node->id))  ;
	echo '<div style="margin-left: '.$marginleft.'px">'. $node->id ."</div>";
}

// 指定用show来遍历节点
$uTree->setVisitFunction('show');

// 深度优先遍历
echo '<div style="width:100%;"><hr>深度优先遍历<hr></div>';
$uTree->d(1);  

echo '<div style="width:100%;"><hr>广度优先遍历<hr></div>';

$uTree->setVisitFunction('show');
// 广度优先遍历
$uTree->b(1); 

//获取一下某节点与其下所有子节点,(参照深度优先遍历看看)
echo '<div style="width:100%;"><hr>获取节点和子节点集合<hr></div>';
$nodeId=5;
echo "<div>$nodeId 与其子节点id集合为: ", print_r($uTree->getSubNodes($nodeId),true ),"</div>";


echo '<div style="width:100%;"><hr>换种id玩玩<hr></div>';

$charTree=new unorderedTree();
// 改用字符来做id,注意这类id不好太多
$charTree->setId('a');
$charTree->setVisitFunction('show');
//获取根id	
$rootid=$charTree->insertNode()->getId();
//在根下插入n个节点
$charTree->insertNode()->insertNode()->insertNode()->insertNode();
// 随便再插几个
$charTree->insertNode('c')->insertNode('d');
// 看看效果
$charTree->d();
 
 
?>



展开阅读全文
打赏
1
3 收藏
分享
加载中
谢谢指教,非常不错
2020/02/29 10:56
回复
举报
梅开源博主

引用来自“lazyphp”的评论

话说。。这是做啥的。36

这方面研究因为后来我没大段闲暇时间就暂时搁浅了。关于做啥, 上面已经解释过很多了,第五点是关键。
2013/12/09 16:42
回复
举报
话说。。这是做啥的。36
2013/12/09 16:35
回复
举报
梅开源博主

引用来自“haigou20”的评论

php实现其他数据结构,又如何呢?能有些什么实际的应用

由于php的array的便利,实现其他数据结构也会十分便利。就实际应用而言,由于php常被只用在网站开发,而网站往往是狂写if-else也ok,所以通常的web开发不容易看到有明显的生产力提升。其他方面,基于数据结构的php程序用来演示数据结构教学,实现工作流等不错。此外推荐lessphp等带“树的操作”的源码。
2013/07/10 11:04
回复
举报
php实现其他数据结构,又如何呢?能有些什么实际的应用
2013/07/10 09:51
回复
举报
梅开源博主

引用来自“李马燕”的评论

您好,两个问题请教:
1 这个无序树能用来干嘛?
2 能不能推荐本适合菜鸟的数据结构和算法的书,关于php的

感谢回复。
1. 暂时没什么实际用途,有序树我会试着做点有趣的例子。我做此无序树有很多方面原因,一是练习php,二是看看用php做数据结构是否便利,三是有感于php在数据结构方面的资料太少,四是人们普遍认为php是草根语言,希望通过自己贡献让人们有所改观,五最重要。 无序树是一个尝试的开始。 这个尝试简单而言,是“以树+php语言为基础的应用编程思路”。树”这种结构,其实与php编程领域时常契合。例如可应用于无限分类,DOM,路由,数据库查询,全文索引,工作流中。关于那些常用树的领域,如果可以用操控树的方法,操作同构的这些领域,会很方便。再不妨设想下,假设存在这么一个框架,用户访问一个URL,实际是走完一个树的一个分支,中间每个关键流程是树的一个节点。由于树的多种抽象数据结构特性,使得开发一个应用天然地自顶向下,无限扩展,节点可复用,易于观测定位跟踪数据,易于调整顺序……

2. php的数据结构的书目前尚未见到,谷歌php 数据结构有些资料,但不细致。
http://www.brpreiss.com/books/opus11/ 里的php版的有点太C++、java风格。
个人受益较多的几本和数据结构有关的是严蔚敏的pascal版的《数据结构》,《像计算机科学家一样思考java》,《C++ primer》,《游戏编程中的人工智能》。





2013/05/16 10:13
回复
举报
您好,两个问题请教:
1 这个无序树能用来干嘛?
2 能不能推荐本适合菜鸟的数据结构和算法的书,关于php的
2013/05/15 22:34
回复
举报
更多评论
打赏
7 评论
3 收藏
1
分享
返回顶部
顶部