首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[PHP] 使用PHP迭代表示二叉树的查找

[PHP] 使用PHP迭代表示二叉树的查找

作者头像
唯一Chat
发布2020-03-19 14:30:21
4130
发布2020-03-19 14:30:21
举报
文章被收录于专栏:陶士涵的菜地陶士涵的菜地

先用一个数组表示一个二叉树搜索树,也就是一个排好序的二叉树,其中左子结点<根结点<右子结点

利用结构数组的形式来表示,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
)
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-03-01 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档