URI Online Judge | 1200
Operações em ABP I
Por Neilor Tonin, URI 
Brasil
Timelimit: 1 Brasil
Marcela recebeu como trabalho de Algoritmos a tarefa de fazer um programa que implemente uma Árvore Binária de Pesquisa (ou Busca). O Programa deve aceitar os seguintes comandos:
- I n: Insere na árvore binária de pesquisa o elemento n.
- INFIXA: lista os elementos já cadastrado segundo o percurso infixo
- PREFIXA: lista os elementos já cadastrado segundo o percurso prefixo
- POSFIXA: lista os elementos já cadastrado segundo o percurso posfixo
- P n: pesquisa se o elemento n existe ou não.
A qualquer momento pode-se inserir um elemento, visitar os elementos previamente inseridos na ordem infixa, prefixa ou posfixa ou ainda procurar por um elemento na árvore para saber se o elemento existe ou não.
Entrada
A entrada contém N operações utilizando letras (A-Z,a-z) sobre uma árvore binária de Busca, que inicialmente se encontra vazia. A primeira linha de entrada contém a inserção de algum elemento. As demais linhas de entrada podem conter quaiquer um dos comandos descritos acima, conforme exemplo abaixo. O final da entrada é determinado pelo final de arquivo (EOF).
Obs: Considere que não serão inseridos elementos repetidos na árvore.
Saída
Cada linha de entrada, com exceção das linhas que contém o comando "I", deve produzir uma linha de saída. A saída deve ser de acordo com o exemplo fornecido abaixo. Não deve haver espaço em branco após o último caractere de cada linha, caso contrário, sua submissão receberá Presentation Error.
#include <iostream>
#include <cstdlib>
#define TIPO char
using namespace std;
int cont = 0;
struct nodo {
nodo *esquerda;
TIPO informacao;
nodo *direita;
nodo (TIPO info ):
informacao(info),
esquerda(0),
direita(0) {}
};
nodo *P;
int espaco;
struct nodo *insere (nodo *tree, TIPO informacao) {
if(tree == NULL)
tree = new nodo (informacao);
else if (informacao < tree ->informacao)
tree->esquerda = insere(tree->esquerda, informacao);
else if (informacao > tree->informacao)
tree->direita = insere(tree->direita, informacao);
return tree;
};
struct nodo *busca(nodo *raiz, char valor) {
if(raiz == NULL) {
cout << valor << " nao existe" << endl;
return NULL;
} else {
if(raiz->informacao > valor) {
busca(raiz->esquerda, valor);
} else if(raiz->informacao < valor) {
busca(raiz->direita, valor);
} else cout << valor << " existe" << endl;
}
};
void infixa(nodo *tree) {
if(tree != NULL) {
infixa(tree->esquerda);
if(espaco != 1)
cout << " " << tree->informacao;
else {
cout << tree->informacao;
espaco = 0;
}
infixa(tree->direita);
}
}
void prefixa(nodo *tree) {
if(tree != NULL) {
if(espaco != 1)
cout << " " << tree->informacao;
else {
cout << tree->informacao;
espaco = 0;
}
prefixa(tree->esquerda);
prefixa(tree->direita);
}
}
void posfixa(nodo *tree) {
if(tree != NULL) {
posfixa(tree->esquerda);
posfixa(tree->direita);
if(espaco != 1)
cout << " " << tree->informacao;
else {
cout << tree->informacao;
espaco = 0;
}
}
}
int main() {
nodo *raiz = 0;
TIPO valor;
string op;
while(cin >> op) {
if(op == "I") {
cin >> valor;
raiz = insere(raiz, valor);
}
if (op == "P") {
cin >> valor;
busca(raiz, valor);
}
if(op == "INFIXA") {
espaco = 1;
infixa(raiz);
cout << endl;
}
if(op == "PREFIXA") {
espaco = 1;
prefixa(raiz);
cout << endl;
}
if(op == "POSFIXA") {
espaco = 1;
posfixa(raiz);
cout << endl;
}
}
}
0 Comentários