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)
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!