Exclusão em arvore!

[marcianorott]

E aí galera, beleza? To com bastante dificuldade em implementar uma função em C que exclua numa arvore binária! A de inserção consegui.

Se alguém tiver condições de me ajudar ficaria muito agradecido. **De preferencia onde não use recursividade.

minha estrutura é essa:

typedef struct def_arvore
        {
           int  Dado;
           struct def_arvore    *FilhoEsq;
           struct def_arvore    *FilhoDir;
           struct def_arvore    *Pai;
        }  tipo_arvore;

tipo_arvore *nodo=NULL; // definindo meu nodo inicial como NULL

Falow pessoal abraço!

[KaKarotto]

Aonde está realmente sua dúvida?

Eu recomento a você montar o algoritmo primeiro removendo um elemento filho que não tenha outros filhos, e depois trate das excessões, como o filho ser um nó interno por exemplo. Acho mais fácil...

Lembre-se que deve fazer a troca de elementos para manter a in-ordem. Botar no papel ajuda.

Abraço

[Guest --Marciano --]

Minha dúvida está na exclusão de Nodos com Filho a esquerda e Direita

[KaKarotto]

Suba sempre o filho da direita, caso for uma árvore de busca. Se for uma árvore de busca, o filho da direita sempre vai ser maior que o pai, portanto, é ele quem vai substituí-lo.

Aquele abraço.

[Guest --marcianorott --]

Caso o dado a excluir seja a Raiz ??? if( nodo->pai == NULL)

[KaKarotto]

Como é uma arvore de busca, o algoritmo que já deve ter implementado é o de percorrer nessa árvore. Esse algoritmo vai ser muito necessário na hora da remoção, que eu considero a parte mais crítica da arvore.

Então o que deve fazer é pegar o nodo que antecede o pai, percorrendo a árvore em in-ordem.

8

/ \

4 12

/ \ /\

2 6 10 14

Percorrendo em in-ordem : 2 - 4 - 6 - 8 - 10 - 12 - 14

Removendo a raiz 8, o nodo anterior ao 8 é o 6. Suba o 6, nesse caso o 6 não tem filho, o 4 acaba tendo o filho direito como folha.

  6

/ \

4 12

/ \ /\

2 ^ 10 14

Você sabe que fez a coisa certa, se percorrer a in-ordem e os nodos continuarem em ordem:

in-ordem: (filho esquerdo, pai, filho direito)

2-4-6-10-12-14

[KaKarotto]

Suba sempre o filho da direita, caso for uma árvore de busca. Se for uma árvore de busca, o filho da direita sempre vai ser maior que o pai, portanto, é ele quem vai substituí-lo.

Perdão, aqui eu esqueci de um detalhe. Isso apenas quando o nó a ser escolhido tem dois filhos, e esses filhos não tem filhos.

No caso de ter, a remoção é idêntica ao caso descrito antes, da raiz.

[Guest --marcianorott --]

no inicio tentei fazer sem recursividade, depois de ler alguns foruns e apostilas resolvi aplicar recursividade.Porém, to com uma dúvida.... como que faço no MAIN para receber o valor a excluir da arvore... vou postar a função e a idéia da opção retira

t

ipo_arvore *retira (tipo_arvore* aux, int v)

{
tipo_arvore *pai,*f,*t;
            
   if (aux == NULL)
      return NULL;
   else 
   if (aux->Dado > v)
      aux->FilhoEsq = retira(aux->FilhoEsq, v);
   else 
   if (aux->Dado < v)      
      aux->FilhoDir = retira(aux->FilhoDir, v);
   else   /* achou o elemento */
   { 
   if (aux->FilhoEsq == NULL && aux->FilhoDir == NULL)   /* elemento sem filhos */
   { 
       free (aux);
       aux = NULL;
   }
   else 
   if (aux->FilhoEsq == NULL) /* só tem filho à direita */
   { 
       
      t = aux;
      aux = aux->FilhoDir;
      free (t);
   }
   else
   if (aux->FilhoDir == NULL)  /* só tem filho à esquerda */ 
   { 
       
      t = aux;
      aux = aux->FilhoEsq;
      free (t);
   }
   else           /* tem os dois filhos */
   { 
      
      pai = aux;
    
      f = aux->FilhoEsq;
   while (f->FilhoDir != NULL) 
   {
      pai = f;
      f = f->FilhoDir;
   }
   aux->Dado = f->Dado; /* troca as informações */
   f->Dado = v;
   aux->FilhoEsq = retira(aux->FilhoEsq,v);
}
}
    return aux;
}


// aqui minha duvida: Como que passo o valor que a pessoa digitou para dentro da função. Antes da recursividade eu fazia com o valor to tipo INT
 case '3':
       printf("Digite o valor a ser removido \n");
       scanf("%d",&vl);
       resultado(nodo,10);

[KaKarotto]

Não muda. Continua ainda tendo que procurar um número inteiro. É a mesma coisa.

Desculpe por não conseguir ajudar com códigos, mas estou sem um compilador de C/C++.

Vou tentar te ajudar com a lógica, já que deu pra perceber que sabe programar direitinho, vai conseguir.

Uma dica que dou é, use funções para ir solucionando pequenos problemas, pensa na parte específica, depois vá para o todo.

Use uma função chamada busca(int); que retorne um ponteiro para o nodo achado.

Olha:

busca(4) retornaria o nodo que contem o valor 4. Daí você já tem um retorno que possui 3 ponteiros. Que apontam para 8, 2 e 6. Então, você usaria esse ponteiro para passar como parâmetro para a função remove, que teria seu próprio algoritmo para remover.