Scribd
Importer
5 vues8 pages

Types d'arbres et parcours associés

Le document présente les différents types d'arbres en informatique, tels que les arbres complets, ordonnés et binaires, ainsi que leurs caractéristiques. Il décrit également les concepts de taille et de niveau d'un arbre, ainsi que les arbres n-aires et les méthodes de parcours, y compris le parcours en profondeur et en largeur. Ces informations sont essentielles pour comprendre la structure et la manipulation des données hiérarchiques.

Transféré par

Abakar Abdoulaye
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
5 vues8 pages

Types d'arbres et parcours associés

Le document présente les différents types d'arbres en informatique, tels que les arbres complets, ordonnés et binaires, ainsi que leurs caractéristiques. Il décrit également les concepts de taille et de niveau d'un arbre, ainsi que les arbres n-aires et les méthodes de parcours, y compris le parcours en profondeur et en largeur. Ces informations sont essentielles pour comprendre la structure et la manipulation des données hiérarchiques.

Transféré par

Abakar Abdoulaye
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

ARBRE

Realisé par:

HAWA MAHAMAT TAHIR MOUSSA ABDOULAYE IBEDALLAH


Type d’arbre
Les types d’arbres sont:
• Arbre complet: un arbre est complet si toutes ces feuilles sont sur le même
niveau;
• Arbre ordonné est un arbre dans lequel les noeuds respectent un ordre bien
détermine.
• Arbre binéaire c’est un arbre où le degré maximum d’un noeud est inférieur
ou égal à 2.
• Arbre binéaire ordonné :c’est un arbre où :
o Tout élément à gauche de la racine est inférieur à la valeur de la racine
o Tout élément à droite de la racine est supérieure à la valeur de la racine;
o Cette propriété doit être vérifiée recrusivement à tous les niveaux pour que
l’arbre binéaire soit ordonné
Arbre
Un arbre est une structure des données non lineaires sert à mémoriser des données
d’une manière hiérarchique.
C’est un graphe sans cycle où chaque noeud a au plus prédecesseur.
De manière plus simple, il est constitué d’élément que l’on appel souvent de noeud ou
Sommet telque:
• Le prémier noeud s’appel racine
• Un noeud peut avoir 0,1 ou plusieur sous noeuds(fils)
• Un fils n’a qu’un seul père
• Les feuilles sont des noeud qui sont au bout des branches et qui n’ont pas des fils
• Taille d’un arbre
C’est le nombre de noeud qu’il possède.
Un arbre vide est de taille égale à 0.

• Niveau d’un noeud


Le niveau de la racine = 0,
Le niveau de chaque noeud est égale au niveau de son père plus 1.
Arbre N-aires
Un arbre n-aire est un arbre dans lequel chaque noeud a un nombre
quelconque de fils. On peut utiliser un arbre n-aire pour représenter
un dictionnaire et ainsi accélérer la recherche. La racine a autant de fils
que de premières lettres possibles, puis chacun de ces fils autant de fils
que de seconde lettre possible, etc. Pour représenter un tel arbre, une
solution consiste à attacher à chaque noeud deux liens : un lien vers
son premier fils et un lien vers son frère.
Les parcours d’un arbre
Le parcours d’un arbre consiste à passer par tous ses noeuds. Le
parcours permet d’éffectuer tout un ensemble de traitement sur les
arbres. Par ailleurs on distingue deux types de parcours:
Parcours en profondeur et parcours en largeur.
Parcours en profondeur
Dans le Parcours en profondeur, on déscend le plus profondement
possible dans l’arbre puis, une fois qu’une feuille a été atteint , on
rémonte pour explorer les autres branches en commençant par la
branche la plus base parmi celles n’ont pas encore parcourus.
Dans le parcours en profondeur, il existe principalement 3 types de
parcours:
• Prefixé
• Infixé
• Post fixé
parcours en largeur
• Le parcours en largeur, aussi appelé "parcours en largeur d'abord, est
un algorithme de recherche utilisé pour parcourir un arbre de
manière systématique. L'idée est de visiter tous les voisins d'un nœud
avant de passer aux nœuds voisins de ces voisins.
• Le parcours en largeur est souvent utilisé pour trouver le plus court
chemin entre deux nœuds dans un graphe non pondéré, pour
détecter les cycles dans un graphe, ou pour trouver tous les nœuds
accessibles à partir d'un nœud donné.

Vous aimerez peut-être aussi