El árbol binario significa que el nodo puede tener un máximo de dos hijos. Aquí, el propio nombre binario sugiere que 'dos'; por lo tanto, cada nodo puede tener 0, 1 o 2 hijos.
Entendamos el árbol binario a través de un ejemplo.
El árbol anterior es un árbol binario porque cada nodo contiene como máximo dos hijos. La representación lógica del árbol anterior se proporciona a continuación:
En el árbol anterior, el nodo 1 contiene dos punteros, es decir, un puntero izquierdo y derecho que apunta al nodo izquierdo y derecho respectivamente. El nodo 2 contiene ambos nodos (nodo izquierdo y derecho); por lo tanto, tiene dos punteros (izquierdo y derecho). Los nodos 3, 5 y 6 son los nodos hoja, por lo que todos estos nodos contienen NULO puntero en las partes izquierda y derecha.
Propiedades del árbol binario
- En cada nivel de i, el número máximo de nodos es 2i.
- La altura del árbol se define como el camino más largo desde el nodo raíz hasta el nodo hoja. El árbol que se muestra arriba tiene una altura igual a 3. Por lo tanto, el número máximo de nodos en la altura 3 es igual a (1+2+4+8) = 15. En general, el número máximo de nodos posibles en la altura h es (20+ 21+ 22+….2h) = 2h+1-1.
- El número mínimo de nodos posibles a la altura h es igual a h+1 .
- Si el número de nodos es mínimo, entonces la altura del árbol será máxima. Por el contrario, si el número de nodos es máximo, entonces la altura del árbol sería mínima.
Si hay 'n' número de nodos en el árbol binario.
La altura mínima se puede calcular como:
Como sabemos eso,
norte = 2h+1-1
norte+1 = 2h+1
Tomando troncos por ambos lados,
registro2(n+1) = log2(2h+1)
registro2(n+1) = h+1
h = registro2(n+1) - 1
La altura máxima se puede calcular como:
Como sabemos eso,
norte = h+1
escáner siguiente
h= n-1
Tipos de árbol binario
Hay cuatro tipos de árbol binario:
1. Árbol binario completo/adecuado/estricto
El árbol binario completo también se conoce como árbol binario estricto. El árbol sólo puede considerarse como un árbol binario completo si cada nodo debe contener 0 o 2 hijos. El árbol binario completo también se puede definir como el árbol en el que cada nodo debe contener 2 hijos excepto los nodos hoja.
Veamos el ejemplo sencillo del árbol binario completo.
En el árbol anterior, podemos observar que cada nodo contiene cero o dos hijos; por lo tanto, es un árbol binario completo.
Propiedades del árbol binario completo
- El número de nodos hoja es igual al número de nodos internos más 1. En el ejemplo anterior, el número de nodos internos es 5; por lo tanto, el número de nodos de hoja es igual a 6.
- El número máximo de nodos es el mismo que el número de nodos en el árbol binario, es decir, 2h+1-1.
- El número mínimo de nodos en el árbol binario completo es 2*h-1.
- La altura mínima del árbol binario completo es registro2(norte+1) - 1.
- La altura máxima del árbol binario completo se puede calcular como:
norte= 2*h - 1
norte+1 = 2*h
funciones de cadena en java
h = norte+1/2
Árbol binario completo
El árbol binario completo es un árbol en el que todos los nodos están completamente llenos excepto el último nivel. En el último nivel, todos los nodos deben estar lo más a la izquierda posible. En un árbol binario completo, los nodos deben agregarse desde la izquierda.
Creemos un árbol binario completo.
El árbol anterior es un árbol binario completo porque todos los nodos están completamente llenos y todos los nodos del último nivel se agregan primero a la izquierda.
Propiedades del árbol binario completo
- El número máximo de nodos en un árbol binario completo es 2h+1- 1.
- El número mínimo de nodos en un árbol binario completo es 2h.
- La altura mínima de un árbol binario completo es registro2(norte+1) - 1.
- La altura máxima de un árbol binario completo es
Árbol binario perfecto
Un árbol es un árbol binario perfecto si todos los nodos internos tienen 2 hijos y todos los nodos hoja están al mismo nivel.
Veamos un ejemplo sencillo de un árbol binario perfecto.
listas de látex
El siguiente árbol no es un árbol binario perfecto porque todos los nodos de las hojas no están al mismo nivel.
Nota: Todos los árboles binarios perfectos son árboles binarios completos así como el árbol binario completo, pero viceversa no es cierto, es decir, todos los árboles binarios completos y los árboles binarios completos son árboles binarios perfectos.
Árbol binario degenerado
El árbol binario degenerado es un árbol en el que todos los nodos internos tienen un solo hijo.
Entendamos el árbol binario degenerado a través de ejemplos.
El árbol anterior es un árbol binario degenerado porque todos los nodos tienen un solo hijo. También se le conoce como árbol sesgado a la derecha, ya que todos los nodos tienen solo un hijo derecho.
El árbol anterior también es un árbol binario degenerado porque todos los nodos tienen un solo hijo. También se le conoce como árbol sesgado a la izquierda, ya que todos los nodos tienen solo un hijo izquierdo.
Árbol binario equilibrado
El árbol binario equilibrado es un árbol en el que tanto el árbol izquierdo como el derecho difieren como máximo en 1. Por ejemplo, AVL y Árboles rojo-negros Son árboles binarios equilibrados.
Entendamos el árbol binario equilibrado a través de ejemplos.
El árbol anterior es un árbol binario equilibrado porque la diferencia entre el subárbol izquierdo y el subárbol derecho es cero.
El árbol anterior no es un árbol binario equilibrado porque la diferencia entre el subárbol izquierdo y el subárbol derecho es mayor que 1.
Implementación del árbol binario
Un árbol binario se implementa con la ayuda de punteros. El primer nodo del árbol está representado por el puntero raíz. Cada nodo del árbol consta de tres partes, es decir, datos, puntero izquierdo y puntero derecho. Para crear un árbol binario, primero necesitamos crear el nodo. Crearemos el nodo definido por el usuario como se muestra a continuación:
struct node { int data, struct node *left, *right; } En la estructura anterior, datos es el valor, puntero izquierdo contiene la dirección del nodo izquierdo, y puntero derecho contiene la dirección del nodo derecho.
Programa de árbol binario en C
#include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } El código anterior llama a la función create() de forma recursiva y crea un nuevo nodo en cada llamada recursiva. Cuando se crean todos los nodos, se forma una estructura de árbol binario. El proceso de visitar los nodos se conoce como recorrido de árbol. Hay tres tipos de recorridos que se utilizan para visitar un nodo:
- recorrido en orden
- recorrido de preorden
- Recorrido del giro postal