[Resolvido] Percorrer árvore binária

[alves077]

Boa tarde,

Estou a resolver um problema, acho que ja consegui chegar a solução que quero, mas acho que pode ser melhorada. Basicamente tenho uma árvore que percorro de forma recursiva, cada nó está numerado, não de forma sequencialmente e pode se repetir o mesmo número. Tem um limite dado, e tenho que contar se as folhas fazem parte de um conjunto de número previamente definido.

Já consegui resolver o problema de forma simples, verifico todas as folhas percorrendo recursivamente, só que queria optimizar, não visitando todas as folhas, isto é não ter que verificar todas as possibilidades, alguma ideia como poderei descartar alguns ramos ?

Pensei em guardar o caminho que estou a percorrer se aparecer algum igual não seguir, mas sinceramente não sei muito bem como fazer, só gastaria mais tempo a verificar se o caminho actual já foi pesquisado... alguem me consegue alguma dica como optimizar a pesquisa ?

Obrigado pela ajuda,

alves077

[HappyHippyHippo]

se a árvore não está ordenada só tens uma solução : percorrer toda a árvore

[alves077]

Posso me ter explicado mal, mesmo não estando ordenada, e podendo repetir números, a relação dos nós é única. Isto é, se o nó 1 ramifica para 1,2, o nó esquerdo da raiz 1 será o 1 outra vez, logo o terceiro nível do lado esquerdo será (1,2) na mesma, logo existe aqui uma repetição, sendo que sei qual as folhas que interessam acho q se pode ignorar este tipo de ramos que não leva a lado nenhum. Só não sei ao certo onde posso tirar proveito de trabalho já realizado...

Edited February 14, 2014 at 08:34 PM by alves077

[HappyHippyHippo]

Posso me ter explicado mal

mas eu não

mas caso seja de difícil leitura deixo novamente o comentário:

se a árvore não está ordenada só tens uma solução : percorrer toda a árvore

explica lá como é que podes supor que valores existem nos ramos se esta não está ordenada ? e por consequente, como podes saber se estes valores estão dentro do teu grupo ?

[alves077]

Ok, na medida que não se consegue prever o futuro percebo o que dizes, mas mesmo sabendo que a relação é única e que a árvore tem um tamanho pré-definido não conseguirei aproveitar trabalho já realizado?

[HappyHippyHippo]

epa .. não sei porque continuas a teimar na expressão "relação única", eu até acho que nem tu deves saber o que estás a dizer ...

[alves077]

O que quero dizer é que determinado número terá sempre os mesmos dois "filhos".

Um exemplo de onde queria chegar, se o tamanho da minha árvore for 3 níveis, sabendo que 1 tem como filhos 1 e 2, e que nem 1 nem o 2 as folhas pretendidas, poderia não chamar o 3º nivel a árvore do lado esquerdo, porque posso saber que já analisei o 1 e o 2 e não são os pretendidos, e como a partir do 1 só consigo chegar ao 1 e 2, e que número máximo de níveis é 3, é uma ramificação desnecessária.

Edited February 14, 2014 at 11:28 PM by alves077

[HappyHippyHippo]

O que quero dizer é que determinado número terá sempre os mesmos dois "filhos".

E que tomam is ramos do valor 2? E do 3? E do 28462? E do 524372645?

[alves077]

Sim, eu percebo o que dizes, estava só a tentar perceber se posso cortar ou a aproveitando alguma coisa da recursividade, por exemplo guardo o caminho por onde vou passando, assim se estiver a seguir esse caminho e conhecer o tamanho máximo sabia q esse caminho não valeria a pena.

Mas mais do que não ir a ramos, o que pretendia era mesmo aproveitar trabalho feito, se é que me percebem, se já verifiquei determinado tipo de combinações podia guardar em memoria, mas.. sinceramente não sei bem como fazer, e se faz algum sentido o que estou a dizer... só estou tentar perceber onde posso melhorar...

[HappyHippyHippo]

e se faz algum sentido o que estou a dizer

nop, não faz

[alves077]

Ok, então se calhar vou desistir da minha ideia de optimizar isto...

Será que ganho alguma coisa em vez de percorrer a árvore ter uma matriz de adjacência ?

Não sei se fiz me entender, mas os números são sequenciais, só podem estar ligados a um qualquer, mas são sequenciais. Isto é se tiver uma árvore de tamanho 5, quer dizer que os nós da árvore são compostas pelo alfabeto = 1 a 5.

Obrigado pela atenção,

alves077

Edited February 15, 2014 at 03:44 PM by alves077

[HappyHippyHippo]

Ok, então se calhar vou desistir da minha ideia de optimizar isto...

existem hipóteses de optimização, pensa bem no que podes fazer. claro que passa sempre ou por ordenar a árvore ou estruturas auxiliares ...

Será que ganho alguma coisa em vez de percorrer a árvore ter uma matriz de adjacência ?

talvez em facilidade na criação do código, mas por outro lado tens a criação de uma estrutura auxiliar extra que aumenta quadraticamente com o número de nós da árvore)

[alves077]

Pois, mas se não passa por guardar alguns caminhos já realizados para não fazer o mesmo, não sei muito por onde optimizar. Mas tiver a matriz, supostamente já não preciso da árvore em si...

Não podes só dar uma dicas que caminho devo seguir? Já fiz várias tentativas mas só pioro o rendimento..

[HappyHippyHippo]

ordena a árvore ...