Como criar uma árvore binária em C. Árvores binárias em C são uma boa maneira de organizar dados dinamicamente para facilitar a pesquisa. No entanto, eles exigem muito trabalho para manter.
Crie a árvore binária
Etapa 1
Estruture sua árvore binária. Toda árvore binária precisará de uma estrutura, mesmo que tenha apenas uma variável. Escolha um nome e use typedef para criá-lo:typedef struct student_data STUDENT_DATA;
Etapa 2
Defina a estrutura. Inclua dois ponteiros para a mesma estrutura:struct student_data { int student_ID; int aluno_classe; STUDENT_DATA
esquerda, certo;};
Etapa 3
Aloque um ponteiro para esta estrutura de dados, inicializando-a com NULL, para ser a cabeça da árvore:STUDENT_DATA *students =NULL;
Adicionar à árvore binária
Etapa 1
Aloque dois ponteiros temporários para a estrutura de dados:STUDENT_DATA
new_student, cur_aluno;
Etapa 2
Use malloc() para criar um novo elemento, sempre verificando se há um erro:if ((new_student =malloc(sizeof(STUDENT_DATA))) ==NULL) { abort(); }
Etapa 3
Preencha os campos do novo elemento. Defina seus campos esquerdo e direito como NULL:new_student->student_ID =newID;new_student->student_size =newsize;new_student->left =NULL;new_student->right =NULL;
Etapa 4
Considere a variável head. Se a variável head for NULL, este é o primeiro elemento adicionado à árvore, então defina a variável head para apontar para ela e pronto:if (!students) { students =new_student; Retorna; }
Etapa 5
Comece no topo da árvore:cur_student =students;while (cur_student) {
Etapa 6
Manipule a entrada duplicada se o novo valor e o valor atual forem iguais:if (newID ==cur_student->student_ID) { abort(); }
Etapa 7
Lidar com valores desiguais. Se o novo valor for menor que o valor atual, o novo elemento vai para a esquerda. Adicione-o imediatamente se não houver nada à esquerda. Caso contrário, percorra para a esquerda e faça um loop:if (newID
student_ID) { if (cur_student->left ==NULL) { cur_student->left =newstudent; retorno 1; } cur_student =cur_student->left;
Etapa 8
Faça a mesma coisa à direita, caso contrário:} else { if (cur_student->right ==NULL) { cur_student->right =newstudent; retorno 1; } cur_student =cur_student->right; }}
Pesquise na árvore binária
Etapa 1
Crie uma variável temporária apontando para a estrutura de dados:STUDENT_DATA *cur_student;
Etapa 2
Defina sua variável temporária para a variável head:cur_student =students_head;
Etapa 3
Percorra os elementos, verificando o valor desejado:while (cur_student) { if (cur_student->student_ID ==15) { return cur_student->student_grade; }
Etapa 4
Ramifique para a esquerda ou direita e faça um loop, se não for encontrado:if (cur_student->student_ID <15) { cur_student =cur_student->right; } else { cur_student =cur_student->left; }
Etapa 5
Veja se o loop termina. Se isso acontecer, significa que você nunca encontrou o item:}return 0;
Limpar
Etapa 1
Desaloque a árvore binária quando seu programa terminar, pois nem todos os sistemas operacionais irão lidar com isso automaticamente. Isso é feito melhor usando uma função recursiva:void deallocate_binary_tree(STUDENT_DATA *tree) {
Etapa 2
Observe:Se não houver nenhuma árvore, não há nada a fazer:if (!tree) return;
Etapa 3
Desaloque as subárvores esquerda e direita recursivamente:deallocate_binary_tree(tree->left); deallocate_binary_tree(árvore->direita);
Etapa 4
Desaloque o elemento e pronto:free(tree);}
Dica
Pesquisar e adicionar a árvores binárias também pode ser feito usando recursão. Isso será muito mais fácil de escrever e manter, mas um pouco mais difícil de entender, até que você se acostume. É comum criar uma árvore binária que contém apenas ponteiros para uma segunda estrutura de dados C, geralmente uma matriz ou lista vinculada, onde residem os dados reais. Cada árvore binária é um índice para pesquisar rapidamente um único campo dos dados da lista.
Aviso
A exclusão de uma árvore binária é um algoritmo muito complicado em C, mas em muitos usos de árvores binárias, os elementos nunca são excluídos.
