[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
)