Ir ao conteúdo
  • Comunicados

    • Gabriel Torres

      Seja um moderador do Clube do Hardware!   12-02-2016

      Prezados membros do Clube do Hardware, Está aberto o processo de seleção de novos moderadores para diversos setores ou áreas do Clube do Hardware. Os requisitos são:   Pelo menos 500 posts e um ano de cadastro; Boa frequência de participação; Ser respeitoso, cordial e educado com os demais membros; Ter bom nível de português; Ter razoável conhecimento da área em que pretende atuar; Saber trabalhar em equipe (com os moderadores, coordenadores e administradores).   Os interessados deverão enviar uma mensagem privada para o usuário @Equipe Clube do Hardware com o título "Candidato a moderador". A mensagem deverá conter respostas às perguntas abaixo:   Qual o seu nome completo? Qual sua data de nascimento? Qual sua formação/profissão? Já atuou como moderador em algo outro fórum, se sim, qual? De forma sucinta, explique o porquê de querer ser moderador do fórum e conte-nos um pouco sobre você.   OBS: Não se trata de função remunerada. Todos que fazem parte do staff são voluntários.
    • DiF

      Poste seus códigos corretamente!   21-05-2016

      Prezados membros do Fórum do Clube do Hardware, O Fórum oferece um recurso chamado CODE, onde o ícone no painel do editor é  <>     O uso deste recurso é  imprescindível para uma melhor leitura, manter a organização, diferenciar de texto comum e principalmente evitar que os compiladores e IDEs acusem erro ao colar um código copiado daqui. Portanto convido-lhes para ler as instruções de como usar este recurso CODE neste tópico:  
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.

Editado por AnsiC
  • 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!

 

Editado por fabiowa

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






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

×