[PHP] 使用PHP迭代表示二叉树的查找
先用一个数组表示一个二叉树搜索树,也就是一个排好序的二叉树,其中左子结点<根结点<右子结点
利用结构数组的形式来表示,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 )