近期琢磨着用php实现数据结构里的一些“树”，于是用php先写了个各类树中最简单的无序树，实现了插入节点，深度遍历，广度遍历，获取树的深度等操作。 暂未实现获取树的度，删除节点等操作。 这是无序树，所以prev，next之类排序有关的不在其中实现，以后在有序树里实现那些。
一些感想：
- 对“树”的主要应用领域而言，php天生就可能不是很适合。或者是因为已经太容易获取那些实现给php调用，所以其实没什么一般应用需用php去实现个树出来。php的数组天生就能够凑合当树用，所以很多框架也就直接用数组做树做的事情。所以，会不会用php写树其实不重要。前阵子看这里有个帖里面很多朋友挺纠结会不会用php写二叉树之类来着。
- 我的数据结构是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();
?>
