Corrigé du TD n° 11

1) Parcours

Dessinez 2 arbres binaires (chaque nœud interne possède exactement deux fils) ayant chacun 11 nœuds désignés
par les lettres de a à k et dont la racine est a. Pour chacun de ces arbres, donnez l’ordre de parcours des nœuds
suivant qu’il est préfixé, infixé ou postfixé.

        Arbre 1

           a
          / \                      Arbre 2
         /   \
        /     \                       a
       /       \                     / \
      /         \                   /   \
     b           c                 /     \
    / \         / \               b       c
   /   \       /   \             / \     / \
  d     e     f     g           d   e   f   g
 / \   / \                     / \         / \
h   i j   k                   h   i       j   k

Parcours :

            Arbre 1         Arbre 2

préfixé   abdhiejkcfg     abdhiecfgjk
infixé    hdibjekafcg     hdibeafcgjk
postfixé  hidjkebfgca     hidebfjkgca

2) Classe Arbre récursive

2.1) 

Arbre racine()
  Arbre racine <- self
  tant que racine.parent != nil
    racine <- racine.parent
  renvoyer racine

ou, en exploitant la récursivité,

Arbre racine()
  si parent = nil
    renvoyer self
  sinon
    renvoyer parent.racine()

2.2)

Ici, il s'agit de compter le nombre total des noeuds dans le sousarbre, racine excluse :

entier nbDescendants()
  entier n <- 0
  pour i de 1 à fils.taille()
    n <- n + fils[i].nbDescendants() + 1
  renvoyer n

2.3)

entier nbFeuilles()
  si fils.taille() = 0  # ce noeud est une feuille
    renvoyer 1
  sinon
    entier n <- 0
    pour i de 1 à fils.taille()
      n <- n + fils[i].nbFeuilles()
    renvoyer n

2.4)

entier profondeur()
  si parent = nil
    renvoyer 0
  sinon
    renvoyer parent.profondeur() + 1

2.5)

entier nbPetitFils()
  entier n <- 0
  pour i de 1 à fils.taille()
    n <- n + fils[i].fils.taille()
  renvoyer n

2.6)

entier nbDescendants(entier k)
  entier n <- 0
  if k > 0
    pour i de 1 à fils.taille()
      n <- n + fils[i].nbDescendants(k - 1) + 1
  renvoyer n

2.7)

booléen estDescendant(Arbre x)
  si x.parent = nil
    renvoyer faux
  sinon
    renvoyer estDescendant(x.parent)

3.2)

Supposons de disposer d'une classe Ensemble, avec les deux méthodes
- ajoute(x) : ajoute l'élément x à l'ensemble
- contient(x) : renvoie vrai si x appartient à l'ensemble, faux sinon
(Une telle classe pourrait être réalisée avec une table de hachage, par exemple)

Arbre acpp(Arbre u, Arbre v)
  Ensemble ancêtres <- nouveau Ensemble()
  Arbre a <- u.parent
  tant que a != nil
    ancêtres.add(a)
    a <- a.parent
  Arbre w <- v
  tant que w != nil
    si ancêtres.contient(w)
      sortir de la boucle
    w <- w.parent
  renovoyer w

4)

Voir exemple dans les transparents du cours...

5)

booléen valeur(Interprétation I)
  si fils.taille() = 0
    renvoyer I.valeur(contenu)
  si contenu = négation
    renvoyer non fils[1].valeur(I)
  si contenu = disjonction
    renvoyer fils[1].valeur(I) ou fils[2].valeur(I)
  si contenu = conjonction
    renvoyer fils[1].valeur(I) et fils[2].valeur(I)
  lancer exception : opérateur logique non supporté