¿Cuáles son los nodos terminales de un árbol binario?
En informática, un árbol binario es una estructura de árbol con como máximo dos subárboles por nodo. Por lo general, los subárboles se denominan "subárbol izquierdo" y "subárbol derecho". Los árboles binarios se utilizan comúnmente para implementar árboles de búsqueda binarios y montones binarios.
Un árbol binario con profundidad k y 2 k-1 nodos se llama árbol binario completo. La característica de este tipo de árbol es que el número de nodos en cada nivel es el mayor.
En un árbol binario, si todos los niveles excepto el último están llenos, y el último nivel está lleno o faltan varios nodos consecutivos a la derecha, el árbol binario es un árbol binario completo. La profundidad de un árbol binario completo con n nodos es piso (log2n) +1. Un árbol binario completo con profundidad k tiene al menos 2k-1 nodos de hoja y como máximo 2k-1 nodos.
Datos extendidos
Tipo:
1, árbol binario completo: si la altura del árbol binario es h, entonces todas las capas excepto la capa h (1 ~ h -1) El número de nodos alcanza el máximo. Hay nodos de hoja en la capa h. Los nodos de hoja están organizados de izquierda a derecha, que es un árbol binario completo.
2. Árbol binario completo: un árbol binario en el que cada nodo, excepto el nodo hoja, tiene un cotiledón izquierdo y derecho, con el nodo hoja en la parte inferior.
3. Árbol binario equilibrado: un árbol binario equilibrado también se denomina árbol AVL (diferente del algoritmo AVL). Es un árbol de clasificación binario con las siguientes propiedades: es un árbol vacío o el valor absoluto de la diferencia de altura entre sus subárboles izquierdo y derecho no excede 1, y los subárboles izquierdo y derecho son árboles binarios equilibrados.
Enciclopedia Baidu-Árbol binario