SHARE
TWEET

Vai dar bom na prova amanhã

a guest Dec 2nd, 2019 83 in 2 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. /*typedef int int;
  5.  
  6. typedef struct {
  7.   int Chave;
  8. } int;*/
  9.  
  10. typedef struct SNo TArvBin;
  11. struct SNo{
  12.   int Item;
  13.   struct SNo *Esq;
  14.   struct SNo *Dir;
  15. };
  16.  
  17. typedef struct Arvore {
  18.   TArvBin *raiz;
  19. } Arv;
  20.  
  21. void TArvBin_Inicia (Arv *arv, int v){
  22.   arv->raiz = (TArvBin *) malloc (sizeof(TArvBin));
  23.   arv->raiz->Item = v;
  24.   arv->raiz->Esq = NULL;
  25.   arv->raiz->Dir = NULL;
  26. }
  27.  
  28. TArvBin* TArvBin_CriaNo (int x, TArvBin *Esq, TArvBin *Dir){
  29.   TArvBin* No;
  30.   No = (TArvBin*) malloc(sizeof(TArvBin));
  31.   No->Item = x;
  32.   No->Esq = Esq;
  33.   No->Dir = Dir;
  34.   return No;
  35. }
  36.  
  37. void TArvBin_Libera (TArvBin *No){
  38.   if (No != NULL){
  39.     TArvBin_Libera(No->Esq);
  40.     TArvBin_Libera(No->Dir);
  41.     free(No);
  42.   }
  43. }
  44.  
  45. void PreOrdem(TArvBin *No){
  46.   printf ("(C%d", No->Item);
  47.   if ( No->Esq != NULL ) PreOrdem ( No->Esq );
  48.   if (No->Esq==NULL) printf("()");
  49.   if ( No->Dir != NULL ) PreOrdem ( No->Dir );
  50.   if (No->Dir==NULL) printf("()");
  51.   printf(")");
  52. }
  53.  
  54. int TArvBin_Pesquisa(TArvBin *Raiz, int x){
  55.   TArvBin *No;
  56.   No = Raiz;
  57.   while ((No != NULL) && (x != No->Item)){
  58.     if (x < No->Item){
  59.       No = No->Esq;
  60.     }
  61.     else if (x > No->Item){
  62.       No = No->Dir;
  63.     }
  64.   }
  65.   if ( No == NULL ) return 0;
  66.   else return 1;
  67. }
  68.  
  69. int Insere(TArvBin *pRaiz, int x){
  70.   TArvBin *pNo;
  71.   pNo = pRaiz;
  72.   while ((pNo != NULL) && (x != pNo->Item)){
  73.     if ( x == pNo->Item ) {
  74.       return 0;
  75.     }
  76.     else if (x < pNo->Item){
  77.       if ( pNo->Esq == NULL ){
  78.         pNo->Esq = TArvBin_CriaNo (x, NULL, NULL);
  79.         return 1;
  80.       }
  81.       else pNo = pNo->Esq;
  82.     }
  83.  
  84.     else if (x > pNo->Item){
  85.       if ( pNo->Dir == NULL ){
  86.         pNo->Dir = TArvBin_CriaNo (x, NULL, NULL);
  87.         return 1;
  88.       }
  89.       else pNo = pNo->Dir;
  90.     }
  91.   }
  92.   return 1;
  93. }
  94.  
  95. TArvBin* Sucessor(TArvBin *dir){
  96.   if ( dir != NULL ){
  97.     if ( dir->Esq == NULL ){
  98.       return dir;
  99.     }
  100.     else {
  101.       return Sucessor ( dir->Esq );
  102.     }
  103.   }
  104.   return NULL;
  105. }
  106.  
  107. int Remove(TArvBin *pRaiz, int x){
  108.   TArvBin *p, *q;
  109.   p = pRaiz;
  110.   while (p != NULL) {
  111.     if ( p->Dir != NULL ){
  112.       if ( p->Dir->Item == x ) break;
  113.     }
  114.     if ( p->Esq != NULL ){
  115.       if ( p->Esq->Item == x ) break;
  116.     }
  117.  
  118.     if (x < p->Item){
  119.       if ( p->Esq != NULL ) p = p->Esq;
  120.     }
  121.  
  122.     else if (x > p->Item){
  123.       p = p->Dir;
  124.     }
  125.   }
  126.   if ( p == NULL ){
  127.     //printf ("nulo\n");
  128.     return 0;
  129.   }
  130.   TArvBin *aux;
  131.   if ( p->Esq != NULL ){
  132.     if ( p->Esq->Item == x ){
  133.       //printf ("Esquerda\n");
  134.       aux = p->Esq;
  135.       if ( aux->Dir == aux->Esq && aux->Esq == NULL ){
  136.         p->Esq = NULL;
  137.       }
  138.       else {
  139.         if ( p->Esq->Dir == NULL ){
  140.           p->Esq = p->Esq->Esq;
  141.         }
  142.         else if ( p->Esq->Esq == NULL ){
  143.           p->Esq = Sucessor ( p->Esq->Dir );
  144.         }
  145.       }
  146.     }
  147.   }
  148.   else {
  149.     aux = p->Dir;
  150.     if ( aux->Dir == aux->Esq && aux->Esq == NULL ){
  151.       p->Dir = NULL;
  152.     }
  153.     else {
  154.       //printf ("laksjdfl\n");
  155.       if ( p->Dir->Dir == NULL ){
  156.         p->Dir = p->Dir->Esq;
  157.       }
  158.       else if ( p->Dir->Esq == NULL ){
  159.         //printf ("antes sucessor\n");
  160.         p->Dir = Sucessor ( p->Dir->Dir );
  161.         //printf ("saiu sucessor\n");
  162.       }
  163.     }
  164.   }
  165.   //printf ("fim\n");
  166.   free ( aux );
  167.   return 1;
  168. }
  169. int main(){
  170.  
  171.   Arv arv;
  172.  
  173.   int chave, itens[1000], qtd, i;
  174.  
  175.   scanf("%d", &qtd);
  176.  
  177.   // Li todos os valores da árvore
  178.   for (i=0; i<qtd; i++) {
  179.     scanf("%d", &itens[i]);
  180.   }
  181.  
  182.   // Inicio a árvore com o primeiro valor da lista, que é a raiz
  183.   TArvBin_Inicia(&arv, itens[0]);
  184.  
  185.   // Leitura da chave que queremos excluir, se existe na arvore ou inclusão se não existe
  186.   scanf("%d", &chave);
  187.  
  188.   for (i = 1; i < qtd; i++) {
  189.     Insere(arv.raiz, itens[i]);
  190.   }
  191.  
  192.   if (TArvBin_Pesquisa (arv.raiz, chave) == 1) {
  193.     Remove(arv.raiz, chave);
  194.   }else{
  195.     Insere(arv.raiz, chave);
  196.   }
  197.   PreOrdem(arv.raiz);
  198.   return 0;
  199. }
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