Arbres - Exercices - 1

Exercice 1

2020, sujet 0

Question 1

Déterminer la taille et la hauteur de l’arbre binaire suivant :

graph TD
A(A)
B(B)
E(E)
C(C)
D(D)
F(F)
L( )
G(G)
J( )
H(H)
I(I)
A --- B
A --- E
B --- C
B --- D
E --- F
E --- L
D --- G
D --- J
F --- H
F --- I
linkStyle 5 stroke-width:0px;
linkStyle 7 stroke-width:0px;
style L opacity:0;
style J opacity:0;

Question 2

On décide de numéroter en binaire les nœuds d’un arbre binaire de la façon suivante :

  • la racine correspond Ă  1 ;
  • la numĂ©rotation pour un fils gauche s’obtient en ajoutant le chiffre 0 Ă  droite au numĂ©ro de son père ;
  • la numĂ©rotation pour un fils droit s’obtient en ajoutant le chiffre 1 Ă  droite au numĂ©ro de son père ;

Par exemple, dans l’arbre ci-dessous, on a utilisé ce procédé pour numéroter les nœuds A, B, C, E et F .

graph TD
A(A : 1)
B(B : 10)
E(E : 11)
C(C : 100)
D(D : ?)
F(F : 110)
L( )
G(G : ?)
J( )
H(H : ?)
I(I : ?)
A --- B
A --- E
B --- C
B --- D
E --- F
E --- L
D --- G
D --- J
F --- H
F --- I
linkStyle 5 stroke-width:0px;
linkStyle 7 stroke-width:0px;
style L opacity:0;
style J opacity:0;
  1. Dans l’exemple précédent, quel est le numéro en binaire associé au nœud G ?
  2. Quel est le nœud dont le numéro en binaire vaut 13 en décimal ?
  3. En notant \(h\) la hauteur de l’arbre, sur combien de bits seront numérotés les nœuds les plus en bas ?
  4. Justifier que pour tout arbre de hauteur \(h\) et de taille \(n \geqslant 2\), on a : \(h\leqslant n \leqslant 2^h-1\)

Question 3
Un arbre binaire est dit complet si tous les niveaux de l’arbre sont remplis.

graph TD
A(A)
B(B)
C(C)
D(D)
E(E)
F(F)
G(G)
H(H)
I(I)
J(J)
K(K)
L(L)
M(M)
N(N)
O(O)

A --- B
A --- C
B --- D
B --- E
C --- F
C --- G
D --- H
D --- I
E --- J
E --- K
F --- L
F --- M
G --- N
G --- O

On décide de représenter un arbre binaire complet par un tableau de taille \(n + 1\), où \(n\) est la taille de l’arbre, de la façon suivante:

  • La racine a pour indice 1 ;
  • Le fils gauche du nĹ“ud d’indice i a pour indice \(2 \times i\) ;
  • Le fils droit du nĹ“ud d’indice i a pour indice \(2 \times i + 1\) ;
  • On place la taille \(n\) de l’arbre dans la case d’indice 0.

RĂ©pondre aux questions suivantes :

  1. Déterminer le tableau qui représente l’arbre binaire complet de l’exemple précédent.
  2. On considère le père du nœud d’indice \(i\) avec \(i \geqslant 2\). Quel est son indice dans le tableau ?

Question 4

On se place dans le cas particulier d’un arbre binaire de recherche complet où les nœuds contiennent des entiers et pour lequel la valeur de chaque noeud est supérieure à celles des noeuds de son fils gauche, et inférieure à celles des noeuds de son fils droit.

Écrire une fonction recherche ayant pour paramètres un arbre arbre et un élément element. Cette fonction renvoie True si element est dans l’arbre et False sinon. L’arbre sera représenté par un tableau comme dans la question précédente.

Corrigé

Q1 La taille est 9, la hauteur est 4.
Q2 1. G est associé à 1010.
Q2 2. 13 s'écrit 1101 en binaire, c'est donc le nœud I.
Q2 3. Les nœuds les plus en bas sont notés sur \(h\) bits.
Q2 4. L'arbre de hauteur \(h\) de taille minimale est l'arbre filiforme, qui est de taille \(h\).
L'arbre de hauteur \(h\) de taille maximale est l'arbre complet, qui est de taille \(2^h-1\). Si \(n\) est la taille d'un arbre quelconque de taille \(h\), on a donc bien

\(h \leqslant n \leqslant 2^h-1\).

Q3 1. Tableau : [15, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O] .
Q3 2. Le père du nœud d'indice i a pour indice i//2.

Q4 :

Python
def recherche(arbre, element):
    i = 1
    while i < len(arbre):
        if arbre[i] == element:
            return True
        if element < arbre[i]:
            i = 2*i # on se place sur le fils gauche
        else:
            i = 2*i +  1 # on se place sur le fils droit
    return False

Exercice 2

Arbre binaire en POO