Le nombre de nœuds feuilles d'un arbre binaire complet

Un arbre binaire complet à n nœuds, le nombre de nœuds feuilles n0 est : n/2 arrondi vers le haut, ou (n+1)/2 arrondi vers le bas

Informations détaillées :

Arbre binaire complet

L'arbre binaire complet est une structure de données très efficace. Un arbre binaire complet est composé d'un binaire complet. arbre Et sorti. Pour un arbre binaire à n nœuds de profondeur K, on ​​parle d'arbre binaire complet si et seulement si chaque nœud correspond biunivoque aux nœuds numérotés de 1 à n dans l'arbre binaire complet de profondeur K.

Définition

Si la profondeur de l'arbre binaire est h, à l'exception du h-ème niveau, tous autres niveaux (1 ~ h-1) Le nombre de nœuds a atteint le nombre maximum et tous les nœuds du h-ème niveau sont continuellement concentrés sur le côté le plus à gauche. Il s'agit d'un arbre binaire complet.

Les arbres binaires complets sont dérivés d'arbres binaires complets. Pour un arbre binaire à n nœuds de profondeur K, on ​​parle d'arbre binaire complet si et seulement si chaque nœud correspond biunivoque aux nœuds numérotés de 1 à n dans l'arbre binaire complet de profondeur K.

(1) Tous les nœuds feuilles apparaissent au kème niveau ou au niveau k-l (les deux plus grands niveaux)

(2) Pour tout nœud, si son sous-arbre droit Le niveau maximum de est L, alors le niveau maximum de son sous-arbre gauche est L ou L+l.

Dans un arbre binaire, au plus, le degré des nœuds des deux niveaux inférieurs peut être inférieur à 2, et les nœuds du niveau inférieur sont tous concentrés dans les positions les plus à gauche du niveau, alors le l'arbre binaire devient complet Un arbre binaire dans lequel les nœuds du niveau le plus bas sont concentrés dans les positions les plus à gauche du niveau, et au dernier niveau, un certain nombre de nœuds à droite manquent, alors cet arbre binaire devient un arbre binaire complet .

Pour des articles plus techniques liés aux questions fréquemment posées, veuillez visiter la colonne FAQ pour en savoir 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!