Planche : 1


Diversion

On sait…







Slogan!
Ce qui est static est à la classe, ce qui est dynamique est à l’objet.

Planche : 2


Application du slogan
class Pair {
  static int count = 0 ;
  int xy ;

  Pair (int xint y) {
    this.x = x ; this.y = y ; count++ ;
  }

  public static void main(String [] arg) {
    Pair p = new Pair (1, 2), q = new Pair (2, 3) ;
    System.out.println(count) ;
  }
}

Planche : 3


Implémentation (simplification)

Deux objets de la même classe Pair.


Planche : 4


Cas des méthodes

Le slogan s’applique encore.


Planche : 5


Si c’est static, ya pas d’objet

Une petite inattention.

class Pair {
  private int count ;
  int xy ;
  Pair (int xint y) {
    this.x = x ; this.y = y ; count++ ;
  }

  static int lireCount() {
    return count ;
  }
}

Est-ce que ça compile ? Non ! Pourquoi ?.

La méthode statique lireCount fait référence à la variable non-statique count.

# javac Pair.java
Pair.java:10: non-static variable count
              cannot be referenced from a static context
    return count ;
           ^

Planche : 6


Quelques exemples de méthodes dynamiques

Planche : 7


Un arbre dans la nature

Planche : 8


Un arbre dans l’ordinateur

Planche : 9


Structure récursive (« fractale »)

Planche : 10


Au final…
T → D[-T]+T

Planche : 11


Un autre arbre, plus naturel
T → D[-T]D[++T]T

Planche : 12


Les arbres « hiéarchie »

Planche : 13


Les arbres structurants

Planche : 14


Ou plus informatiquement…
  

Planche : 15


Bon et en Java ?

Planche : 16


Définition des cellules d’arbre (binaire)
class Tree {
  int val ;
  Tree leftright ;

  Tree (Tree leftint valTree right) {
    this.left = left ;
    this.val = val ;
    this.right = right ;
  }
}

Remarquer


Planche : 17


Fabriquons un arbre
new Tree (
   new Tree (null, 2, null),
   4,
   new Tree (
     new Tree (null, 6, new Tree (null, 7, null)),
     8,
     new Tree (null, 9, null)))

Planche : 18


Surcharge du constructeur

Permet de faire un peu plus concis (mais ça n’ira pas loin).

Tree (int val) {
  this.val = val ;
}

new Tree (
   new Tree (2),
   4,
   new Tree  (
     new Tree (null, 6, new Tree (7)),
     8,
     new Tree (9)))

Planche : 19


Arbre et récursivité

Les arbres sont des structures très récursives :

On peut voir les arbres comme solutions de cette équation.

T = null ⊎ (T × int × T)

La programmation est systématiquement récursive.


Planche : 20


Vocabulaire

En java, arbre ∼ référence, sommet ∼ cellule.


Planche : 21


Se repérer dans un arbre

Dans une liste on parlait du k-ième élément, dans un arbre on parle de chemin.

Par exemple le chemin vers la feuille étiquetée 7 est : 1.0.1.

Le chemin vers la racine est : «» (rien ou Λ).

Il est également pratique de repérer les sous-arbres (ex. 0.0).

Bref, les chemins sont tout bêtement des listes.


Planche : 22


Hauteur

La profondeur d’un sous-arbre est la longueur du chemin qui y mène,


Planche : 23


Calcul de la hauteur

Il n’y pas le choix : approche… récursive.

H(∅)=
H(T0, _, T1)=1 + max(H(T0), H(T1))
static int getHeight(Tree t) {
  if (t == null) {
    return 0 ;
  } else {
    return 1+Math.max(getHeight(t.left), getHeight(t.right)) ;
  }
}

Planche : 24


Borner la hauteur

Soit un arbre de hauteur h, contenant n sommets.

h ≤ n ≤ 2h−1

Soit encore.

log2(n+1) ≤ h ≤ n

Planche : 25


Trouver un sous-arbre connaissant son chemin

La définition inductive est assez claire :

