Discussion :

[lazydev]

Voilà je suis tjrs. en train de faire quelques exemples pour préparer mon examen et je voulais avoir votre avis sur mon code.

Voilà les 3 questions que j'essaye de résoudre j'ai du mal à comprendre la question b si qn. a une de ce qu'il faut faire ce serait sympa de me l'expliquer.
J'ai l'impression que je me complique la vie avec la question b.

Sinon j'ai écrit un code pour les questions a et c

(a)Ecrire une fonction qui prend comme argument un arbre binaire dans lequel chaque noeud a une clé et détermine si l'arbre est un arbre binaire trié.

(b)Ecrire une fonction qui calcue dans un arbre binaire trié pour un noeud donné x le successeur de x c'est-à-dire, le noeud avec la plus petite clé supérieur à la clé de x.

(c)Pour un noeud donnée d'un arbe binaire définir de déséquilibre comme la différence des hauteurs des deux sous arbres en valeur absolue (on suppose que la hauteur d'un sous-arbre vide est -1). le déséquilibre d'un arbre est le maximum des déséquilibres des noeuds. Ecrire un fonction qui calcule le déséquilibre d'un arbre binaire donné en argument.

Réponse A

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
 
static boolean isBST2(Arbre root) {
 return( isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE) );
}
 
static boolean isBST2(Arbre node, int min, int max) {
  if (node==null) {
    return(true);
  }
 
   boolean leftOk = isBST2(node.filsG, min, node.contenu);
 
   // if the left is not ok, bail out
   if (!leftOk) return(false);
 
 
   // right should be in range node.data+1..max
   boolean rightOk = isBST2(node.filsD, node.contenu+1, max);
 
   if (!rightOk) return(false);
 
   if(node.contenu<=max && node.contenu>=min){
       return true;
   }else{
       return false;
   }
 
}

Réponse C

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
 
 static int calculeDes(Arbre a)
  {
    int hautTD=0;
    int hautTG=0;
    if(a.filsD!=null){
        hautTD=calculeDes(a.filsD);
    }
    if(a.filsG!=null){
        hautTG=calculeDes(a.filsG);
    }
    int désT=Math.abs(Math.max(hautTD, hautTG));
    int hautG=hauteur(a.filsD);
    int hautD=hauteur(a.filsG);
    int dés=Math.abs(hautG-hautD);
    return Math.max(dés,désT);
  }
 
  static int hauteur(Arbre a){
      if(a==null){
        return -1;
      }else{
        int hautG=hauteur(a.filsG);
        int hautD=hauteur(a.filsD);
        return 1+Math.max(hautG, hautD);
      }
  }

Merci

[dinobogan]

La question b n'est pas limpide. J'imagine que la fonction a en paramètre un arbre et une clé, et qu'il faut chercher récursivement la clé suivante dans l'ordre de tri de l'arbre ?
Si c'est ça, alors il faut faire une simple recherche par une boucle while dans l'arbre pour trouver la clé (puisque l'arbre est trié), puis renvoyer le fils droit du noeud contenant la clé, ou null si pas de fils.

Pour la réponse a, j'aurais fait plus simple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
static boolean isBST2(Arbre root)
{
  if( root == null )
  {
    return true;
  }
 
  return isBST2( root.filsG ) && isBST2( root.filsD )
    && ( root.filsG == null || root.contenu >= root.filsG.contenu )
    && ( root.filsD == null || root.contenu < root.filsD.contenu ) );
}

[lazydev]

Pour la question b j'ai du mal à comprendre l'énoncé de la question, c'est ca mon problème.
J'avais aussi penser a ce que tu propose, donc je pars sur ca et j'essais de faire l'exo.

Merci pour la simplification de la réponse a

[professeur shadoko]

questions complémentaires (puisqu'on est dans le monde universitaire ): est-ce qu'on vous fait calculer la complexité d'un tel algorithme? Est ce qu'on en fait tirer des conclusions sur la conception de tels arbres?

[lazydev]

je ne suis pas dans une université mais je prépare seulement un examen, je n'ais plus trop l'habitude de programmer donc pas évident .
Mais si je me rapelle bien dans mon école sup. on calculé la complexité de tel arbres, mais bon cela remonte à tellement loin.
Il y a-t-il une raison a ta question?

Une petite question lecode :

Code :

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

1
2
3
4
 
return isBST2( root.filsG ) && isBST2( root.filsD )
    && ( root.filsG == null || root.contenu >= root.filsG.contenu )
    && ( root.filsD == null || root.contenu < root.filsD.contenu ) );

on pourrait le simplifier en supprimant le root.filsG == null et root.filsD == null?

Code :

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

1
2
3
4
 
return isBST2( root.filsG ) && isBST2( root.filsD )
    && (root.contenu >= root.filsG.contenu )
    && ( root.contenu < root.filsD.contenu ) );

Ou est-ce-que j'ai rater un truc.

[dinobogan]

non, ce n'est pas simplifiable, car tu tentes d'accéder à un attribut du fils. Si le fils est null, il va y avoir un NullPointerException.
Il faut donc tester si l'objet existe avant de l'utiliser.

[professeur shadoko]

Il y a-t-il une raison a ta question?

ben oui: l'algo reste purement un exercice vu que sa complexité est pas terrible. Le fait d'être "trié" devrait être une propriété sui generis de l'arbre et les opérations d'insertion doivent en tenir compte (arbres "balancés").