<?php class Node{ var $data; //数据 var $left; //左孩子 var $right; //右孩子 //前序遍历 public function preTraverse(){ echo "$this->data<br>"; if($this->left != NULL) $this->left->middleTraverse(); if($this->right != NULL){ $this->right->middleTraverse(); } }
public function Node($data,$left,$right){ $this->data = $data; $this->left = $left; $this->right = $right; }
} $D=new Node("D",NULL,NULL); $E = new Node("E",NULL,NULL); $B = new Node("B",$D,$E);$I=new Node("I",NULL,NULL); $J = new Node("J",NULL,NULL); $C = new Node("C",$I,$J);$A = new Node("A",$B,$C);$K=new Node("K",NULL,NULL); $L = new Node("L",NULL,NULL); $G = new Node("G",$K,$L);$M=new Node("M",NULL,NULL); $N = new Node("JN",NULL,NULL); $H = new Node("H",$M,$N);$E = new Node("E",$G,$H);$PP = new Node("PP",$A,$E);$PP->middleTraverse();?>
class Node{
var $data; //数据
var $left; //左孩子
var $right; //右孩子
//前序遍历
public function preTraverse(){
echo "$this->data<br>";
if($this->left != NULL)
$this->left->middleTraverse();
if($this->right != NULL){
$this->right->middleTraverse();
}
}
public function Node($data,$left,$right){
$this->data = $data;
$this->left = $left;
$this->right = $right;
}
}
$D=new Node("D",NULL,NULL);
$E = new Node("E",NULL,NULL);
$B = new Node("B",$D,$E);$I=new Node("I",NULL,NULL);
$J = new Node("J",NULL,NULL);
$C = new Node("C",$I,$J);$A = new Node("A",$B,$C);$K=new Node("K",NULL,NULL);
$L = new Node("L",NULL,NULL);
$G = new Node("G",$K,$L);$M=new Node("M",NULL,NULL);
$N = new Node("JN",NULL,NULL);
$H = new Node("H",$M,$N);$E = new Node("E",$G,$H);$PP = new Node("PP",$A,$E);$PP->middleTraverse();?>
AAAA
-1层BBBB
--2层NNNN
--2层MMMM
-1层CCCC
--2层GGGG
---3层HHHH
----4层JJJJ
实现时
如果访问不频繁,则可使用“邻接表算法”
如果访问频繁,则可使用“前序遍历”算法
这都有稳定健壮的php代码,搜索一下就有了
源代码:调用代码:
$tmpArray = array(array('id'=>1, 'name'=>'aaa', 'pid'=>0),
array('id'=>2, 'name'=>'aaa1', 'pid'=>1),
array('id'=>3, 'name'=>'bbb', 'pid'=>0),
array('id'=>4, 'name'=>'bbb1', 'pid'=>3),
array('id'=>5, 'name'=>'aaa1_1_1', 'pid'=>6),
array('id'=>6, 'name'=>'aaa1_1', 'pid'=>2),
array('id'=>7, 'name'=>'aaa1_1_2', 'pid'=>6),
array('id'=>8, 'name'=>'bbb2', 'pid'=>3),
array('id'=>9, 'name'=>'aaa1_1_3', 'pid'=>6),
array('id'=>10, 'name'=>'ccc', 'pid'=>0),
array('id'=>11, 'name'=>'ccc1', 'pid'=>10),
array('id'=>12, 'name'=>'ccc2', 'pid'=>10),
array('id'=>13, 'name'=>'ccc3', 'pid'=>10),
array('id'=>14, 'name'=>'ccc2_1', 'pid'=>12),
array('id'=>15, 'name'=>'ccc2_2', 'pid'=>12),
);
$keyId=0;
$categoryClass = new GggCatagory($tmpArray,"id","name","pid");
$categoryClass->SetParentKey(0); //设置代表根类的key
$categoryClass->getCategoryChildrens($keyId,' - ',$category_array);
foreach ($category_array as $key => $value)
{
print($key.":");
print($value);
print("<br>");
}
结果
1: - aaa
2: - - aaa1
6: - - - aaa1_1
5: - - - - aaa1_1_1
7: - - - - aaa1_1_2
9: - - - - aaa1_1_3
3: - bbb
4: - - bbb1
8: - - bbb2
10: - ccc
11: - - ccc1
12: - - ccc2
14: - - - ccc2_1
15: - - - ccc2_2
13: - - ccc3
源代码
<?
if(!defined("CLASS_GggCatagory"))
{
define("CLASS_GggCatagory","1");
class GggCatagory
{
var $mParentArray= array(); //根据 key 得到 parent
var $mValueArray= array(); //根据 key 得到 Value
var $mKeyArray= array(); //根据 序号 得到 key
var $mChildrenArray= array(); //根据 parent 来得到 key,这时对应的key有可能会是多条,用二维数组来保存(相当于得到下一级的功能)
//该二维数组保存 最后生成的树 按从树根到枝叶排序
var $mTreeArray=array(); // $mTreeArray['key'][0] ,$mTreeArray['value'][0] ...
//调用时传替过来的数组下标
var $mKey;
var $mValue;
var $mParent;
var $mparentKey=0; //根节点的值 默认 parent 为0表示该节点为根节点
var $indent=' - '; //缩进 的符号
function GggCatagory($tmpData,$tmpKey="key",$tmpValue="value",$tmpParent="parent")
{
foreach($tmpData as $key => $value)
{
$this->mKeyArray[$key]=$value[$tmpKey];
$this->mParentArray[$value[$tmpKey]]=$value[$tmpParent]; //得到上一级id
$this->mValueArray[$value[$tmpKey]]=$value[$tmpValue];
$this->mChildrenArray[$value[$tmpParent]][]=$key; //根据 pid 来得到 key 相当于得到下一级的功能
//print($value[$tmpParent]);
//print("?");
}
$this->mKey=$tmpKey;
$this->mValue=$tmpValue;
$this->mParent=$tmpParent;
}//END GggCatagory
//************************* 设置根节点的值 默认 parent 为0表示该节点为根节点 *************************
function SetParentKey($keyId)
{
$this->mparentKey=$keyId;
}//END Set_ParentKey
//************************* 当前节点下面是否还有子节点 *************************
function HasChildren($keyId)
{
return count($this->mChildrenArray[$keyId])<1?false:true;
}//END HasChildren
//************************* 查看当前节点是不是根节点 *************************
function isRootParent($keyId)
{
return $this->mParentArray[$keyId]==$this->mparentKey;
}//END isRootParent
function GetNode($keyId)
{
if(!in_array($keyId,$this->mKeyArray)) //如果当前节点不存在直接返回
return;
unset($tmpTreeArray);
$tmpTreeArray[$this->mKey][]=$keyId;
$tmpTreeArray[$this->mValue][]=$this->mValueArray[$keyId];
$tmpTreeArray[$this->mParent][]=$this->mParentArray[$keyId];
return $tmpTreeArray;
}//END GetNode
function GetParent($keyId)
{
if($this->isRootParent($keyId)) //本身是根类了
return;
return $this->GetNode($this->mParentArray[$keyId]);
}//END GetParent
function GetChildren($keyId)
{
if(!$this->HasChildren($keyId))
return;
$currKey=$keyId;
$tmpTreeArray=array();
$keyIdArray=$this->mChildrenArray[$currKey]; //得到当前类下的子类
if(is_array($keyIdArray)) //表示类下有子类
{
foreach($keyIdArray as $key => $value)
{
$currKey=$this->mKeyArray[$value];
$tmpTreeArray[$this->mKey][]=$currKey;
$tmpTreeArray[$this->mValue][]=$this->mValueArray[$currKey];
$tmpTreeArray[$this->mParent][]=$this->mParentArray[$currKey];
}
}
//print($tmpTreeArray[0][$this->mKey]);
return $tmpTreeArray;
}//END GetChildren
function getCategoryChildrens($parent_key, $indent='', &$category_array)
{
$tmpData=$this->GetChildren($parent_key);
$len_i=count($tmpData[$this->mKey]);
for($tmp_i=0;$tmp_i<$len_i;$tmp_i++)
{
$category_array[$tmpData[$this->mKey][$tmp_i]] = $indent.$tmpData[$this->mValue][$tmp_i];
$this->getCategoryChildrens($tmpData[$this->mKey][$tmp_i],$indent.' - ',$category_array);
}
} //end getCategoryChildrens
}//END class GggCatagory
}