打印

PHP源码：树操作类

本主题由 admin 于 2007-11-4 12:02 移动

dmlk31

高级会员

Rank: 4

1^# 大中小发表于 2007-9-25 13:52 只看该作者

PHP源码：树操作类

http://www.phpweblog.net/dmlk31/articles/2013.html

<?php
/**//*******************************************
*
* 作者: 外来物种

* 时间: 2007-9-25

* 修改: 2007-9-25
*
*******************************************/

class Tree{
/**//**
* 树型数据,经过排序的记录集
*/
var $mRsTree = array();

/**//**
 * id字段名父id的字段名根id的值
 */
var $mFdId = null;
var $mFdFId = null;
var $mRId = null;

/**//**
 *
 * 构造函数
 *
 */
function Tree($rsTree,$fdId = "id",$fdFId = "pid",$rootId = 0)
{
 $this->mFdId = $fdId;
 $this->mFdFId = $fdFId;
 $this->mRId = $rootId;

 $this->mRsTree = $this->AddLevelInfo($rsTree);
}

/**//**
 *
 * 取得到某一节点的路径
 *
 */
public function GetTrackNodes($id,$level = 1)
{
 $hash_tree_id = array();
 $tracks = array();

 //以记录ID号为索引
 $hash_tree_id = $this->GetHashOneToOne($this->mRsTree,$this->mFdId);

 do{
 $tracks[] = $hash_tree_id[$id];
 $id = $hash_tree_id[$id][ $this->mFdFId ];
 }while( isset($hash_tree_id[$id]) && $id != $this->mRId && $hash_tree_id[$id]['level'] >= $level);

 return array_reverse($tracks);
}

/**//**
 *
 * 取得某层的所有节点
 *
 */
public function GetLevelNodes($level)
{
 $ret_nodes = array();

 foreach($this->mRsTree AS $i=>$r){
 if( $r['level'] == $level )
 $ret_nodes[] = $r;
 }

 return $ret_nodes;
}

/**//**
 *
 * 取得某个节点的叶子节点
 *
 */
public function GetLeafNodes($id)
{
 $ind = null;
 $id_level = null;
 $ret_nodes = array();

 //获得当前记录在数组中的索引号
 for($i=0; $i < count($this->mRsTree); $i++){
 if( $this->mRsTree[$i][$this->mFdId] == $id ){
 $id_level = $this->mRsTree[$i]['level'];
 $ind = $i;
 break;
 }
 }

 //无子孩子
 if( !isset($this->mRsTree[$ind+1]) || $this->mRsTree[$ind+1]['level'] == $id_level ){
 $ret_nodes[] = $this->mRsTree[$ind];
 return $ret_nodes;
 }

 $ind++;

 while(isset($this->mRsTree[$ind]) && $this->mRsTree[$ind]['level'] != $id_level){
 if( !isset($this->mRsTree[$ind+1]) || $this->mRsTree[$ind]['level'] >= $this->mRsTree[$ind+1]['level'] ){
 $ret_nodes[] = $this->mRsTree[$ind];
 }

 $ind++;
 }

 return $ret_nodes;
}

/**//**
 *
 * 取得某个节点的子孩子
 *
 */
public function GetChildNodes($id)
{
 $ind = 0;
 $id_level = 0;
 $ret_nodes = array();

 $rs_cnt = count($this->mRsTree);

 //获得 id=$id 记录在数组中的索引号和层次
 for($i=0; $i < $rs_cnt; $i++){
 if( $this->mRsTree[$i][$this->mFdId] == $id ){
 $id_level = $this->mRsTree[$i]['level'];
 $ind = $i;
 break;
 }
 }

 for($i=$ind+1; $i < $rs_cnt; $i++){
 if( $this->mRsTree[$i]['level'] <= $id_level )
 break;

 $ret_nodes[] = $this->mRsTree[$i];
 }

 return $ret_nodes;
}

/**//**
 *
 * 取得某个节点的子孩子
 *
 */
public function GetParentNodes($id)
{
 $ind = 0;
 $id_fid = 0;

 $rs_cnt = count($this->mRsTree);

 //获得 id=$id 记录在数组中的索引号和层次
 for($i=0; $i < $rs_cnt; $i++){
 if( $this->mRsTree[$i][$this->mFdId] == $id ){
 $id_fid = $this->mRsTree[$i][ $this->mFdFId ];
 $ind = $i;
 break;
 }
 }

 for($i=$ind; $i >= 0; $i--){
 if( $this->mRsTree[$i][$this->mFdId] == $id_fid )
 return $this->mRsTree[$i];
 }
}

/**//**
 *
 * 增加层次信息
 *
 */
private function AddLevelInfo($rsTree)
{
 //树型排序
 $rsTree = $this->SortToTreeRs($rsTree);

 //增加 level 信息
 $levels = array();

 foreach($rsTree AS $i => $r){
 if($r[ $this->mFdFId ] == $this->mRId){
 $rsTree[$i]['level'] = 1;
 $levels[ $r[ $this->mFdId ] ] = $rsTree[$i]['level'];
 }
 else{
 $rsTree[$i]['level'] = $levels[ $r[ $this->mFdFId ] ] + 1;
 $levels[ $r[ $this->mFdId ] ] = $rsTree[$i]['level'];
 }
 }

 return $rsTree;
}

/**//**
 *
 * 将树型记录集按树型排序
 *
 * array("id"=>4,"fid"=>2) array("id"=>4,"fid"=>0)
 * array("id"=>4,"fid"=>0) => array("id"=>2,"fid"=>4)
 * array("id"=>2,"fid"=>4) array("id"=>5,"fid"=>2)
 *
 */
private function SortToTreeRs($rsTree)
{
 $rs_cnt = count($rsTree);

 for($i=0; $i < $rs_cnt; $i++){
 $float_ind = $i;
 $cur_fid = $rsTree[$i][$this->mFdFId];

 //上浮索引
 while($float_ind > 0 && $cur_fid != $rsTree[$float_ind-1][$this->mFdId]){
 $float_ind--;
 }

 //浮动终止，替换内容
 if($float_ind != $i){
 array_splice( $rsTree,$float_ind,0,array_splice($rsTree,$i,1) );
 }
 }

 return $rsTree;
}

/**//**
*
* 取得哈希数组
*
*/
private function GetHashOneToOne($rsTree, $key)
{
 $ret_hash = array();

 foreach($rsTree AS $i=>$r){
 $ret_hash[ $r[$key] ] = $r;
 }

 return $ret_hash;
}
}

