¿Cuáles son las propiedades de los árboles binarios?
Propiedad 1: Hay como máximo 2i-1 nodos en el i-ésimo nivel del árbol binario (i≥1).
Demostración: Supongamos que el árbol no está vacío y demuéstrelo mediante inducción matemática.
Base de inducción: cuando i = 1, todo el árbol binario tiene un solo nodo raíz. En este momento, 2i-1 = 20 = 1, se establece la conclusión.
Hipótesis de inducción: suponga que la conclusión se cumple cuando i = k, es decir, el número total de nodos en la k-ésima capa es como máximo 2k-1.
Ahora se demuestra que cuando i=k+1, se establece la conclusión. Debido a que el grado de cada nodo en el árbol binario es como máximo 2, el número total de nodos en el nivel k + 1 es como máximo el doble del número máximo de nodos en el nivel k, es decir, ¿2k-1 = 2? (k+1)-1, por lo que se establece la conclusión.
Propiedad 2: Un árbol binario con profundidad k contiene como máximo 2k-1 nodos (k≥1).
Prueba: Según la propiedad 1, el i-ésimo nivel tiene como máximo 2i-1 (1≤i≤k) nodos, por lo que el número total de nodos de un árbol binario con profundidad k es como máximo 221+...+2k-1= 2k-1 (piezas).
Propiedad 2: Para cualquier árbol binario T, si el número de nodos terminales es n0 y el número de nodos con grado 2 es n2, entonces n0=n2+1.
Prueba:
(1) Supongamos que el número total de nodos en el árbol binario es n, n1 es el número total de nodos con grado 1 en el árbol binario y el total El número de nodos en el árbol binario es igual al grado 0. Los nodos de grado más los nodos de grado 1 más los nodos de grado 2, entonces n=nn1+n2.
(2) Por otro lado, en un árbol binario, el nodo de primer grado tiene un hijo, el nodo de segundo grado tiene dos hijos y el nodo raíz no es hijo de ningún nodo. Por lo tanto, el número total de nodos es: n =n1+2n2+1.
(2) Resta las dos ecuaciones y obtén n0=n2+1 después de ordenar, por lo que se establece la conclusión.
Propiedad 4: La profundidad de un árbol binario completo con n nodos es "log2n#+1 o $log2(n+1), donde "log2n# significa tomar la parte entera menor o igual a " log2n#, $log2( n+1) significa tomar la parte entera mayor o igual a log2(n+1)
Prueba: suponga que la profundidad de un árbol binario completo con n nodos es k. Según la propiedad 2, se puede ver que el número total de nodos del árbol binario completo de nivel k-1 es n1 = 2k-1-1, y el número total de nodos del árbol binario completo de nivel k es n2. =2k-1 Por lo tanto, el número de nodos n del árbol binario completo obviamente satisface n1 Propiedad 5: para un árbol binario completo con n nodos. , numerados jerárquicamente de arriba a abajo y de izquierda a derecha, luego, para cualquier nodo numerado i (1≤i≤n) en el árbol binario: (1) Si i>1, entonces el número de serie del nodo padre del nodo i es "i/2#; si i=1, entonces el nodo i es el nodo raíz y no tiene nodo padre; (2) Si 2i≤n, entonces el número de secuencia del hijo izquierdo del nodo i es 2i Si 2i>n, entonces al nodo i no le quedan hijos. (2) Si 2i+1≤n, entonces el número de secuencia del hijo derecho del nodo i es 2i+1. Si 2i+1>n, entonces el nodo i no tiene hijo derecho. Esta propiedad se puede entender en el ejemplo de la Figura 6-8(b). Este es un árbol binario completo con una profundidad de 4 y un total de 12 nodos. Para el primer elemento, es obvio que cuando i=1, es el nodo raíz. Cuando i>1, por ejemplo, el nodo G tiene un número de secuencia de 7 y sus padres son "7/2#=2; el nodo I tiene un número de secuencia de 9 y sus padres son "9/2#=4. En segundo lugar, por ejemplo, el nodo H tiene un número de secuencia de 8. Debido a que 2?8=16 excede el número total de nodos, 12, al nodo H no le queda ningún hijo y es un nodo hoja. De manera similar, el número de secuencia del nodo F es 6, porque 2?6=12 es exactamente el número total de nodos, 12, por lo que su hijo izquierdo es el nodo L. Artículo 3, por ejemplo, el nodo I, su número de secuencia es 9, porque 2?9+1=19, que es mayor que el número total de nodos, 12, por lo que no tiene hijo derecho. El número de secuencia del nodo E es 5, porque 2?5 + 1 = 11 es menor que 12, por lo que su hijo derecho es el nodo K.