T/Λ = T,   (T0, _, T1)/0.C = T0/C,   (T0, _, T1)/1.C = T1/C,  

Un Chemin est une liste d’entiers.

static Tree subTree(Tree tChemin c) {
  if (c == null) {
    return t ;
  } else if (t == null) {
    throw new Error () ;
  } else if (c.val == 0) {
    return subTree(t.leftc.next) ;
  } else if (c.val == 1) {
    return subTree(t.rightc.next) ;
  } else {
    throw new Error () ;
  }
}

Planche : 26


Trouver son chemin II

Du point de vue du chemin, on effectue un parcours de liste, d’où le code alternatif suivant.

static Tree subTree(Tree tChemin c) {
  for ( ; c != null ; c = c.next) {
    // Traiter d'abord l'erreur
    if (t == null) { throw new Error () ; }
    // Ici t n'est pas null
    if (c.val == 0) { t = t.left ; }
    else if (c.val == 1) { t = t.right ; }
    else { throw new Error () ; }
  }
  return t ;
}

De fait, la récursion était terminale (cf. amphi 02).


Planche : 27


Arbres strictement binaires

Les sommets ont zéro ou deux fils. Définition sans l’arbre vide :

Attention : en programmation null demeure…(pour repérer les feuilles).

class Tree {
  // Comme avant.

  Tree (int x) { this.val = x; } // Constructeur des feuilles.

  boolean isLeaf() {
    return this.left == null && this.right == null ;
  }
}

Planche : 28


Une amusante propriété des arbres binaires (stricts)
Un arbre binaire strict possède n+1 feuilles et n sommets internes.

Planche : 29


Parcourir un arbre

En largeur d’abord.

Si on parcourt pour afficher, on affichera donc :

[4], [2, 8], [6, 9], [7].

C’est conceptuellement assez simple (parcours « par étages » de profondeur croissante), mais un peu délicat à programmer.


Planche : 30


Parcours en profondeur d’abord

Conceptuellement simples, si on veut bien adopter le point de vue récursif :

Il n’y a rien d’autre à comprendre (savoir)!


Planche : 31


Exemple, en profondeur (postfixe)

Planche : 32


Le plus simple est encore de programmer
static void postfix(Tree t) {
  if (t != null) {
    postfix(t.left) ;
    postfix(t.right) ;
    System.out.println(t.val) ;
  }
}

Note : généralisation de l’affichage des listes.

static void print(List p) {
  if (p != null) {
    print(p.next) ; System.out.prinln(t.val) ;
  }
}

Planche : 33


Un problème un peu différent

Calculer la liste des étiquettes (dans l’ordre postfixe).

Solution « théorique »

P(∅)=∅ 
P(T0xT1)=P(T0) ; P(T1) ; x

Bon nous voilà bien avancés…

static IntList postfix(Tree t) {
  if (t == null) {
     return null ;
  } else {
    return
      IntList.append(postfix(t.left),
        IntList.append(postfix(t.right),
          new IntList (t.valnull))) ;
  }
}

Planche : 34


Débarassons nous de ces concaténations coûteuses

Généralisons (un peu) le problème. Le mission de P(T, k) est renvoyer la liste des étiquettes de T suivie de la liste k.

P(∅, k)k 
P((T0xT1), k)P(T0,P(T1, (x ; k)))
static IntList postfix(Tree tIntList k) {
  if (t == null) {
    return k ;
  } else {
    return
      postfix(t.leftpostfix(t.rightnew IntList (t.val,k))) ;
  }
}
static IntList postfix(Tree t) { // Surcharge
  return postfix(tnull) ;
}

Planche : 35


Comment programmer le parcours en largeur

On va donc avoir recours à un raisonnement plus global.


Planche : 36


