19 708 Pages

en informatique, un arbre ou structure arborescente (arbre en Anglais) Il est structure de données ce qui conduit à la notion de arbre avec racine présenter Théorie des graphes. Un arbre se compose de deux types de sous-structures de base: la nœud, qui contient généralement des informations, et l 'arc, l'établissement d'un lien entre deux noeuds hiérarchique: ceci est appelé un noeud parent d'où il sort un arc dirigé qui se connecte à un noeud enfant.

Il demande également que chaque nœud peut avoir au plus un arc entrant, alors que les différents noeuds peuvent sortir des arcs sortants de numéros différents. Enfin, il demande que l'arbre possède un noeud unique, dépourvu d'arc entrant: ce noeud est dit racine (racine) Arbre. Chaque nœud qui n'a pas d'arcs sortants est dit feuille (noeud feuille) Et dans chaque arbre fini, qui est, avec un nombre fini de nœuds, il y a au moins un noeud de feuille. De toute évidence, un nœud peut être simultanément père (si elle a des arcs sortants) et fils (si elle a un arc entrant, ou si elle est différente de la racine).

En général, chaque nœud apporte des informations et très souvent une clé avec laquelle il peut être identifié de manière unique dans l'arborescence. L 'hauteur ou profondeur l'arbre est le maximum des longueurs de son plafonds de marche, chemins allant des racines aux feuilles.

types d'arbres

Arbre (informatique)
Un arbre commandé binaire

Principalement des arbres sont divisés en arbres désordonnées et ordonnés arbres. Le premier ne suivent pas les règles concernant les relations parent-enfant, alors que celui-ci exige que entre le noeud parent et l'enfant nœuds il y a une loi spécifique. Les plus couramment utilisés en informatique sont certainement ordonnés arbres. peut être une autre classification en fonction du nombre maximum d'enfants d'un nœud peut avoir. On peut donc parler de Les arbres binaires dans lequel chaque noeud peut avoir au maximum deux enfants, ou Les arbres n-aires où il y a une limite au nombre maximum de nœuds enfants.

Une caractérisation plus poussée est celle qui est basée sur la soi-disant équilibre: un arbre est parfaitement équilibré si elle a toutes les feuilles au même niveau, ou si chaque feuille de l'arbre a la même distance de la racine. Un arbre est -équilibré si, pour chaque noeud N, dire K fixer des teneurs maximales atteint à la suite de toutes les feuilles N, la différence entre le maximum et le minimum de K Il ne dépasse pas .

L'ensemble de noeuds au-dessus d'un noeud comprend l'ensemble des prédécesseurs, ceux qui suivent sont les descendants.

Les types d'arbres les plus courants sont les suivants:

mises en œuvre

La mise en œuvre la plus commune des arbres est basée sur listes chaînées, ou par des objets (nœuds) qui font référence à d'autres objets.

Java

typique d'un noeud d'une interface arbre binaire en Java Il peut être la suivante:

public classe nœud {
public nœud figlioSinistro;
public nœud figlioDestro;
// les informations du noeud, de type objet à généralisent
public objet information;
// une clé unique pour identifier le nœud, par exemple dans son ensemble
public int chiaveUnivoca;
}

Notoirement, les arbres tas Ils peuvent être mis en œuvre aussi par tableau ou transporteurs

C

  • une structure définissant
typedef int TKey;
typedef int OESR;
struct sInfo{
TKey clé;
OESR satellite;
};
typedef struct sInfo TINFO;
struct Snøde {
TINFO d'info;
struct Snøde *gauche;
struct Snøde *droit;
};
typedef struct Snøde TNODE;
typedef TNODE* Ttree;
  • Créer arbre
Ttree tree_create() {
retour NULL;
}
  • arbre Destruction
Ttree tree_destroy(Ttree arbre) {
si(tree_empty(arbre)==faux)
retour NULL;
d'autre si((arbre->gauche==NULL)  (arbre->droit==NULL)) {
gratuit(arbre);
retour NULL;
} d'autre {
arbre->gauche = tree_destroy(arbre->gauche);
arbre->droit = tree_destroy(arbre->droit);
gratuit(arbre);
retour NULL;
}
}
  • élément de recherche
