先用一个数组表示一个二叉树搜索树，也就是一个排好序的二叉树，其中左子结点<根结点<右子结点
利用结构数组的形式来表示，id , left , right 代表结点id ，左子树 ，右子树
下面这个二维数组
$data[]=['id'=>8,'left'=>2,'right'=>10,'data'=>'test'];
$data[]=['id'=>2,'left'=>1,'right'=>0,'data'=>'test1'];
$data[]=['id'=>10,'left'=>0,'right'=>0,'data'=>'test2'];
$data[]=['id'=>1,'left'=>0,'right'=>0,'data'=>'test3'];
转换成成多维的树结构
$root=8;
$tree=[];
//遍历
foreach($data as $k=>$v){
$refer[$v['id']]=&$data[$k];//为每个数组成员建立对应关系
}
//遍历2
foreach($data as $k=>$v){
$left=&$refer[$v['left']];
$right=&$refer[$v['right']];
$data[$k]['left']=&$left;
$data[$k]['right']=&$right;
}
//遍历3
foreach($data as $k=>$v){
if($v['id']==$root){
$tree=$v;
break;
}
}
结果是：
Array
(
[id] => 8
[left] => Array
(
[id] => 2
[left] => Array
(
[id] => 1
[left] =>
[right] =>
[data] => test3
)
[right] =>
[data] => test1
)
[right] => Array
(
[id] => 10
[left] =>
[right] =>
[data] => test2
)
[data] => test
)
使用迭代的方式来查找，如果值比当前结点小，就把左子树赋给当前树 ，如果大就把右子树赋给当前树
function find($tree,$id){
while(is_array($tree)){
if($id<$tree['id']){
$tree=$tree['left'];
}elseif($id>$tree['id']){
$tree=$tree['right'];
}else{
return $tree;
}
}
return false;
}
结果是：
$r=find($tree,2);
Array
(
[id] => 2
[left] => Array
(
[id] => 1
[left] =>
[right] =>
[data] => test3
)
[right] =>
[data] => test1
)
相关文章
发表评论