$rsTree = array(
array("id"=>3,"fid"=>6,"title"=>"节点3"),
array("id"=>7,"fid"=>0,"title"=>"节点7"),
array("id"=>22,"fid"=>7,"title"=>"节点22"),
array("id"=>1,"fid"=>7,"title"=>"节点1"),
array("id"=>6,"fid"=>22,"title"=>"节点6"),
array("id"=>8,"fid"=>7,"title"=>"节点8"),
array("id"=>13,"fid"=>8,"title"=>"节点13"),
array("id"=>17,"fid"=>22,"title"=>"节点17"),
array("id"=>2,"fid"=>13,"title"=>"节点2"),
array("id"=>24,"fid"=>13,"title"=>"节点24"),
array("id"=>19,"fid"=>13,"title"=>"节点19"),
array("id"=>56,"fid"=>13,"title"=>"节点56"),
);

$oTree = new Tree($rsTree,"id","fid");
//my_print_line($oTree->GetTrackNodes(56,0) );
//my_print_line($oTree->GetLeafNodes(7));
//my_print_line($oTree->GetLevelNodes(4));
//my_print_line($oTree->GetChildNodes(22) );
//my_print_line($oTree->GetParentNodes(22) );
//my_print_line($oTree->GetChildNodes(13) );
?>

<?php
function my_print_line($rs,$level=1)
{
if( !is_array($rs) )
 return $rs;

$str = "array(";
if($level == 1) $str .= " ";

foreach($rs AS $i=>$r){
 $str .= " [{$i}]=>".my_print_line($r,$level+1);
}

if($level == 1) $str .= " ";
$str .= ") ";

if($level > 1) return $str;

echo "<pre>{$str}</pre>";
}
?>

[ 本帖最后由 dmlk31 于 2007-9-25 14:13 编辑 ]