Árvore binária de busca (BST)
Comece com uma árvore binária de busca aleatória e insira, busque ou exclua valores passo a passo, com sua forma em array e o código C++ destacado.
Tudo é simulado neste navegador; nada é enviado a nenhum servidor.
Sem passos
Sem passos
Árvore binária de busca
Índice no array
Forma em array
Os filhos do índice i estão em 2i+1 e 2i+2.
- Sem relação
- Já percorrido
- Sendo comparado
- Encontrado
- Novo
- A excluir
- Sucessor
Sem passos
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 setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
Node* insert(Node* root, int v) { // Insere v na árvore de busca e devolve a raiz
if (root == nullptr) // Posição vazia: o novo nó fica aqui
return new Node(v); // Cria o novo nó
if (v < root->getValue()) // Valores menores vão para a esquerda e maiores para a direita
root->setLeft(insert(root->getLeft(), v)); // Desce pela subárvore esquerda
else
root->setRight(insert(root->getRight(), v)); // Desce pela subárvore direita
return root;
}
int main() {
Node* root = buildTree(); // A árvore exibida, já construída
root = insert(root, v); // Primeira chamada, a partir de main
return 0; // Fim da operação
}