Percursos de árvore binária
Gere uma árvore binária de busca e acompanhe passo a passo os percursos em pré-ordem, em ordem ou em pós-ordem com uma função recursiva em C++.
Tudo é simulado neste navegador; nada é enviado a nenhum servidor.
Visita o nó, depois a subárvore esquerda e em seguida a direita.
A função é chamada com o nó 60
A função é chamada com o nó 60
Árvore binária
Saída
Nenhum nó foi visitado ainda
- Não visitado
- Em execução
- Na pilha
- Visitado
Passo 1 / 44
Código
#include <iostream>
using namespace std;
class Node { // Um nó guarda seu valor e ponteiros para seus dois filhos
private: // Atributos privados: só os métodos acessam
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
void preorder(Node* node) { // Percorre a subárvore com raiz em node
if (node == nullptr) return; // Caso base: uma subárvore vazia não tem nada a visitar
cout << node->getValue() << " "; // Visita o nó: processa seu valor
preorder(node->getLeft()); // Percorre a subárvore esquerda
preorder(node->getRight()); // Percorre a subárvore direita
} // Retorna ao chamador
Node* insert(Node* root, int v) { // Insere v na árvore de busca e devolve a raiz
if (root == nullptr) return new Node(v); // Posição vazia: o novo nó fica aqui
if (v < root->getValue()) // Valores menores vão para a esquerda e maiores para a direita
root->setLeft(insert(root->getLeft(), v));
else
root->setRight(insert(root->getRight(), v));
return root;
}
Node* buildTree() { // Constrói a árvore inserindo os valores um a um
int values[] = {60, 45, 85, 68, 21, 55, 32}; // Os valores da árvore exibida, na ordem de inserção
Node* root = nullptr;
for (int v : values) root = insert(root, v);
return root;
}
int main() {
Node* root = buildTree(); // A árvore da animação, já construída
preorder(root); // Primeira chamada, a partir de main
cout << endl; // Fim do percurso
return 0;
}