Programmation du parcours en largeur
static void bfs(Tree t) {
  TreeList next = new TreeList(t,null) ; // int k=0 ;
  while (next != null) {  // next -> sous-arbres profondeur k
    TreeList now = next ; // now -> sous-abres profondeur k
    next = null ;
    for ( ; now != null ; now = now.next) {
// pour tous les sous-arbres de profondeur k
      Tree t = now.val ;
      if (t != null) {
        System.out.println(t.val) ; // Afficher
        next = new TreeList (t.left,
                 new TreeList (t.rightnext)) ;
        // Collecter les fils (next -> profondeur k+1)
      }
    } // k = k+1 => next -> profondeur k
  }
}

Planche : 37


Programmation traditionnelle de la largeur d’abord
static void bfs(Tree t) {
  Fifo f = new Fifo () ;
  f.enfile() ;
  while (!f.isEmpty()) {
     Tree t = f.defile() ;
     if (t != null) {
       System.out.println(t.val) ;
       f.enfile(t.left) ;
       f.enfile(t.right) ;
     }
  }
}

Pourquoi ça marche ?


Planche : 38


Exemple de fonctionnement
 Λ 
  
4
—→
 
  
 10 
  
2
—→
 
  
 0.10.01 
  
8
—→
 
 1.11.00.10.0 
  —→…—→  
 1.11.0 
  
6
—→
 
 1.0.11.0.01.1 
  
9
—→
 

Planche : 39


Preuve de correction du parcours avec file

Transitions effectuées sur un état comprenant file F et affichage A.

F=F; (T0xT1)k,  A=A  ⇒  F=T1k+1T0k+1F,  A=Axk
F=F; ∅k,  A=A  ⇒  F=F,  A=A

(T à la profondeur k, noté Tk.)

On voit alors que l’on a, en n étapes

F=T1k; ⋯; Tnk,  A=A   
*
 
   F=U1k+1; ⋯; Umk+1,  A=Ax1k; ⋯; xk

Ce qui suffit pour montrer, qu’en h grosses étapes, on a :

F=T0,  A=  
*
 
   F=,  A=A

A est une séquence de sommet de profondeurs croissantes.


Planche : 40


Et avec une pile explicite ?
static parcours(Tree t) {
  Stack<Treestack = new Stack<Tree> () ;
  stack.push(t) ;
  while (!stack.isEmpty()) {
     Tree t = stack.pop() ;
     if (t != null) {
       System.out.println(t.val) ;
       stack.push(t.right) ;
       stack.push(t.left) ;
     }
  }
}

C’est le parcours : préfixe !


Planche : 41


Preuve de l’affichage préfixe avec pile explicite

Transitions effectuées sur un état comprenant pile S et affichage A.

S=S; (T0xT1),  A=A  ⇒  S=ST1T0,  A=Ax
S=S; ∅,  A=A  ⇒  S=S,  A=A

Notons P la séquence des sommets dans l’ordre préfixe :

P(∅) =,   P(T0xT1) = xP(T0); P(T1)

On veut montrer

S=ST,  A=A  
*
 
  S=S,  A=AP(T)

Par induction structurelle sur T (cas de base laissé en exercice).

S=S; (T0xT1),  A=A  ⇒  S=ST1T0,  A=Ax
 
  
*
 
  
S=ST1,  A=Ax;P(T0)
 
  
*
 
  
S=S,  A=Ax;P(T0); P(T1)

Planche : 42


Les expressions arithmétiques

1 + (2 × 3)

Approche récursive, une expression est :

Inportant : Il n’y a pas d’arbre vide.


Planche : 43


Réalisation simple
class Exp {
  final static int OP=0, INT=1 ;
  int nature ; // champ 'indicateur'

  int val ;   // valide si nature == INT
  char op ; Exp leftright ; // valides si nature == OP

  Exp (int val) {
    nature = INT ; this.val = val ;
  }

  Exp (Exp leftchar opExp right) {
    nature = OP ;
    this.op = op ; this.left = left ; this.right = right ;
  }
}

Planche : 44


Construction, avec les constructeurs
  Exp e = new Exp(
      new Exp(1),
      '+',
      new Exp (new Exp(2), '*'new Exp(3))) ;

C’est lourd et en fait assez eloigné des habitudes.

Habituellement, on écrit 1 + 2 × 3 et on « comprend » l’arbre.


