Ol\u00e1, pessoal.<\/p>\n
Abaixo, o c\u00f3digo da \u00c1rvore AVL da aula de ontem (a que voc\u00eas fizeram), com a fun\u00e7\u00e3o para imprimir a \u00e1rvore graficamente. Comentei tudo pra facilitar o entendimento e aproveitei pra melhorar algumas coisas no menu de op\u00e7\u00f5es. Para inserir os elementos da \u00e1rvore, n\u00e3o precisa mais ir de um por um, pode digitar todos os elementos separados por espa\u00e7os (na ordem em que deseja inserir), teclar ENTER e depois, CTRL+D.<\/p>\n
A constante TELA pode ser alterada para aumentar ou diminuir o tamanho da tela do seu terminal (em colunas).<\/p>\n
\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n#include <math.h>\r\n#include <list>\r\n\r\n\/\/ Tamanho da tela em colunas (para impress\u00e3o da \u00e1rvore)\r\n#define TELA 64\r\n\r\nusing namespace std;\r\n\r\n\/* Estrutura de um n\u00f3 *\/\r\nstruct no\r\n{\r\n int chave;\r\n int nivel; \/\/ Para impress\u00e3o em gr\u00e1fico\r\n int pos; \/\/ Para impress\u00e3o em gr\u00e1fico\r\n struct no *p;\r\n struct no *e;\r\n struct no *d;\r\n};\r\n\r\n\/\/ Imprime a \u00e1rvore graficamente\r\n\/\/ A posi\u00e7\u00e3o de cada elemento ser\u00e1 relativa ao seu n\u00edvel na \u00e1rvore\r\n\/\/ Por isso usa a equa\u00e7\u00e3o (TELA \/ 2^(nivel + 2)) para determinar o quanto\r\n\/\/ o elemento deve variar para cada lado\r\nvoid imprime_graf(struct no *raiz)\r\n{\r\n list<struct no *> fila; \/\/ Fila para manuten\u00e7\u00e3o da impress\u00e3o\r\n int nivel_ant = 0; \/\/ Indica o n\u00edvel do n\u00f3 impresso anteriormente\r\n int pos_filho; \/\/ Usado para calcular a posi\u00e7\u00e3o do filho do n\u00f3 atual\r\n int linha_pos = 0; \/\/ Calcula quantas casas j\u00e1 foram movimentadas em uma linha\r\n\r\n \/\/ Inicializa o n\u00edvel e a posi\u00e7\u00e3o da ra\u00edz e insere na fila\r\n raiz->nivel = 0;\r\n raiz->pos = TELA \/ 2;\r\n fila.push_back(raiz);\r\n\r\n \/\/ Enquanto houver elementos na fila, imprime!\r\n while (!fila.empty())\r\n {\r\n \/\/ Pega o primeiro elemento da fila\r\n struct no *temp = fila.front();\r\n fila.pop_front();\r\n\r\n \/\/ Se o n\u00edvel deste novo elemento for maior que o do anterior, significa\r\n \/\/ que ele deve ficar na linha abaixo. Atualiza o n\u00edvel e a posi\u00e7\u00e3o\r\n \/\/ atual da linha\r\n if (temp->nivel > nivel_ant)\r\n {\r\n printf("\\n");\r\n nivel_ant = temp->nivel;\r\n linha_pos = 0;\r\n }\r\n\r\n \/\/ Insere espa\u00e7os at\u00e9 a posi\u00e7\u00e3o de um prov\u00e1vel filho que esse n\u00f3 possa\r\n \/\/ ter \u00e0 esquerda\r\n pos_filho = temp->pos - (TELA \/ pow(2, temp->nivel + 2));\r\n for (int i = linha_pos; i < pos_filho; i++)\r\n linha_pos += printf(" ");\r\n\r\n \/\/ Verifica se o elemento tem filho \u00e0 esquerda. Se tiver, insere tra\u00e7os.\r\n \/\/ Caso contr\u00e1rio, insere espa\u00e7os\r\n if (temp->e != NULL) linha_pos += printf("|");\r\n for (int i = linha_pos; i < temp->pos; i++)\r\n temp->e != NULL ? linha_pos += printf("-") : linha_pos += printf(" ");\r\n\r\n \/\/ Imprime o elemento atual e atualiza a posi\u00e7\u00e3o na linha.\r\n linha_pos += printf("%d", temp->chave);\r\n\r\n \/\/ Verifica se o elemento tem filho \u00e0 direita. Se tiver, posiciona no\r\n \/\/ local onde o filho ser\u00e1 impresso abaixo e insere tra\u00e7os.\r\n if (temp->d != NULL)\r\n {\r\n pos_filho = temp->pos + (TELA \/ pow(2, temp->nivel + 2));\r\n for (int i = linha_pos; i < pos_filho; i++)\r\n linha_pos += printf("-");\r\n linha_pos += printf("|");\r\n }\r\n\r\n \/\/ Insere os filhos deste elemento na fila, armazenando suas posi\u00e7\u00f5es.\r\n if (temp->e != NULL)\r\n {\r\n temp->e->nivel = temp->nivel + 1;\r\n temp->e->pos = temp->pos - (TELA \/ pow(2, temp->e->nivel + 1));\r\n fila.push_back(temp->e);\r\n }\r\n\r\n if (temp->d != NULL)\r\n {\r\n temp->d->nivel = temp->nivel + 1;\r\n temp->d->pos = temp->pos + (TELA \/ pow(2, temp->d->nivel + 1));\r\n fila.push_back(temp->d);\r\n }\r\n }\r\n\r\n printf("\\n\\n");\r\n}\r\n\r\n\/* Cria um n\u00f3 *\/\r\nstruct no *criar(int chave)\r\n{\r\n struct no *novo = (struct no *)malloc(sizeof(struct no));\r\n novo->chave = chave;\r\n novo->p = novo->e = novo->d = NULL;\r\n}\r\n\r\n\/* Rotaciona n\u00f3 para direita *\/\r\nvoid girar_direita(struct no **raiz)\r\n{\r\n struct no *temp = *raiz;\r\n struct no *temp_esquerda = (*raiz)->e;\r\n temp->e = temp_esquerda->d;\r\n temp_esquerda->d = temp;\r\n temp_esquerda->p = temp->p;\r\n temp->p = temp_esquerda;\r\n *raiz = temp_esquerda;\r\n}\r\n\r\n\/* Rotaciona n\u00f3 para esquerda *\/\r\nvoid girar_esquerda(struct no **raiz)\r\n{\r\n struct no *temp = *raiz;\r\n struct no *temp_direita = (*raiz)->d;\r\n temp->d = temp_direita->e;\r\n temp_direita->e = temp;\r\n temp_direita->p = temp->p;\r\n temp->p = temp_direita;\r\n *raiz = temp_direita;\r\n}\r\n\r\n\/* Calcula a altura de uma \u00e1rvore *\/\r\nint altura(struct no *raiz)\r\n{\r\n if(raiz == NULL)\r\n return 0;\r\n\r\n int e = altura(raiz->e);\r\n int d = altura(raiz->d);\r\n int m;\r\n\r\n if (e > d)\r\n m = e;\r\n else\r\n m = d;\r\n\r\n return m + 1;\r\n}\r\n\r\n\r\n\/* Calcula o fator de balanceamento de um n\u00f3 *\/\r\nint balanceamento(struct no *raiz)\r\n{\r\n return altura(raiz->d) - altura(raiz->e);\r\n}\r\n\r\n\/*Percorre a \u00e1rvore pelo m\u00e9todo da p\u00f3s-ordem em busca de n\u00f3s desbalanceados *\/\r\nvoid verificar_balanceamento(struct no **raiz)\r\n{\r\n if ((*raiz) == NULL)\r\n return;\r\n\r\n verificar_balanceamento(&(*raiz)->e);\r\n verificar_balanceamento(&(*raiz)->d);\r\n\r\n if(balanceamento((*raiz)) == 2)\r\n {\r\n \/\/Rota\u00e7\u00e3o a esquerda\r\n if(balanceamento((*raiz)->d) == -1)\r\n girar_direita(&(*raiz)->d);\r\n girar_esquerda(&(*raiz));\r\n }\r\n else if(balanceamento((*raiz)) == -2)\r\n {\r\n \/\/Rota\u00e7\u00e3o a direita\r\n if(balanceamento((*raiz)->e) == 1)\r\n girar_esquerda(&(*raiz)->e);\r\n girar_direita(&(*raiz));\r\n }\r\n}\r\n\r\n\/* Adiciona elemento na \u00e1rvore *\/\r\nstruct no *adicionar(struct no *raiz, int chave)\r\n{\r\n struct no *novo = (struct no *)malloc(sizeof(struct no));\r\n if (raiz == NULL)\r\n {\r\n novo = criar(chave);\r\n return novo;\r\n }\r\n\r\n if (chave < raiz->chave)\r\n {\r\n novo = adicionar(raiz->e, chave);\r\n raiz->e = novo;\r\n novo->p = raiz;\r\n }\r\n else\r\n {\r\n novo = adicionar(raiz->d, chave);\r\n raiz->d = novo;\r\n novo->p = raiz;\r\n }\r\n\r\n verificar_balanceamento(&raiz);\r\n\r\n return raiz;\r\n}\r\n\r\n\/* Busca um n\u00f3 na \u00e1rvore *\/\r\nstruct no *buscar(struct no *raiz, int chave)\r\n{\r\n if(raiz == NULL)\r\n return NULL;\r\n if(raiz->chave == chave)\r\n return raiz;\r\n\r\n if(chave > raiz->chave)\r\n return buscar(raiz->d,chave);\r\n else\r\n return buscar(raiz->e,chave);\r\n}\r\n\r\n\/* Imprime a \u00e1rvore em ordem *\/\r\nvoid emordem(struct no *raiz)\r\n{\r\n if (raiz == NULL)\r\n return;\r\n\r\n emordem(raiz->e);\r\n printf("%d ",raiz->chave);\r\n emordem(raiz->d);\r\n}\r\n\r\n\/* Imprime a \u00e1rvore em pr\u00e9-ordem *\/\r\nvoid preordem(struct no *raiz)\r\n{\r\n if (raiz == NULL)\r\n return;\r\n\r\n printf("%d ",raiz->chave);\r\n preordem(raiz->e);\r\n preordem(raiz->d);\r\n}\r\n\r\n\/* Imprime a \u00e1rvore em p\u00f3s-ordem *\/\r\nvoid posordem(struct no *raiz)\r\n{\r\n if (raiz == NULL)\r\n return;\r\n\r\n posordem(raiz->e);\r\n posordem(raiz->d);\r\n printf("%d ",raiz->chave);\r\n}\r\n\r\n\/* Retorna o m\u00ednimo de uma \u00e1rvore *\/\r\nstruct no *minimo(struct no *raiz)\r\n{\r\n if (raiz == NULL)\r\n return NULL;\r\n\r\n if (raiz->e == NULL)\r\n return raiz;\r\n\r\n return minimo(raiz->e);\r\n}\r\n\r\n\/* Retorna o m\u00e1ximo de uma \u00e1rvore *\/\r\nstruct no *maximo(struct no *raiz)\r\n{\r\n if (raiz == NULL)\r\n return NULL;\r\n\r\n if (raiz->d == NULL)\r\n return raiz;\r\n\r\n return maximo(raiz->d);\r\n}\r\n\r\n\/* Retorna o antecessor de um n\u00f3 *\/\r\nstruct no *antecessor(struct no *raiz)\r\n{\r\n if(raiz->e == NULL)\r\n {\r\n while(raiz->p != NULL && raiz->p->chave > raiz->chave )\r\n raiz = raiz->p;\r\n\r\n return raiz->p;\r\n }\r\n return maximo(raiz->e);\r\n}\r\n\r\n\/* Retorna o sucessor de um n\u00f3 *\/\r\nstruct no *sucessor(struct no *raiz)\r\n{\r\n if(raiz->d == NULL)\r\n {\r\n while(raiz->p != NULL && raiz->p->chave < raiz->chave )\r\n raiz = raiz->p;\r\n return raiz->p;\r\n }\r\n\r\n return minimo(raiz->d);\r\n\r\n}\r\n\r\n\/* Remove um n\u00f3 da \u00e1rvore e retorna a nova \u00e1rvore *\/\r\nstruct no* remover(struct no *arvore, int chave)\r\n{\r\n if(arvore == NULL)\r\n return NULL;\r\n\r\n struct no *raiz = buscar(arvore, chave);\r\n\r\n if (raiz == NULL)\r\n return arvore;\r\n\r\n \/\/ Remover NO sem Filhos\r\n if (raiz->e == NULL && raiz->d == NULL)\r\n {\r\n if(raiz->p != NULL)\r\n {\r\n if(raiz->p->chave >= raiz->chave)\r\n raiz->p->e = NULL;\r\n else\r\n raiz->p->d = NULL;\r\n free(raiz);\r\n }\r\n else\r\n {\r\n free(raiz);\r\n return NULL;\r\n }\r\n if (raiz == arvore)\r\n return NULL;\r\n }\r\n else\r\n {\r\n \/\/ Remover NO com 2 Filhos\r\n if (raiz->e && raiz->d != NULL)\r\n {\r\n struct no *ant = antecessor(raiz);\r\n raiz->chave = ant->chave;\r\n ant = remover(ant, ant->chave);\r\n }\r\n \/\/ Remover NO com 1 Filho\r\n else\r\n {\r\n \/\/ Reconectar Filho a Esquerda\r\n if(raiz->e != NULL)\r\n {\r\n if (raiz->p != NULL)\r\n {\r\n if(raiz->p->chave > raiz->chave) \/\/ Caso o pai seja maior\r\n raiz->p->e = raiz->e;\r\n else \/\/ Caso o pai seja menor\r\n raiz->p->d = raiz->e;\r\n }\r\n raiz->e->p = raiz->p;\r\n }\r\n \/\/ Reconectar Filho a Direita\r\n else\r\n {\r\n if (raiz->p != NULL)\r\n {\r\n if(raiz->p->chave < raiz->chave) \/\/ Caso o pai seja menor\r\n raiz->p->d = raiz->d;\r\n else \/\/ Caso o pai seja maior\r\n raiz->p->e = raiz->d;\r\n }\r\n raiz->d->p = raiz->p;\r\n\r\n free(raiz);\r\n }\r\n }\r\n }\r\n\r\n return arvore;\r\n}\r\n\r\n\/* Fun\u00e7\u00e3o principal *\/\r\nint main(void)\r\n{\r\n struct no *arvore = NULL;\r\n int opt, chave;\r\n\r\n do\r\n {\r\n printf("==============================\\n");\r\n printf("OPCOES:\\n\\n");\r\n printf("\\t[1] Adicionar\\n");\r\n printf("\\t[2] Listar\\n");\r\n printf("\\t[3] Remover\\n");\r\n printf("\\t[0] Sair\\n\\n");\r\n printf("Escolha: ");\r\n scanf("%d", &opt);\r\n\r\n switch(opt)\r\n {\r\n case 1:\r\n printf("\\n\\nDigite as chaves separadas por espacos, na ordem que deseja inserir, e pressione CTRL+D para finalizar: ");\r\n while (scanf("%d", &chave) != EOF)\r\n arvore = adicionar(arvore, chave);\r\n break;\r\n\r\n case 2:\r\n printf("==============================\\n");\r\n printf("IMPRESSAO DA ARVORE:\\n\\n");\r\n printf("Em ordem:\\n");\r\n emordem(arvore);\r\n printf("\\n\\n");\r\n printf("Pre ordem:\\n");\r\n preordem(arvore);\r\n printf("\\n\\n");\r\n printf("Pos ordem:\\n");\r\n posordem(arvore);\r\n printf("\\n\\n");\r\n printf("Grafico:\\n");\r\n imprime_graf(arvore);\r\n break;\r\n\r\n case 3:\r\n printf("==============================\\n");\r\n printf("Digite a chave a ser removida: ");\r\n scanf("%d", &chave);\r\n arvore = remover(arvore, chave);\r\n break;\r\n\r\n case 0:\r\n return 0;\r\n\r\n default:\r\n printf("Opcao invalida!\\n\\n");\r\n }\r\n } while(1);\r\n\r\n return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Ol\u00e1, pessoal. Abaixo, o c\u00f3digo da \u00c1rvore AVL da aula de ontem (a que voc\u00eas fizeram), com a fun\u00e7\u00e3o para imprimir a \u00e1rvore graficamente. Comentei tudo pra facilitar o entendimento e aproveitei pra melhorar algumas coisas no menu de op\u00e7\u00f5es. …<\/p>\n