[PHP] 使用PHP迭代表示二叉树的查找
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[PHP] 使用PHP迭代表示二叉树的查找，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1474字，纯文字阅读大概需要3分钟。
内容图文
先用一个数组表示一个二叉树搜索树，也就是一个排好序的二叉树，其中左子结点<根结点<右子结点
利用结构数组的形式来表示，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($dataas$k=>$v){
$refer[$v[‘id‘]]=&$data[$k];//为每个数组成员建立对应关系}
//遍历2foreach($dataas$k=>$v){
$left=&$refer[$v[‘left‘]];
$right=&$refer[$v[‘right‘]];
$data[$k][‘left‘]=&$left;
$data[$k][‘right‘]=&$right;
}
//遍历3foreach($dataas$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;
}
}
returnfalse;
}
结果是：
$r=find($tree,2);
Array
(
[id] => 2
[left] => Array
(
[id] => 1
[left] =>
[right] =>
[data] => test3
)
[right] =>
[data] => test1
)
原文：https://www.cnblogs.com/taoshihan/p/12392589.html
内容总结
以上是互联网集市为您收集整理的[PHP] 使用PHP迭代表示二叉树的查找全部内容，希望文章能够帮你解决[PHP] 使用PHP迭代表示二叉树的查找所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】