How to implement substructure judgment of binary trees in PHP (code)-PHP Tutorial-php.cn

How to implement substructure judgment of binary trees in PHP (code)

不言

Release： 2023-04-04 08:36:01

forward

2567 people have browsed it

The content of this article is about how PHP implements the substructure judgment (code) of a binary tree. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Input two binary trees A and B, and determine whether B is a substructure of A. (ps: We agree that the empty tree is not a substructure of any tree)
1. A subtree means that it contains a node, and it must contain all the nodes under this node, and the two trees end at the same time
2. The substructure can be any part of the A tree
Ideas:
1. The first recursion: two trees A and B, first find the same point in A as the root node of B. If the root of A No, then recurse the left and right subtrees of A to find
2. The second recursion: start the comparison from the root nodes of the two trees. During the traversal process, if the B tree is empty, return true; if B is not empty, A is empty, returns false
- ; Recurse the right subtree of A, the right subtree of 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)

Copy after login

<?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));

Copy after login

The above is the detailed content of How to implement substructure judgment of binary trees in PHP (code). For more information, please follow other related articles on the PHP Chinese website!