A quoi servent les arbres binaires ?

Les arbres binaires peuvent être utilisés pour implémenter des arbres de recherche binaires et des tas binaires. En informatique, un arbre binaire est une structure arborescente avec au plus deux sous-arbres par nœud. Le sous-arbre est généralement appelé « sous-arbre gauche » et. "sous-arbre droit", qui peut être divisé en : 1. Arbre binaire complet ; 2. Arbre binaire complet 3. Arbre binaire équilibré selon différentes utilisations ;

Le rôle des arbres binaires

Les arbres binaires sont souvent utilisés pour implémenter des arbres de recherche binaires et des arbres binaires. des tas.

En informatique, un arbre binaire est une structure arborescente comportant au plus deux sous-arbres par nœud. Habituellement, les sous-arbres sont appelés « sous-arbre gauche » et « sous-arbre droit ».

Selon différentes utilisations, il peut être divisé en :

1. Arbre binaire complet - si la hauteur de l'arbre binaire est h, à l'exception du h-ème niveau, tous les autres niveaux. (1 ~ h-1) Le nombre de nœuds a atteint le nombre maximum. Il y a des nœuds feuilles dans la h-ième couche, et les nœuds feuilles sont disposés de gauche à droite.

2. Arbre binaire complet - un arbre binaire dans lequel chaque nœud, à l'exception des nœuds feuilles, a des sous-feuilles gauche et droite, et les nœuds feuilles sont tous en bas.

3. Arbre binaire équilibré - Un arbre binaire équilibré est également appelé arbre AVL (différent de l'algorithme AVL). Il s'agit d'un arbre de tri binaire et possède les propriétés suivantes : c'est un arbre vide ou son arbre binaire. la valeur absolue de la différence de hauteur entre les sous-arbres gauche et droit ne dépasse pas 1, et les sous-arbres gauche et droit sont des arbres binaires équilibrés.

Informations étendues

Un arbre binaire de profondeur h a au plus un nœud (h>=1) et au moins h nœuds. Pour tout arbre binaire, si le nombre de nœuds feuilles est N0 et le nombre total de nœuds de degré 2 est N2, alors N0=N2+1.

Si chaque nœud d'un arbre binaire complet avec N nœuds est stocké de manière séquentielle, les nœuds ont la relation suivante : Si I est le numéro du nœud, alors si I>1, alors son nœud parent Le numéro est I/2. Si 2*IN, il n’y a plus d’enfant. Si 2*I+1

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!