Discussion :

[hbx360]

Bonsoir, je souhaiterai savoir si pour construire un arbre binaire de recherche il faut obligatoirement passé par des liste doublement chainé ou des structures.

Ou est-ce que l'on peut tous simplement passer par un tableau d'entier par exemple ou l'on permuterait les valeur du tableau.

Merci par avance

[Obsidian]

En effet, un arbre de recherche binaire est un concept abstrait et tu peux donc choisir l'implémentation qui te sied le mieux, pourvu que tu puisses certifier qu'elle en respecte bien les règles.

À titre indicatif, il y a un peu plus de quinze ans, j'en avais implémenté un sur la calculatrice d'un étudiant en chimie, à qui on avait donné (comme à ses camarades) un arbre de décision sur papier, avec des branches « oui » ou « non ». La calculatrice en question était une Casio 7700 doté d'un Basic rudimentaire qui ne pouvait exécuter qu'une seule instruction à la suite d'une condition (ce qui, d'un point de vue algorithmique et automatismes, était un défi intéressant). Il m'a suffi d'initialiser une variable à 1, puis de faire une boucle sans fin dans laquelle je multipliais cette variable par 2, puis ajoutait la réponse de l'utilisateur, soit 0 pour non et 1 pour oui. Chaque nœud disposait alors d'un numéro unique propre.

Il suffisait ensuite d'associer chaque valeur avec un « echo » qui affichait soit la question suivante, soit la décision finale à prendre si on avait atteint une feuille.

[hbx360]

Ah oui assez impressionnant merci pour ta réponse ; donc si je veut créer un arbre binaire en passant par un tableau d'entier uniquement en permutant les différentes valeurs c'est possible si j'ai bien compris. Je précise pour plus de clarté construire un arbre binaire de recherche pour moi ces cette figure là :

.............7
.........../....\
.........4.......8
......../...........\
......3.............10
...../..\.........../
...2....4........9
../
1
..\
...2

[picodev]

Bonjour,

Qu'entends par «par un tableau d'entier uniquement en permutant les différentes valeurs» ?

Si par là tu entends utiliser un tableau de structures avec la propriété que fils_gauche(i)=2*i et fils_droit(i)=2*i+1, avec racine=1 et l'élément de rang 0 jouant le rôle d'un pointeur NULL, alors la réponse est oui.

Un tableau d'entiers uniquement ne pourra pas suffire à moins de disposer d'une valeur «interdite» signifiant qu'un nœud est non occupé. Sinon il te faudra passer par un tableau de structures.
Attention au gaspillage dans les cas d'ABR fortement dégénérés (réduits à une liste).

[hbx360]

Merci pour ta réponse. On est donc impérativement obliger de passer par une structure de ce style là :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
typedef struct noeud
{
    int donnée;
    struct noeud *gauche;
    struct noeud *droite;
};

[picodev]

Non, même si c'est une des manières les plus classiques d'implémenter un arbre.

Je te parlais de valeur interdite et de tableau d'entiers. Si tes entiers sont tous positifs ou nuls alors tu peux stocker ton arbre avec un simple tableau. Si on reprend ton exemple, avec comme valeur interdite -1, le début du tableau serait :

indice	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
valeur	7	4	8	3	-1	-1	10	2	4	-1	-1	-1	-1	9	-1	1	...

Les primitives seront :
racine = 0
fils_gauche(i)=2*i+1
fils_droit(i)=2*i+2
pere(i)=(i-1)/2
est_noeud(i)=tab[i]>=0
valeur(i)=tab[i]

C'est une des implémentations d'arbre avec un tableau.