Leer archivo en un árbol de búsqueda binario usando C++
- Árbol de búsqueda binaria en C++
- Inserción en árbol de búsqueda binaria en C++
- Eliminación en árbol de búsqueda binario en C++
- Lea el archivo en un árbol de búsqueda binario en C++
Este tutorial analizará la lectura del archivo en un árbol de búsqueda binaria en C++. Primero, discutiremos rápidamente el árbol de búsqueda binaria y su funcionamiento.
Más adelante veremos cómo leer el archivo en un árbol de búsqueda binario.
Árbol de búsqueda binaria en C++
El árbol de búsqueda binario es un árbol binario con una disposición especial de nodos, que luego ayuda en la búsqueda. Vale la pena mencionar aquí que las estadísticas muestran que más del 90% de las operaciones son operaciones de búsqueda, mientras que; menos del 10% de las operaciones incluyen insertar, actualizar, eliminar, etc.
En el árbol de búsqueda binaria, cada nodo se coloca de manera que el nodo sea siempre más grande que su hijo izquierdo y más pequeño que igual (en caso de duplicación) a su hijo derecho.
Esta definición se aplica recursivamente a cada nodo del árbol. Por lo tanto, siempre tenemos una raíz mayor que todos los nodos de su subárbol izquierdo y menor que igual a todos los nodos de su subárbol derecho.
5 / 3 8 / \ / 1 2 6 9
Aquí puede ver un ejemplo de un árbol de búsqueda binaria, que se explica por sí mismo; como antes, un árbol de búsqueda binario ayuda en la operación de búsqueda.
Por ejemplo, si queremos buscar 7 (dígalo clave) en el árbol de arriba. Compararemos la clave con el nodo raíz 5.
La clave es más grande que el elemento raíz; por lo tanto, tenemos que buscar la clave en el subárbol derecho solo porque todos los valores en el subárbol izquierdo son más pequeños que el nodo raíz.
A continuación, compararemos la clave con 8 y nos moveremos hacia el subárbol izquierdo de 8 porque la clave es más pequeña que 8. A continuación, compararemos 6 con la clave y nos moveremos hacia el subárbol derecho de 6.
A la derecha de 6, tenemos NULL; por lo tanto, detendremos el elemento no encontrado. Hicimos comparaciones de 3 en lugar de 6.
Cuantos más elementos tengamos en el árbol, la proporción de comparaciones con el total de elementos en el árbol se reducirá aún más. La búsqueda parece trivial; sin embargo, le daremos el código completo más adelante.
Antes de presentar el código completo, analicemos las operaciones de inserción y eliminación en el BST. Sin embargo, es mejor ver primero la definición de la clase Nodo.
template <class T>
class Node {
public:
T data;
Node* left;
Node* right;
Node(T data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
Aquí, hemos usado una plantilla para usar el mismo árbol para cualquier tipo de datos. Le mostraremos su beneficio cuando usemos nuestro BST.
En nuestra definición de la clase Nodo, tenemos datos del tipo plantilla, que podemos seleccionar en el momento de la creación del objeto. Tenemos punteros izquierdo y derecho, ya que implementaremos nuestra implementación vinculada a los árboles.
En el constructor, además de los datos, asignamos NULL a los punteros izquierdo y derecho porque cada nuevo nodo en el inicio no tiene nodos secundarios izquierdo y derecho.
Inserción en árbol de búsqueda binaria en C++
Considere la inserción del nuevo elemento en el BST. Hay dos casos posibles: el árbol está vacío o tiene uno o más nodos.
El primer caso es que el árbol está vacío; el nuevo elemento se convertirá en el nodo raíz del árbol después de esta inserción. En el segundo caso, el nuevo nodo se convertirá en hijo izquierdo o derecho de algún nodo existente.
Por lo tanto, comenzaremos desde el nodo raíz, comparando el valor del nodo con nuestro nuevo valor; nos moveremos a la izquierda del nodo actual oa la derecha del nodo actual.
Finalmente, llegaremos a un punto donde tenemos NULL (sin nodo); crearemos un nuevo nodo y lo convertiremos en un hijo izquierdo o derecho de acuerdo con los valores del nodo y del nuevo nodo.
Por ejemplo, si insertamos el nodo 7 en el BST, el nuevo BST será:
5 / 2 8 / \ /
1 3 6 9
7
Comenzando desde el nodo raíz, 5 es más pequeño que 7, así que muévase hacia la derecha. 8 es más grande, por lo que nos movemos hacia el lado izquierdo. 6 es más pequeño; por lo tanto, muévase a la derecha.
A la derecha, no hay ningún nodo, así que creamos un nuevo nodo y lo convertimos en el hijo derecho del nodo 6. Veremos la implementación de la función de inserción, pero antes de eso, veamos la definición de la clase BST.
template <class T>
class BST {
Node<T> *root;
public:
BST() { root = NULL; }
...
Una vez más, hemos creado una clase de plantilla para BST, con solo el miembro de datos raíz de tipo Node<T>. En el constructor, hemos asignado NULL al nodo raíz, lo que significa que el árbol está vacío.
Por tanto, en caso de eliminación, siempre que eliminemos el último nodo, asignaremos NULL al nodo raíz. Veamos la función insertar.
Node<T>* insert(T key) { root = insert(root, key); }
Node<T>* insert(Node<T>* temp, T key) {
if (temp == NULL) return new Node<T>(key);
if (temp->data > key)
temp->left = insert(temp->left, key);
else
temp->right = insert(temp->right, key);
return temp;
}
Primero, tenemos una función contenedora para llamar a la función caballo de batalla, que realiza la tarea de inserción. La razón para escribir la función contenedora es que, por razones de seguridad, no queremos dar acceso al nodo raíz fuera de la clase.
Haga clic en función contenedora si desea obtener información sobre las funciones contenedoras.
En nuestra función de caballo de batalla, tenemos una implementación recursiva, donde el caso base es un nodo NULO, donde crearemos un nuevo nodo y devolveremos su dirección a la persona que llama, que asignará esta dirección al hijo izquierdo o derecho para vincular el nuevo nodo en el árbol.
Si no tenemos un nodo NULL, compararemos los datos y nos moveremos hacia la derecha o hacia la izquierda dependiendo de si el nodo actual tiene un valor menor o mayor, como ya comentamos sobre la estrategia de búsqueda.
Eliminación en árbol de búsqueda binario en C++
Al igual que la inserción, hay dos casos posibles en la eliminación de un elemento en el BST. O estamos eliminando el último nodo, el nodo raíz, o estamos eliminando algún nodo donde tenemos más de un nodo en el árbol, de modo que el árbol no se vacíe después de eliminar el nodo actual.
En el primer caso, borramos el nodo y asignamos NULL al nodo raíz. En el segundo caso, tenemos tres posibilidades:
- el nodo no tiene un nodo secundario
- el nodo tiene solo un nodo secundario
- el nodo tiene nodos secundarios izquierdo y derecho
Los dos primeros esquemas son muy simples. En caso de que no haya un nodo secundario.
Elimine el nodo y devuelva NULL (ya que tenemos una definición recursiva nuevamente) para que al llamar a la función, el nodo principal asigne NULL a su puntero derecho o izquierdo.
Si el nodo tiene un nodo secundario, reemplace el nodo secundario con el nodo actual y elimine el nodo actual. Como resultado, el nodo secundario se asignará al abuelo en lugar del padre porque el padre morirá (perdón por esta analogía).
El último caso es complicado, donde un nodo tiene hijos tanto izquierdo como derecho. En este caso, tenemos dos opciones.
Primero, seleccione el nodo descendiente más a la izquierda del subárbol derecho del nodo actual o el nodo descendiente más a la derecha del subárbol izquierdo. En ambos casos, copie el valor del nodo seleccionado en el nodo actual.
Ahora, tenemos dos nodos en el BST con el mismo valor; por lo tanto, volveremos a llamar a la función recursiva delete en el subárbol izquierdo o en el subárbol derecho del nodo actual.
Considere el ejemplo; supongamos que queremos eliminar 5 del nodo raíz. Podemos seleccionar el nodo 6 del subárbol derecho, siendo el nodo más a la izquierda en el subárbol derecho de 5, o podemos seleccionar el nodo 3 del subárbol izquierdo, que es el nodo más a la derecha en el subárbol izquierdo de 5.
5 3 6 / \ / \ / 2 8 2 8 2 8 / \ / \ / / \ / \ 1 3 6 9 1 6 9 1 3 9
Veamos la implementación de la función borrar.
Node<T>* deleteNode(T key) { root = deleteNode(root, key); }
Node<T>* deleteNode(Node<T>* temp, T key) {
if (temp == NULL) return temp;
if (temp->data > key)
temp->left = deleteNode(temp->left, key);
else if (temp->data < key)
temp->right = deleteNode(temp->right, key);
else {
if (temp->left == NULL && temp->right == NULL) {
delete temp;
temp = NULL;
} else if (temp->left == NULL) {
Node<T>* curr = temp;
temp = temp->right;
delete curr;
} else if (temp->right == NULL) {
Node<T>* curr = temp;
temp = temp->left;
delete curr;
} else {
Node<T>* toBeDeleted = findMinNode(temp->right);
temp->data = toBeDeleted->data;
temp->right = deleteNode(temp->right, toBeDeleted->data);
}
}
return temp;
}
Nuevamente, primero, tenemos una función contenedora. A continuación, tenemos la función de caballo de batalla.
En las primeras tres líneas, estamos buscando nuestro nodo de destino. El valor objetivo no existe en el árbol en este caso; finalmente, llegaremos al nodo NULL.
De lo contrario, hay tres casos, o el nodo actual es más grande que la clave o más pequeño que la clave, o el nodo actual es nuestro nodo de destino (en cuyo caso, pasaremos a la otra parte).
En la otra parte, estamos manejando tres casos; Ya discutimos que el nodo de destino no tiene un nodo secundario, solo el nodo secundario derecho, solo el nodo secundario izquierdo y el secundario izquierdo y derecho (tratados en la otra parte).
En esta parte, usamos la función findMinNode para seleccionar el nodo más pequeño del subárbol derecho del nodo actual/objetivo. Ahora, vea toda la clase de BST.
#include <iostream>
using namespace std;
template <class T>
class Node {
public:
T data;
Node* left;
Node* right;
Node(T data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
template <class T>
class BST {
Node<T>* root;
public:
BST() { root = NULL; }
Node<T>* insert(T key) { root = insert(root, key); }
Node<T>* insert(Node<T>* temp, T key) {
if (temp == NULL) return new Node<T>(key);
if (temp->data > key)
temp->left = insert(temp->left, key);
else
temp->right = insert(temp->right, key);
return temp;
}
Node<T>* findMinNode(Node<T>* temp) {
while (temp->left != NULL) temp = temp->left;
return temp;
}
Node<T>* deleteNode(T key) { root = deleteNode(root, key); }
Node<T>* deleteNode(Node<T>* temp, T key) {
if (temp == NULL) return temp;
if (temp->data > key)
temp->left = deleteNode(temp->left, key);
else if (temp->data < key)
temp->right = deleteNode(temp->right, key);
else {
if (temp->left == NULL && temp->right == NULL) {
delete temp;
temp = NULL;
} else if (temp->left == NULL) {
Node<T>* curr = temp;
temp = temp->right;
delete curr;
} else if (temp->right == NULL) {
Node<T>* curr = temp;
temp = temp->left;
delete curr;
} else {
Node<T>* toBeDeleted = findMinNode(temp->right);
temp->data = toBeDeleted->data;
temp->right = deleteNode(temp->right, toBeDeleted->data);
}
}
return temp;
}
void preOrder() {
preOrder(root);
cout << '\n';
}
void preOrder(Node<T>* temp) {
if (temp == NULL) return;
cout << temp->data << " ";
preOrder(temp->left);
preOrder(temp->right);
}
void inOrder() {
inOrder(root);
cout << '\n';
}
void inOrder(Node<T>* temp) {
if (temp == NULL) return;
inOrder(temp->left);
cout << temp->data << " ";
inOrder(temp->right);
}
};
int main() {
BST<int> tree;
tree.insert(40);
tree.insert(22);
tree.insert(15);
tree.insert(67);
tree.insert(34);
tree.insert(90);
tree.preOrder();
tree.inOrder();
tree.deleteNode(40);
cout << "After deleting 40 temp from the tree\n";
tree.preOrder();
tree.inOrder();
return 0;
}
Tenemos toda la clase BST con las funciones transversales inOrder y preOrder para ver la forma de nuestro árbol. Podemos construir nuestro BST a partir de recorridos en orden y preorden o recorridos en orden y post-orden; puede leer este artículo.
Veamos la salida del código.
40 22 15 34 67 90
15 22 34 40 67 90
After deleting 40 temp from the tree
67 22 15 34 90
15 22 34 67 90
En esta salida, la primera línea tiene un recorrido en orden previo y la segunda línea tiene un recorrido en orden. En primer lugar, BST en orden siempre da elementos ordenados.
Por lo tanto, la segunda línea de alguna manera confirma que nuestro código está insertando correctamente.
Podemos construir un árbol binario a partir de las dos primeras líneas (recorridos). El pedido anticipado siempre comienza el recorrido desde el nodo raíz; por lo tanto, 40 es el nodo raíz.
Si vemos 40 en el recorrido en orden (segunda línea), podemos dividir nuestro árbol binario en subárboles izquierdo y derecho, donde 67 y 90 están en el subárbol derecho, y 15 , 22 y 34 están en el subárbol izquierdo; de manera similar, podemos completar el árbol binario restante. Finalmente, nuestro árbol binario es:
40 / 22 67 / \ 15 34 90
Este árbol binario tiene propiedades de BST y muestra que nuestro código funciona bien; De manera similar, podemos construir un árbol binario después de eliminar 40.
67 / 22 90 / 15 34
El nodo 40 es nuestro nodo de destino, tiene nodos secundarios izquierdo y derecho. Hemos seleccionado el más a la izquierda del subárbol derecho, que es 67 porque 67 no tiene hijo izquierdo; por lo tanto, copiamos el valor 67 en nuestro nodo de destino y llamamos a la función eliminar nuevamente para eliminar 67 del subárbol derecho de la raíz.
Ahora, tenemos un caso donde 67 tiene el único hijo derecho, 90; por lo tanto, reemplazaremos 90 por 67. Como resultado, 90 se convertirá en el hijo derecho de 67.
Lea el archivo en un árbol de búsqueda binario en C++
Finalmente, ahora podemos discutir la lectura de archivos en BST. De nuevo, lo haremos paso a paso.
Primero, considere el siguiente archivo.
This is first line.
This is second line.
This is third line.
This is fourth line.
This is fifth line.
This is sixth line.
This is seventh line.
This is eighth line.
Podemos leer este archivo fácilmente en C++ usando la función getline. Ver el código:
#include <fstream>
#include <iostream>
using namespace std;
int main() {
ifstream in("sample.txt");
string s;
while (getline(in, s)) cout << s << '\n';
in.close();
}
Tendremos la misma salida que puedes ver en el contenido del archivo en el cuadro anterior. Sin embargo, nuestro objetivo es colocar texto en BST para que podamos hacer una búsqueda más rápida.
Entonces, es simple; ya hemos implementado BST en la plantilla de clase, que también podemos usar para cadenas; todo lo que tenemos que hacer es crear un objeto de BST en consecuencia.
Puede guardar el contenido en el archivo sample.txt para leer el archivo a través del código. Aquí tenemos el código para leer el archivo en un árbol de búsqueda binaria.
#include <fstream>
#include <iostream>
using namespace std;
template <class T>
class Node {
public:
T data;
Node* left;
Node* right;
Node(T data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
template <class T>
class BST {
Node<T>* root;
public:
BST() { root = NULL; }
Node<T>* insert(T key) { root = insert(root, key); }
Node<T>* insert(Node<T>* temp, T key) {
if (temp == NULL) return new Node<T>(key);
if (temp->data > key)
temp->left = insert(temp->left, key);
else
temp->right = insert(temp->right, key);
return temp;
}
Node<T>* findMinNode(Node<T>* temp) {
while (temp->left != NULL) temp = temp->left;
return temp;
}
Node<T>* deleteNode(T key) { root = deleteNode(root, key); }
Node<T>* deleteNode(Node<T>* temp, T key) {
if (temp == NULL) return temp;
if (temp->data > key)
temp->left = deleteNode(temp->left, key);
else if (temp->data < key)
temp->right = deleteNode(temp->right, key);
else {
if (temp->left == NULL && temp->right == NULL) {
delete temp;
temp = NULL;
} else if (temp->left == NULL) {
Node<T>* curr = temp;
temp = temp->right;
delete curr;
} else if (temp->right == NULL) {
Node<T>* curr = temp;
temp = temp->left;
delete curr;
} else {
Node<T>* toBeDeleted = findMinNode(temp->right);
temp->data = toBeDeleted->data;
temp->right = deleteNode(temp->right, toBeDeleted->data);
}
}
return temp;
}
void preOrder() {
preOrder(root);
cout << '\n';
}
void preOrder(Node<T>* temp) {
if (temp == NULL) return;
cout << temp->data << " ";
preOrder(temp->left);
preOrder(temp->right);
}
void inOrder() {
inOrder(root);
cout << '\n';
}
void inOrder(Node<T>* temp) {
if (temp == NULL) return;
inOrder(temp->left);
cout << temp->data << " ";
inOrder(temp->right);
}
};
int main() {
BST<string> tree;
ifstream in("sample.txt");
string s;
while (getline(in, s)) tree.insert(s);
tree.preOrder();
tree.inOrder();
in.close();
return 0;
}
Producción:
Nuevamente, primero, tenemos un recorrido de orden previo, que muestra que el nodo raíz es Esta es la primera línea; sin embargo, si vemos un recorrido en orden, tenemos una salida ordenada.
Es decir, octavo a partir de e, la letra más pequeña entre primero, segundo, tercero, cuarto, quinto, sexto, séptimo y octavo, mientras que a continuación, tenemos quinto, que es más pequeño que primero porque f en quinto es más pequeño que r en primero.