Ol\u00e1, pessoal.<\/p>\n
Como prometido, aqui est\u00e1 o c\u00f3digo da \u00e1rvore bin\u00e1ria de busca. Lembrem-se: implementem o balanceamento (\u00c1rvore AVL) e entreguem at\u00e9 o dia 21\/04\/15 via e-mail.<\/p>\n
\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n\r\n\/* Estrutura de um n\u00f3 *\/\r\nstruct no\r\n{\r\n int chave;\r\n struct no *p;\r\n struct no *e;\r\n struct no *d;\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\/* 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\/* Cria um n\u00f3 *\/\r\nstruct no *criar(int chave)\r\n{\r\n struct no *novo = malloc(sizeof(struct no));\r\n novo->chave = chave;\r\n novo->p = novo->e = novo->d = NULL;\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\/* Adiciona elemento na \u00e1rvore *\/\r\nstruct no *adicionar(struct no *raiz, int chave)\r\n{\r\n if (raiz == NULL)\r\n {\r\n struct no *novo = criar(chave);\r\n return novo;\r\n }\r\n\r\n if (chave < raiz->chave)\r\n {\r\n struct no *novo = adicionar(raiz->e, chave);\r\n raiz->e = novo;\r\n novo->p = raiz;\r\n }\r\n else\r\n {\r\n struct no *novo = adicionar(raiz->d, chave);\r\n raiz->d = novo;\r\n novo->p = raiz;\r\n }\r\n\r\n return raiz;\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;\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;\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("Escolha uma opcao:\\n\\n");\r\n printf("1 - Adicionar\\n");\r\n printf("2 - Listar\\n");\r\n printf("3 - Remover\\n");\r\n printf("0 - Sair\\n");\r\n scanf("%d", &opt);\r\n\r\n switch(opt)\r\n {\r\n case 1:\r\n printf("\\n\\nDigite uma chave: ");\r\n scanf("%d", &chave);\r\n arvore = adicionar(arvore, chave);\r\n break;\r\n\r\n case 2:\r\n printf("\\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 break;\r\n\r\n case 3:\r\n printf("\\n\\nDigite 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 }\r\n while(1);\r\n\r\n return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Ol\u00e1, pessoal. Como prometido, aqui est\u00e1 o c\u00f3digo da \u00e1rvore bin\u00e1ria de busca. Lembrem-se: implementem o balanceamento (\u00c1rvore AVL) e entreguem at\u00e9 o dia 21\/04\/15 via e-mail. #include <stdio.h> #include <stdlib.h> \/* Estrutura de um n\u00f3 *\/ struct no { …<\/p>\n