Arvore N-aria - Implementacao e Conversao para Arvore Binaria

Árvore nária Profa Rachel Reis rachelreisufvbr Árvore nária Como seria a implementação de uma árvore nária Nesse tipo de árvore cada nó pode conter um número diferente de subárvores Árvore nária Solução 1 Criar ponteiros de acordo com o grau da árvore ou seja se a árvore tiver grau 5 cinco ponteiros serão criados Desvantagem Para nós com grau menor que 5 acontecerá de alguns ponteiros nunca serem usados Árvore nária Solução 2 Transformar a árvore nária em árvore binária Árvore nária Exemplo A C D B F E G Árvore nária Exemplo A B A C D B F E G Árvore nária Exemplo A B C D A C D B F E G Árvore nária Exemplo A B C D A C D B F E G Árvore nária Exemplo A B C D A C D B F E G E Árvore nária Exemplo A B C D A C D B F E G E Árvore nária Exemplo A B C D A C D B F E G E Árvore nária Exemplo A B C D A C D B F E G E F Árvore nária Exemplo A B C D A C D B F E G E F Árvore nária Exemplo A B C D A C D B F E G E F G Árvore nária Exemplo A B C D A C D B F E G E F G Árvore nária Exemplo A B C D A C D B F E G E F G 1 O primeiro filho de um nó passa a ser seu filho à esquerda na árvore binária Árvore nária Exemplo A B C D A C D B F E G E F G 1 O primeiro filho de um nó passa a ser seu filho à esquerda na árvore binária A B Árvore nária Exemplo A B C D A C D B F E G E F G 2 Os demais filhos de um nó passam a ser filhos à direita do seu irmão imediato à esquerda A B Árvore nária Exemplo A B C D A C D B F E G E F G 2 Os demais filhos de um nó passam a ser filhos à direita do seu irmão imediato à esquerda A B C Árvore nária Exemplo A B C D A C D B F E G E F G 2 Os demais filhos de um nó passam a ser filhos à direita do seu irmão imediato à esquerda A B C D Árvore nária Exemplo A B C D A C D B F E G E F G 1 O primeiro filho de um nó passa a ser seu filho à esquerda na árvore binária A B C D E Árvore nária Exemplo A B C D A C D B F E G E F G 1 O primeiro filho de um nó passa a ser seu filho à esquerda na árvore binária A B C D E F Árvore nária Exemplo A B C D A C D B F E G E F G A B C D E F 2 Os demais filhos de um nó passam a ser filhos à direita do seu irmão imediato à esquerda G Transformar Árvore nária em Binária Passos 1 O primeiro filho de um nó passa a ser seu filho à esquerda na árvore binária 2 Os demais filhos de um nó passam a ser filhos à direita do seu irmão imediato à esquerda 3 Executar o mesmo processo para cada nó da árvore Filho à esquerda primeiro filho Filho à direita irmão seguinte Reconstituição da Árvore nária Exemplo A B C D E F G J K L Reconstituição da Árvore nária Exemplo A B C D E F G J K L Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L A B C D Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L A B C D Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L A B C E D Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L A B C E D Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L A B C E J D Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L A B C D E J Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L A B C D E J F G L Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L A B C D E J F G L Reconstituição da Árvore nária Exemplo A B A B C D E F G J K L E C D J F K G L A B C D E J F G L K Reconstituição da Árvore nária Árvore original A B C D E J F G L K A C D B F E G Árvore modificada Transformar Florestra em Árvore binária A D F B C E G K L H I M J Floresta Basta considerar as raízes das árvores como nós irmãos e aplicar a conversão anterior Exercício Transforme a floresta abaixo em uma árvore binária A D F B C E G K L H I M J Floresta Referências Bibliográficas Ascencio A F G Araújo G S de 2010 Estruturas de Dados algoritmos análise da complexidade e implementações em JAVA e C São Paulo Pearson Prentice Hall Forbellone A L V Eberspacher H F 2005 Lógica de Programação A construção de algoritmos e estruturas de dados 3ª edição São Paulo Pearson Prentice Hall