API tools faq
paste
Advertisement
DimasDark

L2Q1 ~COMPLETE~BST Tree

DimasDark
Jul 1st, 2013
306
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.95 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2.  
  3.  
  4. int _nivel = 0;
  5. int _quantidade = 0;
  6. bool _removeu = false;
  7. bool _achou = false;
  8.  
  9. //BST ~DIMASDARK ~ ADAPTADO PRA QUESTAO DE ALGORITMOS
  10. //PS: ODEIO ESSAS COISAS DE NÃO DEIXAR ESPAÇO NO FINAL, PFVR NÉ -.-"
  11. typedef struct arvore
  12. {
  13.     int tipo;
  14.     int quantidade;
  15.     struct arvore* esquerda;
  16.     struct arvore* direita;
  17.  
  18.  
  19. } Arv;
  20.  
  21.  
  22. Arv* inicializar()
  23. {
  24.     return NULL;
  25. }
  26.  
  27.  
  28. Arv* inserir(int t, int qtd, Arv* raiz, int &nivel, int &qimp, int n = 0)
  29. {
  30.     //qimp = quantidade a imprimir
  31.     //n = nível a imprimir
  32.     nivel = n;
  33.     if (raiz == NULL)
  34.     {
  35.  
  36.         Arv* no = new Arv();
  37.         no->tipo = t;
  38.         no->quantidade = qtd;
  39.         no->direita = no->esquerda = NULL;
  40.         raiz = no;
  41.         qimp = qtd;
  42.         return raiz;
  43.     }
  44.     else
  45.     {
  46.  
  47.         if (t < raiz->tipo )
  48.         {
  49.             raiz->esquerda = inserir(t, qtd, raiz->esquerda, nivel, qimp, n+1);
  50.  
  51.         }
  52.         else if (t > raiz->tipo)
  53.         {
  54.             raiz->direita = inserir(t, qtd, raiz->direita, nivel, qimp, n+1);
  55.  
  56.         }
  57.         else
  58.         {
  59.             raiz->quantidade = raiz->quantidade + qtd;
  60.             qimp = raiz->quantidade;
  61.  
  62.         }
  63.  
  64.         return raiz;
  65.  
  66.     }
  67.  
  68.  
  69.  
  70. }
  71.  
  72.  
  73. int busca (Arv* arv, int t)
  74. {
  75.     int i = arv->quantidade;
  76.     if (arv == NULL)
  77.         return 0; /* árvore vazia: não encontrou */
  78.     else
  79.     {
  80.         if (t > arv->tipo)
  81.         {
  82.             busca(arv->direita, t);
  83.         }
  84.         else if (t < arv->tipo)
  85.         {
  86.             busca(arv->esquerda,t);
  87.         }
  88.         else
  89.         {
  90.             return i;
  91.         }
  92.     }
  93.     return 0;
  94. }
  95.  
  96. Arv* buscaNo(Arv* arv, int t, int &nivel, int &qtd,int n = 0)
  97. {
  98.     nivel = n;
  99.     Arv* aux = arv;
  100.     if (arv == NULL)
  101.         return NULL; /* árvore vazia: não encontrou */
  102.     else
  103.     {
  104.         if (t > arv->tipo)
  105.         {
  106.             aux = buscaNo(arv->direita, t, nivel, qtd, n+1);
  107.         }
  108.         else if (t < arv->tipo)
  109.         {
  110.             aux = buscaNo(arv->esquerda,t, nivel, qtd, n+1);
  111.         }
  112.         else
  113.         {
  114.             qtd = aux->quantidade;
  115.         }
  116.          return aux;
  117.     }
  118. }
  119.  
  120. void preOrdem(Arv* arv, bool cabeca = true)
  121. {
  122.  
  123.     if (arv != NULL)
  124.     {
  125.         if (cabeca)
  126.             printf("%d", arv->tipo);
  127.         else
  128.             printf(" %d", arv->tipo);
  129.         preOrdem(arv->esquerda, false);
  130.         preOrdem(arv->direita, false);
  131.     }
  132.  
  133. }
  134.  
  135. void posOrdem(Arv* arv, bool cabeca = true)
  136. {
  137.  
  138.     if (arv != NULL)
  139.     {
  140.         posOrdem(arv->esquerda, false);
  141.         posOrdem(arv->direita, false);
  142.         if (cabeca)
  143.             printf("%d", arv->tipo);
  144.         else
  145.             printf("%d ", arv->tipo);
  146.     }
  147.  
  148. }
  149.  
  150. void emOrdem(Arv* arv, Arv* maior, bool cabeca = false)
  151. {
  152.     if (arv != NULL)
  153.     {
  154.         emOrdem(arv->esquerda, maior, false);
  155.         if (arv->tipo == maior->tipo)
  156.             printf("%d", arv->tipo);
  157.         else
  158.             printf("%d ", arv->tipo);
  159.         emOrdem(arv->direita, maior, true);
  160.     }
  161.  
  162. }
  163.  
  164. //Para a sub a direita
  165. Arv* pegaAntesMenor(Arv* arvdir)
  166. {
  167.     while (arvdir->esquerda != NULL)
  168.     {
  169.         if (arvdir->esquerda->esquerda == NULL)
  170.             break;
  171.         else
  172.             arvdir = arvdir ->esquerda;
  173.     }
  174.  
  175.     return arvdir;
  176. }
  177.  
  178. Arv* pegaMenorDireita(Arv* arvdir)
  179. {
  180.     while (arvdir->esquerda != NULL)
  181.     {
  182.         arvdir = arvdir ->esquerda;
  183.     }
  184.  
  185.     return arvdir;
  186.  
  187. }
  188.  
  189. //Para maior no da sub a esquerda
  190. Arv* pegaAntesMaior(Arv* arvesq)
  191. {
  192.     if (arvesq->direita != NULL)
  193.     {
  194.         if (arvesq->direita->direita == NULL)
  195.             return arvesq;
  196.         else
  197.             pegaAntesMenor(arvesq->direita);
  198.     }
  199.     else
  200.         return arvesq;
  201.  
  202.     return 0;
  203. }
  204.  
  205. Arv* pegaMaiorElemento(Arv* arv)
  206. {
  207.     if (arv != NULL)
  208.     {
  209.         while (arv->direita != NULL)
  210.             arv = arv->direita;
  211.     }
  212.     return arv;
  213. }
  214.  
  215. Arv* removerMinimoDireita(Arv* arvdir)
  216. {
  217.     Arv* aux = new Arv();
  218.  
  219.     if (arvdir -> esquerda == NULL)
  220.     {
  221.         aux = arvdir -> direita;
  222.         delete(arvdir);
  223.         return aux;
  224.     }
  225.     else
  226.     {
  227.         arvdir -> esquerda = removerMinimoDireita(arvdir -> esquerda);
  228.         return arvdir;
  229.     }
  230. }
  231.  
  232. Arv* removerMaximoEsquerda(Arv* arvesq)
  233. {
  234.     Arv* aux = new Arv();
  235.  
  236.     if (arvesq -> direita == NULL)
  237.     {
  238.         aux = arvesq -> esquerda;
  239.         delete(arvesq);
  240.         return aux;
  241.     }
  242.     else
  243.     {
  244.         arvesq -> direita = removerMinimoDireita(arvesq -> direita);
  245.         return arvesq;
  246.     }
  247. }
  248.  
  249.  
  250. void deletarArvore(Arv* arvore)
  251. {
  252.     if ( arvore != NULL )
  253.     {
  254.         deletarArvore( arvore->esquerda );
  255.         deletarArvore( arvore->direita );
  256.         delete(arvore);
  257.     }
  258. }
  259.  
  260. Arv* deletar2(Arv* arv, int t, int qtd, int &nivel, int &quantidade, bool &removeu, int n = 0)
  261. {
  262.  
  263.  
  264.     nivel = n;
  265.     Arv* temp;
  266.     if(arv==NULL)
  267.     {
  268.  
  269.     }
  270.     else if(t < arv->tipo)
  271.     {
  272.         arv->esquerda = deletar2(arv->esquerda, t, qtd, nivel, quantidade, removeu, n+1);
  273.     }
  274.     else if(t > arv->tipo)
  275.     {
  276.         arv->direita = deletar2(arv->direita, t, qtd, nivel, quantidade, removeu, n+1);
  277.     }
  278.     else
  279.     {
  280.  
  281.         if(arv->direita && arv->esquerda)
  282.         {
  283.             if (qtd >= arv->quantidade)
  284.             {
  285.                 /* Pega o menor el. da sub arvore a direita e substitui */
  286.                 temp = pegaMenorDireita(arv->direita);
  287.                 arv -> tipo = temp->tipo;
  288.                 arv -> quantidade = temp->quantidade;
  289.                 /* Deletar o no que substituiu pra nao ficar repetido */
  290.                 arv -> direita = removerMinimoDireita(arv->direita);
  291.                 removeu = true;
  292.             }
  293.             else
  294.             {
  295.                 arv->quantidade -= qtd;
  296.                 quantidade = arv->quantidade;
  297.             }
  298.         }
  299.         else
  300.         {
  301.             /* Se tiver zero ou 1 filhos */
  302.             if (qtd >= arv->quantidade)
  303.             {
  304.                 temp = arv;
  305.                 if(arv->esquerda == NULL)
  306.                     arv = arv->direita;
  307.                 else if(arv->direita == NULL)
  308.                     arv = arv->esquerda;
  309.                 delete(temp);
  310.  
  311.                 removeu = true;
  312.             }
  313.             else
  314.             {
  315.                 arv->quantidade -= qtd;
  316.                 quantidade = arv->quantidade;
  317.             }
  318.         }
  319.     }
  320.     return arv;
  321.  
  322. }
  323.  
  324.  
  325.  
  326. //void teste()
  327. //{
  328. //
  329. //    Arv* teste = inicializar();
  330. //    teste = inserir (2, 20, teste, _nivel, _quantidade, _soma);
  331. //    teste = inserir(5, 20, teste, _nivel, _quantidade, _soma);
  332. //    teste = inserir(7, 10, teste, _nivel, _quantidade, _soma);
  333. //    teste = inserir(6, 50, teste, _nivel, _quantidade, _soma);
  334. //    teste = inserir (9, 20, teste, _nivel, _quantidade, _soma);
  335. //    teste = inserir (4, 50, teste, _nivel, _quantidade, _soma);
  336. //    teste = inserir (11, 0, teste, _nivel, _quantidade, _soma);
  337. //    teste = inserir (10, 0, teste, _nivel, _quantidade, _soma);
  338. //    teste = inserir (12, 5, teste, _nivel, _quantidade, _soma);
  339. //    teste = inserir (8, 44, teste, _nivel, _quantidade, _soma);
  340. //
  341. //    remover(7, 20, teste);
  342. //    //  remover(teste, 10, 0);
  343. ////   remover(teste, 11, 0);
  344. ////   remover(teste, 7, 0);
  345. ////    remover(teste, 6, 0);
  346. //
  347. //
  348. //
  349. //
  350. //    printf("Pre Ordem:\n");
  351. //    preOrdem(teste);
  352. //    printf("\nPos Ordem:\n");
  353. //    posOrdem(teste);
  354. //    printf("\nEm Ordem:\n");
  355. //    emOrdem(teste);
  356. //
  357. //}
  358.  
  359.  
  360. int main()
  361. {
  362.     freopen("L2Q1.in", "r", stdin);
  363.     freopen("L2Q1.out", "w", stdout);
  364.  
  365. //    teste();
  366.     int comando = 0, tipo = 0, quantidade = 0;
  367.  
  368.     int operacoes;
  369.  
  370.     while (scanf("%d", &operacoes) != EOF)
  371.     {
  372. //        printf("Operacoes: %d\n", operacoes);
  373.  
  374.         getchar();
  375.         Arv* arvore = new Arv();
  376.         arvore = inicializar();
  377.         while (operacoes > 0)
  378.         {
  379.  
  380.             char linha [30];
  381.             fgets(linha, 30, stdin);
  382.             int num = sscanf(linha, "%d %d %d", &comando, &tipo, &quantidade);
  383. //            if (comando == 1)
  384. //                printf("Numero da operacao: %d. Tipo: %d. Quantidade: %d\n", operacoes, tipo, quantidade);
  385. //            else if (comando == 2)
  386. //                printf("Numero da operacao: %d. Tipo: %d. Quantidade: %d\n", operacoes, tipo, quantidade);
  387. //            else if (comando == 3)
  388. //                printf("Numero da operacao: %d. Tipo: %d.\n", operacoes, tipo);
  389. //            else
  390. //                 printf("Numero da operacao: %d. Tipo: %d.\n", operacoes, tipo);
  391.  
  392.             //3 ints lidos, comando 1 e 2
  393.             if (num == 3)
  394.             {
  395.                 if (comando == 1)
  396.                 {
  397.                     arvore = inserir(tipo, quantidade, arvore, _nivel, _quantidade);
  398.                     printf("%d %d\n", _nivel, _quantidade);
  399.                     _nivel = 0;
  400.                     _quantidade = 0;
  401.                 }
  402.                 else if (comando == 2)
  403.                 {
  404.                     arvore = deletar2(arvore, tipo, quantidade, _nivel, _quantidade, _removeu);
  405.                     if (!_removeu)
  406.                     {
  407.                         if (_quantidade != 0) //Se removeu quantidade
  408.                         {
  409.                             printf("%d %d\n", _nivel, _quantidade);
  410.                         }
  411.                         else
  412.                         {
  413.                             //Imprime nada
  414.                         }
  415.                     }
  416.                     else
  417.                     {
  418.                         printf("%d\n", _nivel);
  419.                         _removeu = false;
  420.                     }
  421.                     _nivel = 0;
  422.                     _quantidade = 0;
  423.  
  424.                 }
  425.             }
  426.             else if (num == 2)     //2 ints lidos ~comando 3
  427.             {
  428.  
  429.                 if (buscaNo(arvore, tipo, _nivel, _quantidade))   //Se encontrou
  430.                 {
  431.                     printf("%d %d\n", _nivel,_quantidade);
  432.  
  433.                 }
  434.                 else
  435.                 {
  436.                     //Imprime nada
  437.                 }
  438.                 _nivel = 0;
  439.                 _quantidade = 0;
  440.             }
  441.             else  //num = 1
  442.             {
  443.                 if (comando == 4)
  444.                 {
  445.                     Arv* maior = pegaMaiorElemento(arvore);
  446.                     emOrdem(arvore, maior);
  447.                     if (arvore != NULL)
  448.                         printf("\n");
  449.                 }
  450.                 else if (comando == 5)
  451.                 {
  452.                     posOrdem(arvore);
  453.                     if (arvore != NULL)
  454.                         printf("\n");
  455.                 }
  456.                 else if (comando == 6)
  457.                 {
  458.                     preOrdem(arvore);
  459.                     if (arvore != NULL)
  460.                         printf("\n");
  461.                 }
  462.  
  463.             }
  464.  
  465.  
  466.             operacoes--;
  467.         }
  468.         printf("\n");
  469.  
  470.     }
  471.     return 0;
  472. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!