5 propriétés des arbres binaires

L'arbre binaire possède les cinq propriétés suivantes :

1. l'arbre binaire Une couche a au plus 2＾(i - 1) nœuds.

2. Un arbre binaire de profondeur k (k>=0) a au moins k nœuds et au plus 2＾k-1 nœuds.

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

4. La profondeur d'un arbre binaire complet à n nœuds est int_UP (log(2,ｎ+1)).

5. Si un arbre binaire complet avec n nœuds est construit de haut en bas, les nœuds d'une même couche sont numérotés 1, 2, 3 en continu de gauche à droite. ． ． ． ． ． , n, puis stockez chaque nœud de l'arborescence séquentiellement dans un tableau unidimensionnel en fonction de ce numéro de nœud, et appelez le nœud numéroté i comme nœud i (i>=1 && i<=n), alors il y a ce qui suit relation :

(1) Si i = 1, alors le nœud i est la racine et n'a pas de nœud parent ; si i> 1, alors le nœud parent du nœud i est le nœud int_DOWN (i / 2 ); 🎜>

(2) Si 2*i <= n, alors l'enfant gauche du nœud i est le nœud 2*i

(3) Si 2*i (4) Si le numéro de nœud i est un nombre impair, et i! =1, il est dans la position frère droit, alors son frère gauche est le nœud i-1

(5) Si le numéro de nœud i est un nombre pair, et i! =n, il est en position frère gauche, alors son frère droit est le nœud i+1

(6) Le niveau du nœud i est int_DOWN (log (2, i)) + 1;

Preuve de certaines propriétés

La propriété 1 peut être prouvée par induction mathématique

Preuve de la propriété 2 :

Preuve de la propriété 1 On peut voir que le nombre total maximum de nœuds dans la couche k peut être exprimé par 2＾0＋2＾ 1＋...+2^ (ｋ-1) = 2^k- 1

Preuve de propriété ; 3 :

Tout d'abord, du point de vue des nœuds, n1 + n2 + n0 = n, soit l'équation (1)

Du point de vue des arêtes, n2 est connecté à ; deux arêtes, n1 est connecté à une arête et n nœuds sont connectés par paires ayant besoin de ｎ-1 côtés, nous pouvons obtenir 2＊ｎ2＋ｎ1=ｎ-1, qui est la formule (2)

 ; (1)-(2), on peut obtenir -n2=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!