Partage

[C++] Creer un arbre binaire

Le 14 avril 2009 à 18:24:20

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
Publicité
Le 14 avril 2009 à 18:24:20
Le 14 avril 2009 à 19:49:40

Le 14 avril 2009 à 21:32:04

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 :p

bah sinon les arbre en informatique c'est pareil que les arbres en math, tu peux en faire tout ce que tu veux :p 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!
Le 14 avril 2009 à 21:57:17

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) ; ...
Le 14 avril 2009 à 22:20:19

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!!
Le 14 avril 2009 à 23:32:42

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;
}
Le 15 avril 2009 à 12:47:52

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.
Le 15 avril 2009 à 20:11:03

Merci je suis satisfait
Le 15 avril 2009 à 20:37:44

Va voir aussi du côté des fonctions récursives pour rechercher un éléments dans un arbre binaire.
Le 16 avril 2009 à 11:03:41

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...

[C++] Creer un arbre binaire

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
  • Editeur
  • Markdown