Como criar uma árvore binária em C

Escrito por ehow contributor | Traduzido por yaakov ben levy
  • Compartilhar
  • Tweetar
  • Compartilhar
  • Pin
  • E-mail
Como criar uma árvore binária em C
Crie uma árvore binária em C (Ablestock.com/AbleStock.com/Getty Images)

As árvores binárias em C são uma boa maneira de organizar dados dinamicamente para uma busca mais fácil. Entretanto, a manutenção dessas árvores é trabalhosa.

Nível de dificuldade:
Desafiante

Outras pessoas estão lendo

Instruções

    Criando uma árvore binária

  1. 1

    Estruture sua árvore binária. Cada árvore binária precisa de uma estrutura, mesmo se ela tiver uma variável. Escolha um nome, depois use o typedef pra poder criá-la: typedef struct student_data STUDENT_DATA;

  2. 2

    Defina a estrutura. Inclua dois ponteiros para a mesma estrutura: struct student_data { int student_ID; int student_grade; STUDENT_DATA left, right;};

  3. 3

    Aloque o ponteiro para essa estrutura de dados, iniciando-o para NULL, para ser o cabeçalho da árvore: STUDENT_DATA *students = NULL;

    Adicione à árvore binária

  1. 1

    Aloque dois ponteiros temporários para a estrutura de dados: STUDENT_DATA new_student, cur_student;

  2. 2

    Utilize malloc() para poder criar um novo elemento, sempre verificando se há erros: if ((new_student = malloc(sizeof(STUDENT_DATA))) == NULL) { abort(); }

  3. 3

    Agora preencha os novos campos do elemento. Configure seus campos esquerdo e direito para NULL: new_student->student_ID = newID;new_student->student_size = newsize;new_student->left = NULL;new_student->right = NULL;

  4. 4

    Considere o cabeçalho da variável. Se for NULL, ele será o primeiro elemento a ser adicionado à árvore, então, configure-o para apontar a isso e pronto: if (!students) { students = new_student; return; }

  5. 5

    Comece do topo da árvore: cur_student = students;while (cur_student) {

  6. 6

    Manuseie a entrada duplicada se o novo valor e o valor atual forem iguais: if (newID == cur_student->student_ID) { abort(); }

  7. 7

    Lide com valores desiguais. Se o novo valor for menor que o valor atual, ele irá para a esquerda. Adicione-o permanentemente se não tiver nada à esquerda. Caso contrário, atravesse e dê um loop: if (newID < cur_student->student_ID) { if (cur_student->left == NULL) { cur_student->left = newstudent; return 1; } cur_student = cur_student->left;

  8. 8

    Faça a mesma coisa no valor da direita, caso contrário: } else { if (cur_student->right == NULL) { cur_student->right = newstudent; return 1; } cur_student = cur_student->right; }}

    Busque na árvore binária

  1. 1

    Crie um novo arquivo temporário apontando para a estrutura de dados: STUDENT_DATA *cur_student;

  2. 2

    Configure sua variável temporária para o cabeçalho da variável: cur_student = students_head;

  3. 3

    Dê um loop entre os elementos, verificando pelo valor desejado: while (cur_student) { if (cur_student->student_ID == 15) { return cur_student->student_grade; }

  4. 4

    Separe os dados da direita e da esquerda e dê um loop. Se ainda não for encontrado: if (cur_student->student_ID < 15) { cur_student = cur_student->right; } else { cur_student = cur_student->left; }

  5. 5

    Veja se o loop termina. Se sim, significa que você nunca encontrou o item: }return 0;

    Limpando

  1. 1

    Desaloque a árvore binária quando o programa terminar, pois nem todos os sistemas operacionais irão lidar com isso automaticamente. A melhor maneira é usando uma função recursiva: void deallocate_binary_tree(STUDENT_DATA *tree) {

  2. 2

    Observação: se não houver nenhuma árvore, não há nada que possa ser feito: if (!tree) return;

  3. 3

    Desaloque as subárvores direita e esquerda recursivamente: deallocate_binary_tree(tree->left); deallocate_binary_tree(tree->right);

  4. 4

    Desaloque o elemento e está tudo pronto: free(tree);}

Dicas & Advertências

  • A busca e a criação de árvores binárias poderão ser feitas também através de uma recursão. Essa maneira é até mais fácil de se escrever e manter, mas é um pouco mais difícil de entender, até você se acostumar com isso.
  • É comum criar uma árvore binária que contenha apenas ponteiros dentro de outra estrutura de dados no C, frequentemente com uma ordem ou uma lista vinculada, onde os dados atuais residem. Cada árvore binária é um índice para uma busca rápida em um único campo da lista de dados.
  • A remoção de uma árvore binária é um algoritmo muito complicado em C, porém, em muitas utilizações de árvores binárias, os elementos nunca são removidos.

Não perca

Filtro:
  • Geral
  • Artigos
  • Slides
  • Vídeos
Mostrar:
  • Mais relevantes
  • Mais lidos
  • Mais recentes

Nenhum artigo disponível

Nenhum slide disponível

Nenhum vídeo disponível