Ir ao conteúdo
  • Cadastre-se
fabiowa

C Função de busca e altura em árvore não binária (com 4 ponteiros)

Recommended Posts

Olá a todos,

 

preciso de ajuda para solucionar um problema. Tenho uma árvore (que não é binária). Cada nó da árvore pode conter 4 filhos (possui 4 ponteiros). A árvore não é ordenada (e não posso ordená-la), entretanto o dado (int) não se repete em nenhum nó. Segue um exemplo de árvore.

 

                    11     

           /      |    |    \

         4       5    1     18

    /  | | \                     \

 2    0 7  20                  6

 

A estrutura da árvore é a seguinte (não posso construir ela com vetor de ponteiros).

 

struct tree {
   int info;
   struct tree* son1;
   struct tree* son2;
   struct tree* son3;
   struct tree* son4;
};

 

Preciso construir uma função que dada a árvore e um dado (int), descobra se o elemento existe ou não na árvore (pode retornar um valor bool mesmo). Além disso, preciso descobrir a altura dessa árvore. Tentei fazer tudo isso por recursão mas não obtive sucesso. A árvore binária (com 2 ponteiros para os filhos) é fácil de implementar, mas esta está me dando uma dor de cabeça tremenda. Alguém poderia me ajudar?

 

Desde já agradeço.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Olá !

Problema é notável, nunca vi dessa forma.

De imediato a ideia é usarmos lista:

 

Cada nó deve ser investigado sistematicamente do primeiro até o último de cada filho, sempre o filho numero 1 primeiro até o último nó dele. Se negativo investigamos o próximo filho sequencialmente da estrutura, se todos os filhos do último nó atual resultarem negativo,  então continua a busca a partir nó anterior guardado na pilha ou na lista.

 

O maior índice alcançado na pilha ou lista durante a busca na árvore é também sua altura.

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

Pois é. Não consegui implementar essa árvore. Sua complexidade é muito grande. Na verdade essa árvore resolveria o problema de encontrar o maior caminho possível em uma matriz 6x6 dos elementos com a mesma cor (números) que são vizinhos.

 

Exemplo de matriz.

 

1 3 4 5 6 2

2 2 2 4 2 2

1 2 4 5 3 2

3 3 4 2 2 2

2 5 5 5 3 3

4 1 1 2 4 4

 

O melhor caminho seria do elemento na posição [0][5] até a posição [3][3] (com 6 nós). A árvore que tivesse a maior altura teria consequentemente o maior path. O jeito foi implementar outra metodologia que não fizesse uso de árvore. O jeito foi coletar o path com o maior número de pontos em uma lista duplamente encadeada e permutar essa lista (achando todas as combinações possíveis com aquele grupo de elementos). A permutação que tiver o maior tamanho vai ser o melhor path. O problema é que se tiver um grupo com n pontos da mesma cor vizinhos, não necessariamente terei um caminho com n pontos, que é o caso da matriz acima (note que o elemento na posição [1][5] fica de fora do path). Além disso, a permutação de n elementos gera n! combinações. Consegui resolver esse problema implementado lista duplamente encadeada e permutação entre os elementos dessa lista. Com árvore a solução não funcionou.

 

Mesmo assim, obrigado!

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

ainda dá para fazer por recursão a busca. O fato dela não estar ordenada significa apenas que vai ficar mais lenta.

 

As árvores B (diferente de árvores binárias) funcionam assim. Inclusive, cada nó chega a ter 10 folhas

 

O algoritmo basicamente seria o seguinte

 

int busca( struct tree **noh , int valor) {
   if (*noh == NULL) { 
        return 0 ; /* não achou */ 
   } 
   return (&(*noh)->info == valor || 
            busca( &(*noh)->son1, valor ) || 
            busca( &(*noh)->son2, valor ) || 
            busca( &(*noh)->son3, valor ) || 
            busca( &(*noh)->son4, valor ) ) ;
}  

Para calcular a altura da árvore o algoritmo seria

           

int altura( struct tree ** noh) { 
   if (*noh == NULL) { 
        return 0 ; /* altura zero */ 
   } 
   int maior = altura(&(*noh)->son1);
   int walt2 = altura(&(*noh)->son2);
   int walt3 = altura(&(*noh)->son3);
   int walt4 = altura(&(*noh)->son4);
   if (walt2 > maior) maior = walt2;
   if (walt3 > maior) maior = walt3;
   if (walt4 > maior) maior = walt4;
   return wmaior+1;
} 

uma ideia seria usar um vetor em vez de 4 son's, se é que me entende. Assim faria as coisas com for e poderia ter mais sons.

Arquivos sequenciais indexados como ISAM e VSAM usam árvores-B. Mais aqui 

 

 


E tem ainda as árvores k-dimesionais. Essas sào muito looooouuuuucas bicho.

 

 

adicionado 5 minutos depois

A manha aí é o seguinte.

No C, quando você tem uma condiçào com OR (||) e ela dá verdadeira, não precisa testar a segunda parte

 

Por exemplo

 

 if ( (a>b) || (c > d) ) { 

     .faz alguma coisa

} else {

    faz outra coisa

}  

 

Se (a>b) for verdadeiro, a expressão (c>d) não será avaliada pois não precisa. O resultado já é true.

 

O contrário acontece com AND (&&). Se a primeira part for falso, a segunda expressão não será avaliada. O resultado já é false.

 

Portanto (a>b) || (c>d) é avaliado de forma diferente de (c >d) || (a >b) 

 

Porque estou dando essa explicação toda ???
Observe o código da busca. A expressão booleana é avaliada da esquerda para a direita. Quando uma das condições for satisfeita, as outras não serão avaliadas. Isso vai agilizar a busca.

 

 

adicionado 6 minutos depois

Experimente e conte para nós o resultado.

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Problema resolvido. Consegui implementar a árvore com os 4 ponteiros para os filhos. Na verdade, precisei utilizar mais 1 ponteiro ainda (para o nó pai). Acabei não utilizando a sua função, mas mesmo assim obrigado. Ao mesmo tempo que inseria um elemento na árvore, inseria o mesmo em uma lista encadeada. Assim era só pesquisar na lista, pois se o elemento estivesse na lista encadeada consequentemente estaria também na árvore (lembrando que os elementos não se repetem).

 

A implementação da árvore otimizou o tempo de execução do programa enormemente, já que não precisei mais permutar os elementos.

 

Mais uma vez, obrigado pela ajuda!

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×