Planche : 45


Pour le moment

Planche : 46


Exemple d’exécution du lecteur d’expressions

—→1 —→2 —→3 —→× —→+

Planche : 47


Réalisation du lecteur d’expressions
class Exp {
  public static void main (String [] arg) {
    Stack<Expstack = new Stack<Exp> ;
    for (int i = 0 ; i < arg.length ; i++) {
      String cmd = arg[i] ;
      if (cmd.equals("+")) {
        Exp x = stack.pop(), Exp = stack.pop() ;
        stack.push(new Exp (y'+'x));
      } else if …
      // Idem pour "*", "/", "-"
      } else {
        stack.push(new Exp (Integer.parseInt(cmd))) ;
      }
    }
    Exp t = stack.pop() ;
  }
}

Planche : 48


Que faire de nos arbres ?

Planche : 49


Résumons nous

Il y a beaucoup de points de vue sur les arbres.


Planche : 50


Les arbres n-aires

Un sommet possède un nombre arbitraire de fils.

Les diverses notions (parcours, etc.) restent naturelles.

En Java :

class Tree {
  int val ;
  TreeList sons ;
  Tree (int valTreeList sons) {
    this.val = val ; this.sons = sons ;
  }
}

class TreeList { … }

Planche : 51


Soyons souples

Selon les circonstances, les listes peuvent être remplacées par des tableaux, des tableaux extensibles (ArrayList<Tree>) etc.

import java.util.* ;
class Tree {
  int val ;
  ArrayList<Treesons ;

  Tree (int valArrayList<Treesons) {
    this.val = val ; this.sons = sons ;
  }

  Tree (int valTree t1Tree t2) {
    this.val = val ;
    this.sons = new  ArrayList<Tree> () ;
    this.sons.add(t1) ; this.sons.add(t2) ;
  }
}

Planche : 52


Un petit exercice

Pour bien se convaincre que les arbres, c’est récursif : calculer tous les chemins !

C(∅)=Λ ; ∅ 
C(T0, _, T1)= Λ ;   { 0.u ∣ u ∈ C(T0) } ;   { 1.u ∣ u ∈ C(T1) }

Clairement, on a besoin d’une fonction auxiliaire : (qui réalise { X.uuU }).

Cette fonction prend en argument un entier (0 ou 1) et une liste de chemins et renvoie : une liste de chemins.

A(x, ∅)=∅ 
A(xu ; U)=(xu) ; A(xU)

Planche : 53


La fonction A

Chemin sont des listes d’entiers et Chemins des listes de listes d’entiers comme d’habitude.

static Chemins add (int xChemins us) {
  if (us == null) {
    return null ;
  } else {
    return
     new Chemins
       (new Chemin (xus.val),
        add (xus.next)) ;
  }
}

Planche : 54


Tous les chemins
C(∅)=Λ ; ∅ 
C(T0, _, T1)=Λ ; A(0, C(T0)) ;  A(1, C(T1))}
static Chemins getPaths (Tree a) {
  if (a == null) {
    return new Chemins (nullnull) ;
  } else {
    Chemins pathsLeft = getPaths(a.left) ;
    Chemins pathsRight = getPaths(a.right) ;
    return
      new Chemins
        (null,
        Chemins.append
          (add(0, pathsLeft), add(1, pathsRight))) ;
  }
}

Planche : 55


Éviter les concaténations
static Chemins add (int xChemins usChemins k) {
  if (us == null) {
    return k ;
  } else {
    return
     new Chemins
       (new Chemin (xus.val),
        add (xus.nextk)) ;
  }
}

Planche : 56


Tous les chemins
static Chemins getPaths (Tree a) {
  if (a == null) {
    return new Chemins (nullnull) ;
  } else {
    Chemins pathsLeft = getPaths(a.left) ;
    Chemins pathsRight = getPaths(a.right) ;
    return
      new Chemins
        (nulladd(0, pathsLeftadd(1, pathsRightnull))) ;
  }
}

Ce document a été traduit de LATEX par HEVEA