[PHP] 使用PHP迭代表示二叉树的查找
2023-02-18 15:41:18 时间
先用一个数组表示一个二叉树搜索树,也就是一个排好序的二叉树,其中左子结点<根结点<右子结点
利用结构数组的形式来表示,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 )
相关文章
- React报错之Rendered more hooks than during the previous render
- 如何使用CSS伪类选择器
- React报错之Property 'value' does not exist on type EventTarget
- React报错之Parameter 'event' implicitly has an 'any' type
- React报错之Parameter 'props' implicitly has an 'any' type
- React报错之Property 'value' does not exist on type 'HTMLElement'
- React报错之You provided a `checked` prop to a form field
- React报错之Invalid hook call
- React报错之React hook 'useState' cannot be called in a class component
- React报错之React Hook 'useEffect' is called in function
- React报错之React hook 'useState' is called conditionally
- 如何在CSS中使用变量
- React报错之React Hook useEffect has a missing dependency
- React报错之Expected an assignment or function call and instead saw an expression
- React报错之Unexpected default export of anonymous function
- React报错之Expected `onClick` listener to be a function
- React报错之Cannot find namespace context
- React报错之Functions are not valid as a React child
- React报错之Encountered two children with the same key
- React报错之Cannot assign to 'current' because it is a read-only property