Formules d'arbre binaire que vous devez comprendre

1. Propriétés des arbres binaires généraux

Propriétés 1. Au niveau i d'un arbre binaire non vide, il y a au plus 2^i nœuds.

Propriété 2. Dans un arbre binaire de hauteur K, il y a au plus 2^(k+1)-1 nœuds.

Propriété 3. Pour tout arbre binaire non vide, si le nombre de nœuds feuilles est n0 et le nombre de nœuds de degré 2 est n2, alors n0=n2+1.

2, Arbre binaire complet

Définition : Si dans un arbre binaire, seuls les degrés des nœuds aux deux niveaux inférieurs sont inférieurs à 2, les degrés de les nœuds à tous les autres niveaux sont égaux à 2, et les nœuds de la couche inférieure sont concentrés dans les positions les plus à gauche de la couche, alors cet arbre binaire est appelé un arbre binaire complet.

Propriété 1. La hauteur k d'un arbre binaire complet à n nœuds est [log^2n].

Propriété 2. Pour un arbre binaire complet avec n nœuds, si tous les nœuds de l'arbre binaire sont séquencés du haut (nœud racine) vers le bas (nœud feuille) et de gauche à droite, la numérotation commence de 0 à n-1, alors pour tout nœud dont l'indice est i, il y a :

(1) Si i=0, alors c'est le nœud racine et il n'a pas de nœud parent ; l'indice de son nœud parent est (i-1)/2.

(2) Si 2i+1<=n-1, alors l'indice du nœud enfant gauche du nœud d'indice i est 2i+1 sinon, le nœud d'indice i n'a pas d'enfant gauche ; nœud.

(3) Si 2i+2<=n-1, alors l'indice du nœud enfant droit du nœud d'indice i est 2i+2 sinon, le nœud d'indice i n'a pas d'enfant droit ; nœud.

3. Arbre binaire complet

Définition : Si un nœud d'un arbre binaire est soit une feuille, soit possède deux sous-arbres non vides, alors cet arbre binaire est appelé Arbre binaire complet.

Propriété, dans un arbre binaire complet, le nombre de nœuds feuilles est 1 de plus que le nombre de nœuds de branche.

4. Arbre binaire étendu

Définition : Un arbre binaire étendu est une expansion d'un arbre binaire existant. Après expansion, les nœuds de l'arbre binaire d'origine deviennent des branches. avec degré 2. nœud. C'est-à-dire que si le degré du nœud d'origine est 2, il restera inchangé ; si le degré est 1, alors une branche sera ajoutée ; si le degré est 0, alors deux branches seront ajoutées ;

Propriété 1. Dans un arbre binaire étendu, le nombre de nœuds externes est 1 de plus que le nombre de nœuds internes.

Propriété 2. Pour tout arbre binaire étendu, la relation suivante est satisfaite entre la longueur du chemin externe E et la longueur du chemin interne I : E=I+2n, où n est le nombre de nœuds internes.

Pour des articles plus techniques liés aux questions fréquemment posées, veuillez visiter la colonne FAQ pour en savoir plus plus!

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!