Introduction aux arbres binaires

Un arbre c'est un graph acyclique, un arbre dont lequel chaque noeud a au plus 2 enfants est appelé un arbre binaire.
Étant donné que chaque noeud 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).

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

• 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

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; 
                    };