ATIVIDADE 1 - ESOFT - ESTRUTURA DE DADOS II - 52/2021
QUESTÃO 1
Uma árvore binária é um conjunto finito de elementos que está vazio ou é particionado em três subconjuntos disjuntos. O primeiro subconjunto contém um único elemento, chamado raiz da árvore. Os outros dois subconjuntos são em si mesmos árvores binárias, chamadas subárvores esquerda e direita da árvore original.
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
De acordo com a definição acima sobre árvores binárias, você deverá apresentar em linguagem C a estrutura de uma árvore binária dinâmica ou estática, além do método de inserção de elementos.
Soluções para a tarefa
Uma árvore binária (= binary tree) é um conjunto de registros que satisfaz certas condições. As condições não serão dadas explicitamente, mas elas ficarão implicitamente claras no contexto. Os registros serão chamados nós (poderiam também ser chamados células). Cada nó tem um endereço. Suporemos por enquanto que cada nó tem apenas três campos: um número inteiro e dois ponteiros para nós. Os nós podem, então, ser definidos assim:
typedef struct reg {
int conteudo; // conteúdo
noh *esq;
noh *dir;
} noh; // nó
Resposta:
Explicação:
Eu colocaria dessa seguinte forma
struct No
{
int numero;
struct No *esquerda;
struct No *direita;
};
typedef struct No No;
void criarArvore(No **pRaiz)
{
*pRaiz = NULL;
}
void insercao(No **pRaiz, int numero2)
{
if (*pRaiz == NULL)
{
*pRaiz=(No *)malloc(sizeof (No));
(*pRaiz)->esquerda=NULL;
(*pRaiz)->direita=NULL;
(*pRaiz)->numero=numero2;
}
else
{
if (numero2 < ((*pRaiz)->numero))
{
insercao(&((*pRaiz)->esquerda), numero2);
}
else
{
insercao(&((*pRaiz)->direita), numero2);
}
}
}
void remover(No **pRaiz, int numero){
if(*pRaiz == NULL){
printf("Numero nao existe na arvore!");
getch();
return;
}
if(numero < (*pRaiz)->numero)
remover(&(*pRaiz)->esquerda, numero);
else
if(numero > (*pRaiz)->numero)
remover(&(*pRaiz)->direita, numero);
else{
No *pAux = *pRaiz;
if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == NULL)){
free(pAux);
(*pRaiz) = NULL;
}
else{
if ((*pRaiz)->esquerda == NULL){
(*pRaiz) = (*pRaiz)->direita;
pAux->direita = NULL;
free(pAux); pAux = NULL;
}
else{
if ((*pRaiz)->direita == NULL){
(*pRaiz) = (*pRaiz)->esquerda;
pAux->esquerda = NULL;
free(pAux); pAux = NULL;
}
else{
pAux = MaiorDireita(&(*pRaiz)->esquerda);
pAux->esquerda = (*pRaiz)->esquerda;
pAux->direita = (*pRaiz)->direita;
(*pRaiz)->esquerda = (*pRaiz)->direita = NULL;
free((*pRaiz)); *pRaiz = pAux; pAux = NULL;
}
}
}
}
}
void exibirEmOrdem(No *pRaiz){
if(pRaiz != NULL){
exibirEmOrdem(pRaiz->esquerda);
printf("\n%i", pRaiz->numero);
exibirEmOrdem(pRaiz->direita);
}
}