La fonction rech2() est récursive. Elle prend trois arguments : la valeur recherchée, la racine de l’arbre et l’adresse du
noeud contenant la valeur trouvée. Si la valeur n’est pas trouvée, l’adresse contient NIL.
Fonction rech2(vrech :entier, pArbre, pEncours,pointeurs sur noeud)
Début
Si pArbre=NIL Alors
pEncours=NIL
Sinon
Si pArbre→valeur=vrech Alors
pEncours=pArbre
Sinon
Si pArbre→valeur > vrech Alors
rech2(valeur,pArbre→pGauche, pEncours)
Sinon
rech2(valeur,pArbre→pDroite, pEncours)
FinSi
Finsi
FinSi
FinFonc
c. Ajout d’un élément
Quand vous ajoutez un élément, vous devez respecter la structure de l’arbre ordonné. L’ajout d’un élément rajoute
une feuille à l’arbre. Il vous faut trouver le chemin jusqu’au noeud père. La fonction rech2() peut être modifiée en ce
sens : si l’élément à ajouter n’est pas trouvé, alors le dernier élément qui vaut alors NIL doit être remplacé par la
nouvelle feuille et être raccordé à la bonne branche au père. Il faut donc conserver l’adresse du père.
La fonction inserer() prend trois arguments : la valeur à rajouter
Fonction inserer(v:entier, pArbre, pPrec : pointeurs sur noeud)
Var
pNouveau=pointeur sur noeud
Début
Si pArbre=NIL Alors
pNouveau=nouveau noeud
pNouveau→valeur=v
pNouveau→pGauche=NIL
pNouveau→pDroite=NIL
Si pPrec<> NIL Alors
Si v>pPrec→Valeur Alors
pPrec→pDroite=pNouveau
Sinon
pPrec→pGauche=pNouveau
FinSI
FinSi
Sinon
Si pArbre→valeur!= ou <> v Alors
Si v > pArbre→valeur Alors
insérer (v, pArbre, pArbre→pDroite)
Sinon
insérer (v,pArbre, pArbre→pGauche)
FinSi
FinSi
FinSi
FinFonc
d. Suppression d’un noeud
Pour le dernier point de ce chapitre, c’est vous qui allez écrire l’algorithme de la fonction nécessaire à la suppression
du noeud. Il y a trois cas à traiter :
q La suppression d’un noeud sans fils (une feuille), c’est le cas le plus simple. Le pointeur correspondant (droite
ou gauche) du père doit être placé à NIL.
q La suppression d’un noeud ayant un fils : le fils droit être raccordé au bon pointeur du grandpère.
- 6 -
© ENI Editions - All rigths reserved - Jonifar lina
192
noeud contenant la valeur trouvée. Si la valeur n’est pas trouvée, l’adresse contient NIL.
Fonction rech2(vrech :entier, pArbre, pEncours,pointeurs sur noeud)
Début
Si pArbre=NIL Alors
pEncours=NIL
Sinon
Si pArbre→valeur=vrech Alors
pEncours=pArbre
Sinon
Si pArbre→valeur > vrech Alors
rech2(valeur,pArbre→pGauche, pEncours)
Sinon
rech2(valeur,pArbre→pDroite, pEncours)
FinSi
Finsi
FinSi
FinFonc
c. Ajout d’un élément
Quand vous ajoutez un élément, vous devez respecter la structure de l’arbre ordonné. L’ajout d’un élément rajoute
une feuille à l’arbre. Il vous faut trouver le chemin jusqu’au noeud père. La fonction rech2() peut être modifiée en ce
sens : si l’élément à ajouter n’est pas trouvé, alors le dernier élément qui vaut alors NIL doit être remplacé par la
nouvelle feuille et être raccordé à la bonne branche au père. Il faut donc conserver l’adresse du père.
La fonction inserer() prend trois arguments : la valeur à rajouter
Fonction inserer(v:entier, pArbre, pPrec : pointeurs sur noeud)
Var
pNouveau=pointeur sur noeud
Début
Si pArbre=NIL Alors
pNouveau=nouveau noeud
pNouveau→valeur=v
pNouveau→pGauche=NIL
pNouveau→pDroite=NIL
Si pPrec<> NIL Alors
Si v>pPrec→Valeur Alors
pPrec→pDroite=pNouveau
Sinon
pPrec→pGauche=pNouveau
FinSI
FinSi
Sinon
Si pArbre→valeur!= ou <> v Alors
Si v > pArbre→valeur Alors
insérer (v, pArbre, pArbre→pDroite)
Sinon
insérer (v,pArbre, pArbre→pGauche)
FinSi
FinSi
FinSi
FinFonc
d. Suppression d’un noeud
Pour le dernier point de ce chapitre, c’est vous qui allez écrire l’algorithme de la fonction nécessaire à la suppression
du noeud. Il y a trois cas à traiter :
q La suppression d’un noeud sans fils (une feuille), c’est le cas le plus simple. Le pointeur correspondant (droite
ou gauche) du père doit être placé à NIL.
q La suppression d’un noeud ayant un fils : le fils droit être raccordé au bon pointeur du grandpère.
- 6 -
© ENI Editions - All rigths reserved - Jonifar lina
192