Coder un arbre binaire

On va s'intéresser dans cette page à des arbres binaires.

Un arbre binaire est un arbre pour lequel tout sommet a au plus deux fils, un fils gauche et un fils droit..

Un exemple d'arbre binaire :

r est la racine de l'arbre, son fils gauche est a, son fils droit est b.
j a un fils gauche (m) et pas de fils droit.
m n'a pas de fils, c'est une feuille de l'arbre.

On décide de coder cet arbre dans un premier temps de la façon suivante :


def noeud(nom, fg = None, fd = None) :
    return {'racine': nom, 'fg' : fg, 'fd': fd}


k = noeud('k')
f = noeud('f')
e = noeud('e', k, None)
b = noeud('b', e, f)
m = noeud('m')
j = noeud('j', m, None)
i = noeud('i')
d = noeud('d', i, j)  
h = noeud('h')
c = noeud('c', None, h) 
a = noeud('a', c, d)
A = noeud('r', a, b)

A partir de ce premier codage, on aimerait obtenir une représentation de l'arbre définie comme suit :

L'arbre vide est représenté par [].

L'arbre racine , codé par :


A = noeud('r')

est représenté par ['r', [], []]

L'arbre racine , codé par :


b = noeud('b')
a = noeud('a')
A = noeud('r', a, b)

est représenté par ['r', ['a', [], []], ['b', [], []]]

L'arbre arbre , codé par :


c = noeud('c')
b = noeud('b',c,None)
a = noeud('a')
A = noeud('r',a,b)

est représenté par ['r', ['a', [], []], ['b', ['c', [], []], []]]

L'arbre tree , codé par :


d = noeud('d')
b = noeud('b',None,d)
a = noeud('a')
A = noeud('r',a,b)

est représenté par ['r', ['a', [], []], ['b', [], ['d', [], []]]]

Écrire une fonction python récursive permettant d'obtenir, à partir du codage proposé, un arbre représenté sous forme d'une liste comme défini dans les exemples précédents.

un code


def noeud(nom, fg = None, fd = None) :
    return {'racine': nom, 'fg' : fg, 'fd': fd}

 
k = noeud('k')
f = noeud('f')
e = noeud('e', k, None)
b = noeud('b', e, f)
m = noeud('m')
j = noeud('j', m, None)
i = noeud('i')
d = noeud('d', i, j)  
h = noeud('h')
c = noeud('c', None, h) 
a = noeud('a', c, d)
A = noeud('r', a, b) 
 
    

def construit(arbre) :
	if arbre == None : return []
	else : return [arbre['racine'],  construit(arbre['fg']), construit(arbre['fd']) ]
      
        
 
    
print(construit(A))

représentation visuelle

A partir du codage obtenu dans l'exercice précédent, on aimerait obtenir une représentation visuelle.

On décide dans un premier temps de la représentation texte suivante :

L'arbre racine codé maintenant par ['r', [], []] sera visualisé ainsi :

r
-*
-*

L'arbre racine , codé par :


b = noeud('b')
a = noeud('a')
A = noeud('r', a, b)

puis par ['r', ['a', [], []], ['b', [], []]] sera visualisé ainsi :

r
-a
--*
--*
-b
--*
--*

L'arbre arbre , codé par :


c = noeud('c')
b = noeud('b',c,None)
a = noeud('a')
A = noeud('r',a,b)

puis par ['r', ['a', [], []], ['b', ['c', [], []], []]] sera visualisé ainsi :

r
-a
--*
--*
-b
--c
---*
---*
--*

L'arbre tree , codé par :


d = noeud('d')
b = noeud('b',None,d)
a = noeud('a')
A = noeud('r',a,b)

puis par ['r', ['a', [], []], ['b', [], ['d', [], []]]]

r
-a
--*
--*
-b
--*
--d
---*
---*

Écrire une fonction python récursive permettant cette représentation texte.

un code



def noeud(nom, fg = None, fd = None) :
    return {'racine': nom, 'fg' : fg, 'fd': fd}

 
k = noeud('k')
f = noeud('f')
e = noeud('e', k, None)
b = noeud('b', e, f)
m = noeud('m')
j = noeud('j', m, None)
i = noeud('i')
d = noeud('d', i, j)  
h = noeud('h')
c = noeud('c', None, h) 
a = noeud('a', c, d)
A = noeud('r', a, b) 
 

     
 
def construit(arbre) :
	if arbre == None : return []
	else : return [arbre['racine'],  construit(arbre['fg']), construit(arbre['fd']) ]
      
        
def represente(arbre, p = 0) :
    if arbre == [] : print('*')
    else :
        print(arbre[0])
        p += 1
        print('-' * p, end ='')
        represente(arbre[1], p)
       
        print('-' * p, end ='')
        represente(arbre[2], p)
        

    
represente(construit(A))

hauteur

L'arbre ci-dessous a pour hauteur 4 : c'est la distance la plus grande entre la racine et une feuille.
exemple d'arbre binaire

L'arbre limité à sa racine (un sommet sans fils) est de hauteur 0.

A partir du codage, obtenu précédemment, d'un arbre binaire sous forme de liste, définir une fonction python récursive déterminant la hauteur d'un arbre.

un code




def noeud(nom, fg = None, fd = None) :
    return {'racine': nom, 'fg' : fg, 'fd': fd}

 
k = noeud('k')
f = noeud('f')
e = noeud('e', k, None)
b = noeud('b', e, f)
m = noeud('m')
j = noeud('j', m, None)
i = noeud('i')
d = noeud('d', i, j)  
h = noeud('h')
c = noeud('c', None, h) 
a = noeud('a', c, d)
A = noeud('r', a, b) 
 
 


def construit(arbre) :
	if arbre == None : return []
	else : return [arbre['racine'],  construit(arbre['fg']), construit(arbre['fd']) ]
        
   
        
def hauteur(arbre ) :
	if arbre == []  : return -1
	else :
		h1 = 1 + hauteur( arbre[1] )
		h2 = 1 + hauteur( arbre[2] )
		return max(h1, h2)
        

 
print(hauteur(construit(A)))

parcours

Nous allons maintenant nous balader autour de l'arbre de la façon ci-dessous (balade à gauche d'abord) et définir des "parcours d'un arbre binaire", c'est à dire des ordres de traitement des sommets rencontrés (le traitement consistera ici simplement en l'écriture du nom du sommet).

Le parcours préfixe

Dans la balade autour de l'arbre (à gauche d'abord) : chaque sommet est traité la première fois qu'on le rencontre dans la balade.

Ici : r,a,c,h,d,i,j,m,b,e,k,f.

Le parcours postfixe (ou suffixe)

Dans la balade autour de l'arbre (à gauche d'abord) : chaque sommet est traité la dernière fois qu'on le rencontre dans la balade.

Ici : h,c,i,m,j,d,a,k,e,f,b,r.

Le parcours infixe

Chaque noeud ayant un fils gauche est traité la seconde fois qu'on le voit dans la balade,
chaque noeud sans fils gauche est traité la première fois qu'on le voit dans la balade.

Une autre façon de décrire cela : on ajoute des fils gauche et droits invisibles à ceux qui n'en ont pas et on traite chaque noeud la seconde fois qu'on le voit dans ce graphe étendu.

Ici : c, h, a, i, d, m, j, r, k, e, b, f.

Votre mission :

Écrire une fonction python récursive pour traduire chacun des parcours.

un code




def noeud(nom, fg = None, fd = None) :
    return {'racine': nom, 'fg' : fg, 'fd': fd}

k = noeud('k')
f = noeud('f')
e = noeud('e', k, None)
b = noeud('b', e, f)
m = noeud('m')
j = noeud('j', m, None)
i = noeud('i')
d = noeud('d', i, j)  
h = noeud('h')
c = noeud('c', None, h) 
a = noeud('a', c, d)
A = noeud('r', a, b) 


