Bonsoir les zeros.
J'ai entendu parler d'arbre binaire en c++.
J'ai fait des recherches mais je n'ai pas encore
compris concretement le concept, a quoi ils
peuvent servir. J'aimerais bien trouver un tutoriel
bien détaillé sur cela. Merci a toute personne
qui voudrait bien m'aider

http://fr.wikipedia.org/wiki/Arbre_binaire

alors pour faire un arbre et nle parcourir il y a plusieurs méthodes, il faut que tu definisse une structure Noeud, et dans cette structure tu met deux pointeurs vers des Noeuds.

typedef struct Noeud
{
    //un arbre d'entiers
    int entier;
    struct Noeud * sous_arbre_gauche;
    struct Noeud * sous_arbre_droit;
}Noeud;

en C++ c'est pareil sauf que tu utilise des classes mais c'est le meme principe un pointeur ver un noeud gauche et ver un noeud droit
apres pour parcourir ton arbre c'est une autre histoire, tu as le parcour Ordre preordre et postordre parcour en largeur avec une file
parcour en profondeur etc...cherche sur google

bah sinon les arbre en informatique c'est pareil que les arbres en math, tu peux en faire tout ce que tu veux mais si tu veux stocker de l'information et récuprer ca rapidement je te conseil plutot les tables de hachages c'est ce qu'il y a de mieux!

J'implémenterais plutôt ça comme ça :

class arbre_binaire
{
   public : // blabla...
   private :
    arbre_binaire* gauche;
    arbre_binaire* droit;
};

On part donc d'une définition qui me fait penser à la programmation fonctionnelle : un arbre binaire est soit rien, soit un élément suivi de deux arbres binaires. Mais bon, il est vrai que la séparation "noeud" <> "arbre" peut être pratique, à toi de voir.

Regarde aussi du côté des arbres binaires de recherche ou des tas (la STL propose une structure de tas : la file de priorité, c'est la classe std::priority_queue), c'est intéressant.

popo_joe : Pour la recherche d'un élément dans un arbre binaire, on peut profiter de la nature de l'arbre binaire. Pour un arbre binaire quelconque : O(n) ; Pour un arbre binaire de recherche : O(log n) ; ...

ShareMan : pourquoi mettre les pointeurs sur les ss arbres en private? c'est pas plus pratique de les mettre en publique?
et sinon oui je suis d'accor avec toi , mais bon, les arbres c'est compliqué, les ABOH les AVL, equilibrer les arbres et tout, oulala ca fait mal a la tete tout ca :/ j'ai eu des exams ya pas lgtmps la dessus j'en fait encor des cauchemards!!

Surtout pas publique !

Faut pas pouvoir faire n'importe quoi avec les pointeurs !

Tu as des méthodes qui ordonnent tout ça comme il faut pour pas qu'il y est d'erreurs.

<template T>
class Noeud
{
    public :

        Noeud();

        Noeud& Add(const T&);
        // ajoute proprement le noeud là
        // où il faut.

        void Remove(const T&);
        // supprime proprement le noeud où se trouve
        // la valeur concernée.

        Noeud& Find(const T&);
        // renvoie le noeud où se trouve
        // la valeur concernée.

        Noeud& Lowest();
        // renvoie le noeud où se trouve
        // la plus petite valeure.

        Noeud& Highest();
        // renvoie le "noeud" où se trouve
        // la plus grande valeure.

        Noeud& Next();
        // renvoie le "noeud" où se trouve
        // la valeur suivante (dans l'ordre croissant).

        Noeud& Previous();
        // renvoie le "noeud" où se trouve
        // la valeur précédente (dans l'ordre croissant).

        const T& GetData() const;
        // renvoie la valeur détenue par le noeud.

        // etc, celon tes besoins.

        ~Noeud();

    private :

        Noeud* _Left;
        Noeud* _Right;

        T      _Data;
}

Citation : popo_joe

ShareMan : pourquoi mettre les pointeurs sur les ss arbres en private? c'est pas plus pratique de les mettre en publique?

C'est relatif. Un type qui code plutôt en fonctionnel ou en impératif aura en premier lieu tendance à trouver cela plus "pratique". Le problème, c'est que l'on est ici dans le paradigme de l'orienté objet. En gros, on considère l'arbre comme un objet. Par principe, tout ce avec quoi nous pouvons interagir est une "interface" composée de méthodes publiques. Et ce sont justement elles qui manipulent les pointeurs dans le cas de l'arbre, ici.

Merci je suis satisfait

Va voir aussi du côté des fonctions récursives pour rechercher un éléments dans un arbre binaire.

Bonjour à tous,
ce topic me rappelle les difficultés que j'ai eu quand j'ai voulu coder les arbres binaires en C++ : comment fait on pour coder l'arbre Vide ?
Parce que je suis d'accord il faut mettre :

fg = NULL;
fd = NULL;

mais la racine, à quoi doit elle être égale?
Je me rappelle que lorsque je les avais codé, j'avais pris par convention racine = 0, mais ce n'est pas super je trouve...

Bonjour

Je ne sais pas comment faire un arbre binaire pour faire un arbre de talent pour mon jeu video --'

Une idée ?

Si tu ne sais pas faire d'arbre binaire, ne fait pas de jeu vidéo.

Raakz a écrit:

Si tu ne sais pas faire d'arbre binaire, ne fait pas de jeu vidéo.

J'irai même plus loin, si tu ne vois pas comment implémenter un arbre binaire, tu n'as pas le niveau pour espérer réussir à faire un jeu vidéo qui tienne la route. Par ailleurs, l'arbre binaire n'est probalement pas adapté à la création d'un arbre de talents, l'arbre de talent c'est le boulot du game designer, pas celui du programmeur, le boulot du programmeur ici, c'est de permettre au game designer de concevoir son arbre de talent comme il veut, et un game designer qui se limiterait à un arbre binaire ferait preuve d'un indiscutable manque d'imagination et de créativité.