Created
December 3, 2014 03:27
-
-
Save marcoscastro/f287ebbe0fa7efe31998 to your computer and use it in GitHub Desktop.
Curso C++ para iniciantes - Aula 53 - Árvore binária
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| using namespace std; | |
| class No | |
| { | |
| private: | |
| No *esq, *dir; | |
| int chave; | |
| public: | |
| No(int chave) | |
| { | |
| this->chave = chave; | |
| esq = NULL; | |
| dir = NULL; | |
| } | |
| int getChave() | |
| { | |
| return chave; | |
| } | |
| // funções getters e setters | |
| No* getEsq() | |
| { | |
| return esq; | |
| } | |
| No* getDir() | |
| { | |
| return dir; | |
| } | |
| void setEsq(No *no) | |
| { | |
| esq = no; | |
| } | |
| void setDir(No *no) | |
| { | |
| dir = no; | |
| } | |
| }; | |
| class Arvore | |
| { | |
| private: | |
| No *raiz; | |
| public: | |
| Arvore() | |
| { | |
| raiz = NULL; | |
| } | |
| void inserir(int chave) | |
| { | |
| if(raiz == NULL) // verifica se a árvore está vazia | |
| raiz = new No(chave); // cria um novo nó | |
| else | |
| inserirAux(raiz, chave); | |
| } | |
| void inserirAux(No *no, int chave) | |
| { | |
| // se for menor, então insere à esquerda | |
| if(chave < no->getChave()) | |
| { | |
| // verifica se a esquerda é nulo | |
| if(no->getEsq() == NULL) | |
| { | |
| No *novo_no = new No(chave); | |
| no->setEsq(novo_no); // seta o novo_no à esquerda | |
| } | |
| else | |
| { | |
| // senão, continua percorrendo recursivamente | |
| inserirAux(no->getEsq(), chave); | |
| } | |
| } | |
| // se for maior, então insere à direita | |
| else if(chave > no->getChave()) | |
| { | |
| // verifica se a direita é nulo | |
| if(no->getDir() == NULL) | |
| { | |
| No *novo_no = new No(chave); | |
| no->setDir(novo_no); // seta o novo_no à direita | |
| } | |
| else | |
| { | |
| // senão, continua percorrendo recursivamente | |
| inserirAux(no->getDir(), chave); | |
| } | |
| } | |
| // se for igual, não vai inserir | |
| // não pode existir 2 chaves iguais | |
| } | |
| No* getRaiz() | |
| { | |
| return raiz; | |
| } | |
| void emOrdem(No* no) | |
| { | |
| if(no != NULL) | |
| { | |
| emOrdem(no->getEsq()); | |
| cout << no->getChave() << " "; | |
| emOrdem(no->getDir()); | |
| } | |
| } | |
| }; | |
| int main(int argc, char *argv[]) | |
| { | |
| Arvore arv; | |
| // insere as chaves | |
| arv.inserir(8); | |
| arv.inserir(3); | |
| arv.inserir(10); | |
| arv.inserir(14); | |
| arv.inserir(13); | |
| arv.inserir(1); | |
| arv.inserir(6); | |
| arv.inserir(4); | |
| arv.inserir(7); | |
| // percorre em ordem iniciando da raiz | |
| cout << "Percorrendo em ordem...\n"; | |
| arv.emOrdem(arv.getRaiz()); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment