Discuter:Arbre binaire

Un article de Wikipédia, l'encyclopédie libre.

	Arbre binaire fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
B	Cet article a été classé comme d'Avancement B selon le Tableau d'évaluation du projet. (Voir les statistiques)
Moyenne	Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet. (Contester?)

Pour l'introduction (la présentation de quelques lignes), j'ai laissé la version française (remanié), puisque je la trouvais plus clair.

J'hésite entre pour le titre d'une section entre : == Méthode d'itération des arbres binaires == et == Méthode de parcours des arbres binaires ==, le second étant plus abordable.

Il faudrait trouver des traductions aux liens connexes : [[AVL tree]], [[B-tree]], [[binary space partition]], [[red-black tree]]

Rege 30 nov 2003 à 12:48 (CET)

[modifier] Modification de l'introduction ?

(attention je débute en Wikipédia mais) dans l'introduction: le calcul du nombre de noeuds me parait faux car ce nombre de noeuds est aléatoire, fonction du problème et des modifications de l'arbre. Je pense que l'auteur voulais faire référence au calcul de la hauteur en fonction du nombre de noeuds (inverse de l'article), dans le style:

Soit un arbre de hauteur h. On a les cas extrèmes suivants:

les noeuds forment une chaine: on a $(h + 1)$ noeuds.
l'arbre est parfait complet: on a $\sum_{i=0}^h 2^i = 2^{h+1}-1$ noeuds.

Donc $h + 1 \le n \le 2^{h+1}-1$ .

Et peut être ajouter (si ce n'est déjà fait) les formules des cas particuliers d'arbres binaires, comme pour le tas:

tas rempli: $\sum_{i=0}^h 2^i = 2^{h+1}-1$
tas avec un seul noeud au dernier rang: $(\sum_{i=0}^{h-1} 2^i) + 1 = 2^h$

donc pour une hauteur h: $2^h \le n < 2^{h+1}, h \le lg(n) < h+1, h = ceil(lg(n))$ noeuds (où ceil est la valeur entière inférieure).

Purple Meteor (lundi 21 juin 2004)

[modifier] Abus d'anglicismes

Je n'en suis pas certain, mais je crois qu'il y a un petit abus d'anglicimes avec les termes inordre, préordre et postordre qui n'existent pas dans les dictionnaires. Ils viendraient tout droit de l'anglais inorder, preorder et postorder, et correspondent à différents types de parcours d'un arbre. Ne faudrait-il pas employer en français les termes infixe, préfixe et postfixe ? ♡ poème 16 aoû 2004 à 08:02 (CEST)

En effet, pour avoir suivi des cours là dessus, je connais les termes préfixe, postfixe ... mais rien des inordre, préordre ... Tipiac 16 aoû 2004 à 09:08 (CEST)

Je suis moi aussi des cours sur les arbres, mais l'enseignante utilise les termes inordre, préordre et postordre... Elle utilise les termes infixe, préfixe et postfixe pour parler des représentations d'expressions arithmétiques. (infixe = A+B-C; préfixe = -+ABC; postfixe = AB+C-) Louis 30 avr 2005 à 03:53 (CEST)

Je confirme pour achever le débat : les mots infixe, inordre, préfixe, préordre, postfixe, postordre existent (maintenant ca dépend du dictionnaire) et sont utilisés pour traiter des arbres. Je pense que le choix entre -ordre et -fixe doit être variable. Je ne pousse pas le débat en français mais je pense que vu la racine latine on devrait utiliser -fixe. Vlad2i 30 avr 2005 à 05:41 (CEST)

Un préordre est un concept très spécifique en mathématique (en français), c'est une relation réflexive et transitive, pour cela les anglais (fauf MathWorld) emploient quasi-order ou quasi-ordering, ce qui laisse libre prorder. Pierre de Lyon 22 février 2006 à 09:07 (CET)

[modifier] KD-tree, R-tree, R* -tree

en fait, si qq1 povait m'expliquer la différence entre les trois arbres....ça serait cool..ou peut etre un lien vers une bosse doc me serait bien util, tt ce que je trouve est en anglais et je gère pas trop... je laisse mon @ : lelofir@elv.enic.fr Merci d'avance.

[modifier] Algorithmes

Je viens de tomber sur la remarque concernant les termes "inordre", "postordre", et "préordre". Il me semble effectivement que ce ne sont pas les traductions exactes. Aussi ai-je pris la liberté de leur accoler "infixe", "postfixe", et "préfixe".

De plus, je tiens à faire une remarque au sujet des algorithmes de parcours originaux dans cet article: le fait qu'ils soient en anglais les rendent moins intuitifs. En ce qui me concerne, j'ai étudié ces parcours cette année et je dois dire que je n'y aurais rien compris si j'étais tombé sur ces algos il y a quelques mois... Aussi, je pense que ce serait bien, pour n'importe quel algo que ce soit, de privilégier une mise en forme francisée via un langage se rapprochant le plus possible du naturel. Ca n'en aide que mieux les néophytes à comprendre. De plus, on a alors l'avantage non négligeable de ne pas s'enfermer dans une structure de langage.

Julien

[modifier] homonymie

Je participe, comme d'autres, (si vous voulez participer, cliquer ici) à la redirection de liens d'articles homonymes (ex: Colbert vers Jean-Baptiste Colbert).

Le terme Racine (qui fait l'objet d'un lien) me semble être bien défini dans l'article et, par conséquent, ne pas avoir besoin de crochets.

A moins, à moins que Racine mérite un article particulier, mais là il faudrait le nommer (peut-être) [[Racine (Algorithmie)]]jpm2112 1 septembre 2005 à 20:39 (CEST)

[modifier] Définition d'un arbre binaire

Il me semble que la définition d'un arbre est incorrect. Le nœud 6 de la figure a un degré deux et pourtant on ne veut pas en faire la racine. De plus, sur cette figure les arcs ont une une pointe, ce qui monte bien que l'on veut parler de graphe orienté. Voici ce que je propose.

Un arbre binaire est un graphe orienté connexe et acyclique dont le degré sortant de chaque nœud est au plus deux. La racine est le seul nœud de degré entrant nul.

On peut noter qu'avec la définition ci-dessus, il y a toujours une et une seule racine. Pierre de Lyon (d) 27 novembre 2007 à 20:43 (CET)

[modifier] Parcours en profondeur

Il me semble qu'il y a petite erreur dans l'algo . Moi je le vois plutot comme ca :

ParcoursProfondeur(Arbre A) {
   S = Pilevide
   ajouter(Racine(A),S)
   Tant que (S != Pilevide) {
       nœud = premier(S)
       retirer(S)
       Visiter(nœud) //On choisit de faire une opération
       Si (gauche droite(nœud) != null) Alors
           ajouter(gauche droite(nœud),S)
       Si (droite gauche(nœud) != null) Alors
           ajouter(droite gacuhe(nœud),S)
   }
}

Omar86 | Niqash 15 décembre 2007 à 15:01 (CET)