Implementar Inorder Traversal para árvore binária de busca em C++
Este artigo explicará como implementar a travessia em ordem para árvores de pesquisa binárias em C++.
Use Inorder Traversal para imprimir o conteúdo da árvore binária de busca
Uma árvore binária de busca é construída de forma que a chave de cada nó deve ser maior que todas as chaves em sua subárvore esquerda e menor que todas as chaves na subárvore direita.
Só consideramos árvores desequilibradas aqui por uma questão de simplicidade, mas em cenários do mundo real, a eficiência de uma árvore binária de busca vem da natureza equilibrada, em que cada subárvore da raiz tem aproximadamente a mesma altura.
Árvores binárias podem ser percorridas usando três métodos diferentes denominados: inorder, preorder e postorder. A travessia em ordem para a árvore binária de busca produz os elementos classificados em ordem não decrescente. Essa versão geralmente começa no nó mais à esquerda e segue a ordem em que a subárvore esquerda será percorrida primeiro, depois o nó raiz e, finalmente, a subárvore direita.
Observe a seguinte saída de fragmento de código e a ordem dos inteiros conforme eles foram inseridos em uma árvore.
#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, podemos precisar utilizar a passagem de pré-ordem ou pós-ordem para acessar o nó na árvore binária de busca. Precisamos apenas mover a linha cout << n->key << "; " nas funções printTree* para modificar o algoritmo de passagem.
A passagem de pré-ordem começa a imprimir a partir do nó raiz e vai para as subárvores esquerda e direita, respectivamente, enquanto a passagem de pós-ordem visita o nó raiz no 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