SHARE
TWEET

Estrutura de Dados - Arvore BST - I/R

shouldz Sep 22nd, 2019 (edited) 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. /*
  5. /@autor: Shouldz
  6. /@Linguagem: C
  7. /@Descrição: [Estrutura de Dados] Árvore BST com operação de inserção e remoção funcionais, ambas recursivas.
  8. */
  9.  
  10. typedef struct no{
  11.     int valor;
  12.     struct no *dir;
  13.     struct no *esq;
  14. }no;
  15.  
  16. no *criar_no(int valor){
  17.     no *criar_no = malloc(sizeof(no));
  18.     criar_no -> dir = NULL;
  19.     criar_no -> esq = NULL;
  20.     criar_no -> valor = valor;
  21.     return criar_no;
  22. }
  23.  
  24. no *inserir(no *raiz, int valor){
  25.     if(raiz == NULL){
  26.         raiz = criar_no(valor);
  27.         return raiz;
  28.     }else{
  29.         if(valor > raiz -> valor){
  30.             raiz -> dir = inserir(raiz -> dir, valor);
  31.         }else{
  32.             raiz -> esq = inserir(raiz -> esq, valor);
  33.         }
  34.     }
  35. }
  36.  
  37. no *maiorDescendenteEsquerdo(no *raiz){
  38.     //Procura o maior descendente esquerdo do elemento a ser removido
  39.     no *auxiliar = raiz;
  40.     //Se a subarvore esquerda do elemento não tem direito, então maior encontrado
  41.     if(auxiliar -> dir == NULL){
  42.         return auxiliar;
  43.     }else{
  44.         //se tem direito, então percorrer todas as subarvores direitas afim do maior
  45.         while(auxiliar -> dir != NULL){
  46.             auxiliar = auxiliar -> dir;
  47.         }
  48.         return auxiliar;
  49.     }
  50. }
  51.  
  52. no *remover(no *raiz, int valor){
  53.     //caso base
  54.     if(raiz == NULL){
  55.         return NULL;
  56.     }
  57.     //if e elif para procurar o elemento
  58.     if(valor > raiz -> valor){
  59.         raiz -> dir = remover(raiz -> dir, valor);
  60.     }else if(valor < raiz -> valor){
  61.         raiz -> esq = remover(raiz -> esq, valor);
  62.     }else{ //caso encontrado
  63.         //caso 01 e 02: No possui um ou nenhum filho
  64.         if(raiz -> dir == NULL){
  65.             no *auxiliarE = raiz -> esq;
  66.             return auxiliarE;
  67.         }else if(raiz -> esq == NULL){
  68.             no *auxiliarD = raiz -> dir;
  69.             return auxiliarD;
  70.         }
  71.         //caso 03: No possui 3 filhos, uso da função para achar maiorDescendenteEsquerdo
  72.         no *receber = maiorDescendenteEsquerdo(raiz -> esq);
  73.         //copia o valor do maiorDescendenteEsquerdo
  74.         raiz -> valor = receber -> valor;
  75.         //remover o elemento copiado
  76.         raiz -> esq = remover(raiz -> esq, receber -> valor);
  77.     }
  78.     return raiz;
  79. }
  80. void preorder(no *arvore){
  81.     if(arvore != NULL){
  82.         printf("[%d]", arvore -> valor);
  83.         preorder(arvore -> esq);
  84.         preorder(arvore -> dir);  
  85.     }
  86. }
  87.  
  88. void main(){
  89.     no *arvore = NULL;
  90.     printf("TESTE 01: R= 70\n");
  91.     arvore = inserir(arvore, 40);
  92.     arvore = inserir(arvore, 12);
  93.     arvore = inserir(arvore, 65);
  94.     arvore = inserir(arvore, 10);
  95.     arvore = inserir(arvore, 70);
  96.     preorder(arvore);
  97.     printf("\n");
  98.     arvore = remover(arvore, 70);
  99.     preorder(arvore);
  100.     printf("\n");
  101.     arvore = NULL;
  102.     printf("TESTE 02: R= 65\n");
  103.     arvore = inserir(arvore, 40);
  104.     arvore = inserir(arvore, 12);
  105.     arvore = inserir(arvore, 65);
  106.     arvore = inserir(arvore, 10);
  107.     arvore = inserir(arvore, 70);
  108.     preorder(arvore);
  109.     printf("\n");
  110.     arvore = remover(arvore, 65);
  111.     preorder(arvore);
  112.     printf("\n");
  113.     arvore = NULL;
  114.     printf("TESTE 03: R= 12\n");
  115.     arvore = inserir(arvore, 40);
  116.     arvore = inserir(arvore, 12);
  117.     arvore = inserir(arvore, 65);
  118.     arvore = inserir(arvore, 10);
  119.     arvore = inserir(arvore, 15);
  120.     arvore = inserir(arvore, 70);
  121.     arvore = inserir(arvore, 8);
  122.     arvore = inserir(arvore, 11);
  123.     preorder(arvore);
  124.     printf("\n");
  125.     arvore = remover(arvore, 12);
  126.     preorder(arvore);
  127. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top