Algoritmo de nodos de hojas de árboles binarios completos

Supongamos: el número de nodos con grado i es ni. De las propiedades de los árboles binarios, podemos saber:

n0 = n2 + 1……………………. ①Fórmula

n = n0 + n1 + n2………②Fórmula

De la fórmula ①, podemos obtener n2 = n0 - 1, y luego agregarlo a la fórmula ② para obtener:

n0 = (n + 1 - n1)/2

Se puede conocer a partir de las propiedades de un árbol binario completo:

Como se muestra en la figura, cuando n es un número par, n1 = 1, n0 = n / 2

Como se muestra en la figura, cuando n es un número impar, n1 = 0, n0 = (n + 1)/2

Combina las dos ecuaciones y escribe: n0 = ? (n+1)/2 ? (El signo de redondeo hacia abajo no se puede perder)

Información ampliada:

Características de un árbol binario completo:

1. Los nodos hoja solo pueden estar en el nivel más grande. Aparece en dos niveles.

2. Para cualquier nodo, si el nivel máximo de sus descendientes bajo la rama izquierda es l, entonces el nivel máximo de sus descendientes bajo la rama izquierda debe ser l o l+1.

Propiedades de un árbol binario completo:

1. La profundidad de un árbol binario completo con n nodos es?log?n?+1.

2. Si los nodos de un árbol binario completo con n nodos están numerados en orden jerárquico, entonces para cualquier nodo i, hay:

(1) Si i=1, entonces el nodo i es el nodo raíz del árbol binario y no tiene padres si i>1, entonces su padre es el nodo ?i/2?.

(2) Si 2i>n, entonces el nodo i no tiene ningún hijo izquierdo; de lo contrario, su hijo izquierdo es el nodo 2i.

(3) Si 2i+1>n, entonces el nodo i no tiene hijo derecho; de lo contrario, su hijo derecho es el nodo 2i+1.