So implementieren Sie die Unterstrukturbeurteilung von Binärbäumen in PHP (Code)

Der Inhalt dieses Artikels handelt davon, wie PHP die Unterstrukturbeurteilung (Code) eines Binärbaums implementiert. Ich hoffe, dass er für Sie hilfreich ist.

Geben Sie zwei Binärbäume A und B ein und bestimmen Sie, ob B eine Unterstruktur von A ist. (ps: Wir sind uns einig, dass der leere Baum keine Unterstruktur eines Baums ist)
1. Ein Unterbaum bedeutet, dass er einen Knoten enthält und alle Knoten unter diesem Knoten enthalten muss und beide Bäume gleichzeitig enden
2. Die Unterstruktur kann ein beliebiger Teil des A-Baums sein
Ideen:
1. Die erste Rekursion: zwei Bäume A und B. Finden Sie zuerst den gleichen Punkt in A wie den Wurzelknoten von B. Wenn Die Wurzel von A Nein, dann rekursieren Sie den linken und rechten Teilbaum von A, um
2 zu finden: Starten Sie den Vergleich von den Wurzelknoten der beiden Bäume. Wenn der B-Baum leer ist, kehren Sie zurück wahr; wenn B nicht leer ist, ist A leer, gib false zurück
                                                             Rekursiver rechter Teilbaum von A, rechter Teilbaum von B

HasSubtree(treeA,treeB)
    if(treeA->val==treeB->val)//根结点相同
        res=tree1HasTreeB(treeA.treeB)
    if !res
        res=HasSubtree(treeA->left.treeB)//第一层遍历
    if !res
        res=HasSubtree(treeA->right.treeB)//第一层遍历
    return res
tree1HasTreeB(treeA,treeB)
    //顺序不能变
    if treeB==null  //B到底的时候，就是true
        return true
    if treeA==null
        return false//B没到底，A到底了，就是false
    if treeA->val!=treeB->val //A和B的结点没对上
        return false
    //短路语法 ，如果前面的是false，直接返回false,后面不用走
    return tree1HasTreeB(treeA->left,treeB->left)&&tree1HasTreeB(treeA->right,treeB->right)

<?php
class TreeNode{
    public $val;
    public $left = NULL;
    public $right = NULL;
    public function __construct($val){
        $this->val = $val;
    }   
}


//构造两棵树
$node1=new TreeNode(1);
$node2=new TreeNode(2);
$node3=new TreeNode(3);
$node4=new TreeNode(4);
$node5=new TreeNode(5);


$treeA=$node1;
$node1->left=$node2;
$node1->right=$node3;
$node3->left=$node4;
$node3->right=$node5;

//var_dump($treeA);

$node6=new TreeNode(3);
$node7=new TreeNode(4);
$node6->left=$node7;
$treeB=$node6;
//var_dump($treeB);

function HasSubtree($pRoot1,$pRoot2){
        $res=false;
        if($pRoot1==null || $pRoot2==null) return $res;
        if($pRoot1->val==$pRoot2->val) $res=tree1HasTree2($pRoot1,$pRoot2);
        if(!$res) $res=HasSubtree($pRoot1->left,$pRoot2);
        if(!$res) $res=HasSubtree($pRoot1->right,$pRoot2);
        return $res;
}
function tree1HasTree2($treeA,$treeB){
        if($treeB==null) return true;
        if($treeA==null) return false;
        if($treeA->val!=$treeB->val) return false;
        return tree1HasTree2($treeA->left,$treeB->left)&&tree1HasTree2($treeA->right,$treeB->right);
}
var_dump(HasSubtree($treeA,$treeB));

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Unterstrukturbeurteilung von Binärbäumen in PHP (Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!