def construit(arbre) :
	if arbre == None : return []
	else : return [arbre['racine'],  construit(arbre['fg']), construit(arbre['fd']) ]
        
 
        
        
def parcoursPrefixe(arbre) :
    if(arbre != []) :
        print(arbre[0], end = ',')
        parcoursPrefixe(arbre[1])
        parcoursPrefixe(arbre[2])
        
def parcoursPostfixe(arbre) :
    if(arbre != []) :
        parcoursPostfixe(arbre[1])
        parcoursPostfixe(arbre[2])
        print(arbre[0], end = ',')
        
def parcoursInfixe(arbre) :
    if(arbre != []) :
        parcoursInfixe(arbre[1])
        print(arbre[0], end = ',')
        parcoursInfixe(arbre[2])
       
       
print("Parcours préfixe : ")
parcoursPrefixe(construit(A))


print('\n')
print("Parcours postfixe : ")
parcoursPostfixe(construit(A))

print()
print("\nParcours infixe : ")
parcoursInfixe(construit(A))

un autre code de représentation

On change de structure de représentation d'un arbre. On va utiliser un dictionnaire.

On codera par exemple comme suit :


A = { 'r' : ['a','b'], 'a' : ['c','d'], 'b' : ['e','f'],\
	 'c' : ['','h'], 'd' : ['i', 'j'], 'e' : ['k',''], 'f' : ['',''], \
  'h' : ['',''], 'i': ['',''], 'j' : ['m',''], 'k' : ['',''], 'm' : ['','']}

l'arbre déjà utilisé :
arbre

Écrire une nouvelle version récursive des fonctions hauteur, parcoursInfixe, parcoursPrefixe, parcoursPostfixe avec cette représentation (on ne traitera pas le cas de l'arbre vide).

un code




 

A = { 'r' : ['a','b'], 'a' : ['c','d'], 'b' : ['e','f'], \ 
	'c' : ['','h'], 'd' : ['i', 'j'], 'e' : ['k',''], 'f' : ['',''], \
     'h' : ['',''], 'i': ['',''], 'j' : ['m',''], 'k' : ['',''], 'm' : ['','']}


def hauteur(arbre, noeud='r') :
	""" hauteur d'un arbre non vide"""
	if arbre[noeud][0] == '' and arbre[noeud][1] == '' : return 0
	elif arbre[noeud][0] == '' : return 1 + hauteur(arbre, arbre[noeud][1])
	elif arbre[noeud][1] == '' : return 1 + hauteur(arbre, arbre[noeud][0])
	else : return 1 + max( hauteur(arbre, arbre[noeud][0]), hauteur(arbre, arbre[noeud][1]) )
        
        
def parcoursPrefixe(arbre, noeud='r') :
    if(noeud != '') :
        print(noeud, end = ',')
        parcoursPrefixe(arbre, arbre[noeud][0])
        parcoursPrefixe(arbre, arbre[noeud][1])
        
def parcoursPostfixe(arbre, noeud='r') :
    if(noeud != '') :
        parcoursPostfixe(arbre, arbre[noeud][0])
        parcoursPostfixe(arbre, arbre[noeud][1])
        print(noeud, end = ',')
     
        
def parcoursInfixe(arbre, noeud='r') :
    if(noeud != '') :
        parcoursInfixe(arbre, arbre[noeud][0])
        print(noeud, end = ',')
        parcoursInfixe(arbre, arbre[noeud][1])
       
       
       
print("Hauteur de l'arbre : ")
print(hauteur(A))

print()
print("Parcours préfixe : ")
parcoursPrefixe(A)

print('\n')
print("Parcours postfixe : ")
parcoursPostfixe(A)

print('\n')
print("Parcours infixe : ")
parcoursInfixe(A)