Implementar Inorder Traversal para el árbol binario de búsqueda en C++
Este artículo explicará cómo implementar el recorrido en orden para árboles de búsqueda binarios en C++.
Utilice Inorder Traversal para imprimir el contenido del árbol binario de búsqueda
Se construye un árbol de búsqueda binario de modo que la clave de cada nodo debe ser mayor que todas las claves en su subárbol izquierdo y menor que todas las claves en el subárbol derecho.
Aquí solo consideramos árboles desequilibrados en aras de la simplicidad, pero en escenarios del mundo real, la eficiencia de un árbol binario de búsqueda proviene de la naturaleza equilibrada, donde cada subárbol de la raíz tiene aproximadamente la misma altura.
Los árboles binarios se pueden atravesar utilizando tres métodos diferentes denominados: inorder, preorder y postorder. El recorrido en orden para el árbol binario de búsqueda produce los elementos ordenados en orden no decreciente. Esta versión generalmente comienza desde el nodo más a la izquierda y sigue el orden en el que se atravesará primero el subárbol izquierdo, luego el nodo raíz y finalmente el subárbol derecho.
Observe la siguiente salida del fragmento de código y el orden de los enteros a medida que se insertaron en un árbol.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct TreeNode {
int key;
struct TreeNode *left{};
struct TreeNode *right{};
};
void insertNode(TreeNode *&root, const int k) {
if (root == nullptr) {
root = new TreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
void printTreeInorder(TreeNode *n) {
if (n != nullptr) {
printTreeInorder(n->left);
cout << n->key << "; ";
printTreeInorder(n->right);
}
}
int main() {
std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};
TreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printTreeInorder(root);
cout << endl;
return EXIT_SUCCESS;
}
2; 3; 5; 9; 11; 15; 20; 23;
Alternativamente, es posible que necesitemos utilizar el recorrido de preorden o postorder para acceder al nodo en el árbol binario de búsqueda. Solo necesitamos mover la línea cout << n->key << "; " en las funciones printTree* para modificar el algoritmo de recorrido.
El recorrido de preorden comienza a imprimirse desde el nodo raíz y luego entra en los subárboles izquierdo y derecho, respectivamente, mientras que el recorrido de posorden visita el nodo raíz al final.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct TreeNode {
int key;
struct TreeNode *left{};
struct TreeNode *right{};
};
void insertNode(TreeNode *&root, const int k) {
if (root == nullptr) {
root = new TreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
void printTreePreorder(TreeNode *n) {
if (n != nullptr) {
cout << n->key << "; ";
printTreePreorder(n->left);
printTreePreorder(n->right);
}
}
void printTreePostorder(TreeNode *n) {
if (n != nullptr) {
printTreePostorder(n->left);
printTreePostorder(n->right);
cout << n->key << "; ";
}
}
int main() {
std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};
TreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printTreePostorder(root);
cout << endl;
printTreePreorder(root);
cout << endl;
return EXIT_SUCCESS;
}
2; 9; 5; 3; 20; 15; 23; 11;
11; 3; 2; 5; 9; 23; 15; 20;
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook