二分探索木の事後探索シーケンスであるかどうかを判断するために PHP を実装する方法 (コード)

この記事の内容は、PHP が二分探索ツリーかどうかを判断するための事後探索シーケンス (コード) を実装する方法についてです。参考値として、困っている友人の参考にしていただければ幸いです。

二分探索木の事後探索シーケンス:
整数配列を入力して、配列が特定の二分探索木の事後探索の結果であるかどうかを判断します。 「はい」の場合は「はい」を出力し、そうでない場合は「いいえ」を出力します。入力配列内の任意の 2 つの数値が互いに異なると仮定します。
アイデア:

1. 事後探索は左と右で、最後の要素はルート ノードです。
2. 二分探索ツリー、左のサブツリー3. 配列を走査し、ルートより大きい最初の位置を見つけます。この位置の左のサブツリーが左のサブツリーで、右のサブツリーが右のサブツリーです。
4. 右のサブツリーを走査します。ルートより小さいものは false を返します
5. 再帰的な左右のサブツリー

VerifySquenceOfBST(seq)
    judge(seq,0,seq.size-1)
judge(seq,start,end)
    if start>=end return true
    root=seq[end]
    index
    for i=start;i<end;i++
        if seq[i]>= root
            index=i
            break
    for i=index;i<end;i++
        if seq[i]<root
            return false
    return judge(seq,start,index-1) && judge(seq,index,end-1)

<?php
function judge($seq,$start,$end){
        if(empty($seq)) return false;
        //跳出条件
        if($start>=$end) return true;
        $root=$seq[$end];
        $index=$end;
        //找出第一个大于root的位置
        for($i=$start;$i<$end;$i++){
                if($seq[$i]>=$root){
                        $index=$i;
                        break;
                }   
        }   
        //查找右子树中如果有小于root的返回false
        for($i=$index;$i<$end;$i++){
                if($seq[$i]<$root){
                        return false;
                }   
        }   
        //短路语法递归调用
        return judge($seq,$start,$index-1) && judge($seq,$index,$end-1);
}

function VerifySquenceOfBST($sequence)
{
    return judge($sequence,0,count($sequence)-1);
}

$seq=array(1,2,3);
$bool=VerifySquenceOfBST($seq);
var_dump($bool);

以上が二分探索木の事後探索シーケンスであるかどうかを判断するために PHP を実装する方法 (コード)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。