[PHP] 使用PHP迭代表示二叉树的查找
2023-02-18 15:41:37 时间
先用一个数组表示一个二叉树搜索树,也就是一个排好序的二叉树,其中左子结点<根结点<右子结点
利用结构数组的形式来表示,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 )
相关文章
- Redis实现朋友圈,微博等Feed流功能,实现Feed流微服务(业务场景、实现思路和环境搭建)
- 马上都2023了,但是CNS级别单细胞文章仍然是使用monocle2
- 使用Mosquitto实现MQTT客服端C语言
- mosquitto移植到ARM
- mosquitto的安装与使用
- QT下载与安装
- 虚拟基站(VRS)
- liunx驱动之字符设备的注册
- 湃兔更新镜像文件的制作与烧写
- 通过busybox制作根文件系统详细过程
- 内核与设备树的编译和烧写
- UBoot的编译与烧写
- Nextcloud 使用教程
- uboot通过NFS挂载ubuntu根文件系统
- 如何在博客园编写博文章
- [NetWork] 数据封装与解封装流程
- 深度学习-LeNet(第一个卷积神经网络)
- Java跨域-Redirect的跨域问题解决
- 十年前,AlexNet就预定了今天的NeurIPS 2022时间检验奖
- 无需新型token mixer就能SOTA:MetaFormer视觉基线模型开源,刷新ImageNet记录