Comment compter les nœuds d'un arbre binaire

1. Le i-ième niveau de l'arbre binaire a au plus 2^(i-1) nœuds

2 L'arbre binaire de profondeur h a au plus. most 2^k- 1 nœud

3. Pour un arbre binaire, s'il contient n0 nœuds feuilles et n2 nœuds de degré 2, il doit y avoir une relation : n2=n0-1

4. La profondeur d'un arbre binaire complet à n nœuds est [log2n]+1.[] signifie arrondir

5 Si la profondeur d'un arbre binaire complet à n nœuds est de haut en bas et de gauche. En numérotant de 1 à n vers la droite, puis pour tout nœud numéroté i dans l'arbre binaire complet :

Si i=1, alors le nœud est la racine de l'arbre binaire et n'a pas de parents Sinon, le. number is Le nœud [i/2] est son nœud parent ;

Si 2i>n, alors le nœud n'a pas de nœud enfant gauche, sinon, le nœud numéroté 2i est son nœud enfant gauche

Si 2i+1>n, alors le nœud n'a pas de nœud enfant droit, sinon, le nœud numéroté 2i+1 est son nœud enfant droit.

Si le nombre de nœuds d'un arbre binaire complet est n, trouvez la hauteur h de n0, n1, n2, le nombre de nœuds enfants gauches nl et le nombre de nœuds enfants droits nr ?

(n0 est un nœud de degré 0, n1 est un nœud de degré 1, n2 est un nœud de degré 2)

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!