Théorie des graphes

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

Introduction aux arbres binaires

Un arbre dont les éléments ont au plus 2 enfants est appelé un arbre binaire.
Étant donné que chaque élément d'un arbre binaire ne peut avoir que 2 enfants, nous les nommons généralement enfant gauche(sous arbre gauche) et enfant droit (sous arbre droit).

Contrairement aux tableaux, listes chaînées, piles et aux files d'attentes, qui sont des structures de données linéaires, les arbres sont des structures de données hiérarchiques.

Le nœud le plus haut est appelé la racine de l'arbre (root). Les éléments qui sont directement sous un élément sont appelés ses enfants. L'élément directement au-dessus de quelque chose est appelé son parent.. Par exemple, "D" est un enfant de "B" et "B" est le parent de "D".
Enfin, les éléments sans enfants sont appelés feuilles (D, E, F, G).

Pourquoi des arbres?

  • Une des raisons d'utiliser des arbres peut être parce que vous souhaitez stocker des informations qui forment naturellement une hiérarchie. Par exemple, le système de fichiers sur un ordinateur
  • Les arbres (avec un certain ordre, par exemple arbre Binaire de recherche) offrent (un accès/une recherche) plus rapides que la liste chaînée et plus lents que les tableaux.
  • Les arbres fournissent une insertion/suppression plus rapide que les tableaux et plus lente que les listes liées non ordonnées.
  • Comme les listes chaînées et contrairement aux tableaux, les arbres n’ont pas de limite supérieure en termes de nombre de nœuds, car les nœuds sont liés à l’aide de pointeurs.

Principales applications des arbres

  • Manipuler des données hiérarchiques.
  • Facilitez la recherche dans les informations
  • Manipuler des listes de données triées.
  • En tant que workflow pour composer des images numériques pour des effets visuels.
  • Algorithmes pour les routeurs
  • Forme d'une prise de décision en plusieurs étapes

Représentation D'arbre Binaire

Un arbre est représenté par un pointeur vers le nœud le plus haut dans l'arbre. Si l'arbre est vide, la valeur de la racine est nulle.

Un nœud contient les parties suivantes :

  1. données (l'information stockée dans l'arbre)
  2. Pointeur sur l'enfant gauche
  3. Pointeur sur l'enfant droit
                class Noeud: 
                    def __init__(self,key): 
                        self.gauche = None
                        self.droit = None
                        self.val = key
            
                    public class Noeud 
                    { 
                        int val; 
                        Noeud gauche, droit; 
                      
                        public Noeud(int key) 
                        { 
                            val = key; 
                            gauche = droit = null; 
                        } 
                    } 
            
                    struct Noeud  
                    { 
                      int val; 
                      struct Noeud *gauche; 
                      struct Noeud *droit; 
                    };
            







Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :