Maison > développement back-end > tutoriel php > Comment implémenter PHP pour déterminer s'il s'agit d'une séquence de parcours post-ordre d'un arbre de recherche binaire (code)

Comment implémenter PHP pour déterminer s'il s'agit d'une séquence de parcours post-ordre d'un arbre de recherche binaire (code)

不言
Libérer: 2023-04-04 09:26:01
avant
2027 Les gens l'ont consulté


Le contenu de cet article explique comment PHP implémente la séquence de parcours post-ordre (code) pour déterminer s'il s'agit d'un arbre de recherche binaire. Pour valeur de référence, les amis dans le besoin peuvent s'y référer. J'espère que cela vous sera utile.

Séquence de parcours post-ordre de l'arbre de recherche binaire :
Saisissez un tableau d'entiers pour déterminer si le tableau est le résultat du parcours post-ordre d'un certain arbre de recherche binaire. Si oui, affichez Oui, sinon affichez Non. Supposons que deux nombres quelconques du tableau d’entrée soient différents l’un de l’autre.
Idée :

1. Le parcours post-ordre est à gauche et à droite, le dernier élément est le nœud racine
2. Arbre de recherche binaire, sous-arbre gauche<=nœud racine<=sous-arbre droit3. Parcourez le tableau et trouvez la première position supérieure à la racine. Le sous-arbre gauche de cette position est le sous-arbre gauche et le sous-arbre droit est le sous-arbre droit
4. que root, renvoie false
5 Sous-arbres récursifs gauche et droit

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)
Copier après la connexion
.

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!

Étiquettes associées:
php
source:cnblogs.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal