URI - 1195 - Árvore Binária de Busca - Grafos - C++

Plataforma: URI

Problema: 1195

Enunciado:

Em computação, a árvores binária de busca ou árvore binária de pesquisa é uma estrutura baseada em nós (nodos), onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (e assim sucessivamente). O objetivo desta árvore é estruturar os dados de forma flexível, permitindo a busca binária de um elemento qualquer da árvore.

A grande vantagem das árvores de busca binária sobre estruturas de dados convencionais é que os algoritmos de ordenação (percurso infixo) e pesquisa que as utilizam são muito eficientes.

Para este problema, você receberá vários conjuntos de números e a partir de cada um dos conjuntos, deverá construir uma árvore binária de busca. Por exemplo, a sequência de valores: 8 3 10 14 6 4 13 7 1 resulta na seguinte árvore binária de busca:

                    8

         3               10

     1       6                14

           4     7         13
Linguagem: C++

Solução:
Primeiramente dividimos a solução em três partes:
1) Criar a estrutura da árvore:
Foi criado uma struct TreeNode. Ele contem um ponteiro para o lado esquerdo, um ponteiro para o lado direito e um valor.
Além disso, foi feito um construtor que coloca NULL em seus dois ponteiros e coloca o valor a ser inserido na estrutura.

2) Inserir os elementos na árvore:
Para inserir o elemento na árvore, é verificado a posição em que deve ser inserido. Se o valor for menor do que o valor que está no nodo atual, então o processo é refeito verificando o nodo a esquerda. Caso o valor a ser inserido for maior que o nodo atual, o processo é refeito verificando o nodo a direita. Quando for encontrado um nodo NULL, então o elemento é inserido.

3) Imprimir a árvore:
É preciso imprimir nas três ordens citadas pelo exercício. A função de imprimir foi feito de forma recursiva, determinando o que deve ser impresso de acordo com a ordem escolhida.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

#include <iostream> using namespace std; struct TreeNode{ TreeNode * left; TreeNode * right; int value; TreeNode(int newValue) { value = newValue; left = NULL; right = NULL; } }; void insert(TreeNode* & root, int newValue){ if(root == NULL){ root = new TreeNode( newValue ); return; } if(newValue > (root->value) ){ insert(root->right, newValue); } else{ insert(root->left, newValue); } return; } // order : 1 - pre, 2 - in, 3 - post void printTree(TreeNode* & root, bool first, int order){ if(root == NULL){ return; } if(first){ switch(order){ case 1: cout << "Pre.:"; break; case 2: cout << "In..:"; break; case 3: cout << "Post:"; break; } } switch(order){ case 1: // pre order cout << " " << root->value; printTree(root->left,false,order); printTree(root->right, false,order); break; case 2: // in order printTree(root->left,false,order); cout << " " << root->value; printTree(root->right, false,order); break; case 3: // post order printTree(root->left,false,order); printTree(root->right, false,order); cout << " " << root->value; break; } if(first){ cout << endl; } } int main(){ int n, elements, value; cin >> n; for(int i = 1;i<=n; i++){ TreeNode * root = NULL; cout << "Case " << i << ":" <<endl; cin >> elements; while(elements--){ cin >> value; insert(root, value); } for(int order = 1; order<=3; order++){ printTree(root, true, order); } delete root; cout << endl; } return 0; }