Comment implémenter le jugement de sous-structure des arbres binaires en PHP (code)

Le contenu de cet article explique comment PHP implémente le jugement de sous-structure (code) d'un arbre binaire. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Saisissez deux arbres binaires A et B et déterminez si B est une sous-structure de A. (ps : Nous sommes d'accord que l'arbre vide n'est une sous-structure d'aucun arbre)
1. Un sous-arbre signifie qu'il contient un nœud, et il doit contenir tous les nœuds sous ce nœud, et les deux arbres se terminent en même temps.
2. La sous-structure peut être n'importe quelle partie de l'arbre A
Idées :
1. La première récursion : deux arbres A et B. Trouvez d'abord le même point dans A que le nœud racine de B. Si la racine de A Non, puis récursez les sous-arbres gauche et droit de A pour trouver
2. La deuxième récursion : lancer la comparaison à partir des nœuds racines des deux arbres. Lors du parcours, si l'arbre B est vide, retournez. true ; si B n'est pas vide, A est vide, return false
                                                        utiliser using   using             utiliser using ‐ pour récursivement ‐ récursivement le sous-arbre gauche de A et le sous-arbre gauche de B ; récursez le sous-arbre droit de A, le sous-arbre droit de 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)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!