TNODE* tree_search_recursive(Ttree arbre, TKey clé) {
si((tree_empty(arbre)==faux) || égal(arbre->d'info.clé, clé))
retour arbre;
d'autre {
si(plus grand(clé, arbre->d'info.clé))
retour tree_search_recursive(arbre->droit, clé);
d'autre
retour tree_search_recursive(arbre->gauche, clé);
}
}
  • Insérer un élément
Ttree tree_insert_recursive(Ttree arbre, TINFO d'info) {
si(tree_empty(arbre)==faux) {
TNODE* newnode;
newnode=(TNODE*) malloc(sizeof(TNODE));
si(newnode==NULL) {
printf(« Échec d'allocation »);
sortie(1);
}
newnode->droit=newnode->gauche=NULL;
newnode->d'info=d'info;
retour newnode;
} d'autre si(!plus grand(d'info.clé,arbre->d'info.clé)) {
arbre->gauche=tree_insert_recursive(arbre->gauche,d'info);
retour arbre;
} d'autre {
arbre->droit=tree_insert_recursive(arbre->droit,d'info);
retour arbre;
}
}
  • supprimer l'élément
Ttree tree_delete_ver2(Ttree arbre, TKey clé) {
si(tree_empty(arbre)==faux)             / * Arbre Empty * /
retour NULL;
d'autre si(plus grand(arbre->d'info.clé, clé)) {
/ * Suppression de la branche gauche * /
arbre->gauche=tree_delete_ver2(arbre->gauche, clé);
retour arbre;
}
d'autre si(plus grand(clé, arbre->d'info.clé)) {
/ * Suppression de la branche droite * /
arbre->droit=tree_delete_ver2(arbre->droit, clé);
retour arbre;
} d'autre {                            /*tree->info.key==key * /
/ * Supprimer de la racine * /
TNODE* min_right, *alias;
si(tree_empty(arbre->droit)==faux)
alias=arbre->gauche;
d'autre {
min_right=tree_min(arbre->droit);
min_right->gauche=arbre->gauche;
alias=arbre->droit;
}
gratuit(arbre);
retour alias;
}
}

Visitez les arbres profonds

beaucoup algorithmes opérant sur les arbres nécessitent de visiter tous les noeuds de l'arbre, ou de définir un algorithme (sous-) qui reçoit un arbre construit permutation tous ses nœuds. les méthodes profondeur première recherche Ils sont les suivants.

  • visite de pré-commande: La racine est visité d'abord, après la sous-arbre gauche, et enfin le sous-arbre droit
vide visitapreordine(Nodepointer début)
{
si (début == NULL) retour;
début->balisage = 1;
printf("% %\n", début->valeur, début->balisage);
visitapreordine(début->son_sx);
visitapreordine(début->son_dx);
}

Nodepointer Il est un pointeur vers le nœud racine d'où la recherche de pré-commande. son_sx et son_dx Ils sont respectivement les enfants à gauche et à droite du noeud à partir duquel la recherche. L'algorithme décrit est limitée à imprimer à la vidéo la valeur et le balisage du noeud considéré.

  • visite pour: Tout d'abord vient visité le sous-arbre gauche, puis la racine, et enfin le sous-arbre droit
vide visitainordine(Nodepointer début)
{
si (début == NULL) retour;
visitainordine(début->son_sx);
début->balisage = 1;
printf("% %\n", début->valeur, début->balisage);
visitainordine(début->son_dx);
}

Nodepointer est un pointeur vers le nœud racine de l'endroit où la recherche dans l'ordre. son_sx et son_dx Ils sont respectivement les enfants à gauche et à droite du noeud à partir duquel la recherche. L'algorithme décrit est limitée à imprimer à la vidéo la valeur et le balisage du noeud considéré.

  • visite de Post-commande: Il est d'abord visité le sous-arbre gauche, puis la droite et à la fin de la racine
vide visitapostordine(Nodepointer début)
{
si (début == NULL) retour;
visitapostordine(début->son_sx);
visitapostordine(début->son_dx);
début->balisage = 1;
printf("% %\n", début->valeur, début->balisage);
}

Nodepointer est un pointeur vers le noeud racine à partir duquel la recherche dans la post-commande. son_sx et son_dx Ils sont respectivement les enfants à gauche et à droite du noeud à partir duquel la recherche. L'algorithme décrit est limitée à imprimer à la vidéo la valeur et le balisage du noeud considéré.

Chaque procédé est appliqué de telle sorte récursif, à-dire pour « approuver un sous-arbre », on entend appliquer le même algorithme pour visiter le nœud racine de ce sous-arbre.

Un exemple d'un procédé pas visite récursive d'un arbre à la place donnée par largeur.

Articles connexes

  • Arbre (graphique)
  • Arbre équilibré

D'autres projets

  • Il contribue à Wikimedia Commons Wikimedia Commons: Il contient des images ou d'autres fichiers arbre
fiber_smart_record Activités Wiki:
Aidez-nous à améliorer Wikipedia!
aller