Discussion :

[princessita]

Bonjour
je veux ecrire en c une fonction permettant de verifier si un arbre binaire est un arbre binaire de recherche (c-a-d chaque sous arbre gauche est inferieur ou egal a la racine et chaque sous arbre droite lui est superieur)
Merci de m'aider

[kwariz]

Bonjour,

si on part de la définition d'un abr :

• un arbre vide est un abr
• chaque noeud vérifie :
  
  • le fils gauche est un abr, la clé du fils gauche (s'il existe) doit être inférieure à la clé du noeud
  • le fils droit est un abr, la clé du fils droit (s'il existe) doit être supérieure à la clé du noeud

Donc l'algorithme consiste à simplement vérifier les propriétés qu'on attend d'un abr. L'implémentation dépend de ta sdd mais est simple à mettre en oeuvre. Il te faut une fonction qui checke les propriétés récursivement à partir d'un noeud :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool isBST(node n)
{
  // Si le noeud est vide c'est bon c'est la première propriété
  if (isEmpty(n))
    return true
  else {
    // Sinon on vérifie les autres propriétés
 
    // Si une des propriétés est violées par le fils gauche on renvoie faux
    if (!isEmpty(getLeftChild(n))) {
      if (getKey(getLeftChild(n))>getKey(n))
        return false
      if (!isBST(getLeftChild(n)))
        return false
    }
 
    // Idem pour le fils droit
    if (!isEmpty(getRightChild(n))) {
      if (getKey(getRightChild(n))<=getKey(n))
        return false
      if (!isBST(getRightChild(n)))
        return false
    }
 
    // Si on arrive ici c'est que toutes les propriétés sont vérifiées
    return true;
  }
}

et une fonction pour ta structure arbre qui ne fait qu'appeller la vérification pour un noeud sur la racine.
Suivant ton style de codage, la sdd utilisée, l'unicité des clés, ..., l'implémentation peut être plus ou moins compacte.