Jump to content
flistergod

Procurar nós em árvores binárias

Recommended Posts

flistergod

Estou a fazer um trabalho em que peço ao utilizador para escrever um texto.

Depois pego nas palavras desse texto e insiro cada uma delas numa árvore binária e a cada nó da árvore está associado uma string e um contador (no case de haver palavras repetidas)

O inserir já está.

Mas o meu professor pede para procurarmos por palavras, ou seja, o utilizador escreve uma palavra ou um bocado dela e todas as palavras na árvore que começarem por esse bocado têm de ser imprimidas.

Até agora eu tenho assim:

Se tiver na árvore as palavras "casa", "casamento", só é imprimida a primeira palavra e não sei porquê. Alguém me pode ajudar?

 

void procura( String x ) {

        if(x.length()==0) {
            listarPosOrdem(raiz); // se o utilizar não introduzir nada, imprimo todas as palavras da árvore, funciona.
            return;
        }
        No actual = raiz;


        if(actual==null){
            System.out.println("palavra nao encontrada");
            return;

        };    
        if(actual.oElemento.startsWith(x)==true){
            System.out.println("Palavras encontradas: ");
            System.out.println(actual.oElemento + " encontrada "  + actual.contador + " vez(es) ");
        }


        while( actual != null && actual.oElemento.startsWith(x)==false){

            if( x.compareTo(actual.oElemento)>0 ){
                actual = actual.dir;
            }
            else
                actual = actual.esq;

            if(actual==null){
                System.out.println("palavra nao encontrada");
                return;

            }

            if(actual.oElemento.startsWith(x)==true){
                System.out.println("Palavras encontradas: ");
                System.out.println(actual.oElemento + " encontrada "  + actual.contador + " vez(es) ");


            }    


        }    
    }
 

Share this post


Link to post
Share on other sites
HappyHippyHippo

3 pontos:

- se o problema é de java, então deveria estar nessa secção

- o teu ciclo tem como condição de paragem exactamente o terres encontrado uma string validada

- já ouviste falar de funções recursivas ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
HappyHippyHippo
19 hours ago, HappyHippyHippo said:

- já ouviste falar de funções recursivas ?

 


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
flistergod

assim ? 

private No procurarRec( No raiz, String procurado ){
        if( raiz == null || raiz.oElemento.startsWith(procurado ))
        return raiz;
        
        if( procurado.compareTo( raiz.oElemento)>0 )
        return procurarRec( raiz.dir, procurado);
        else
        return procurarRec( raiz.esq, procurado);
        }

Share this post


Link to post
Share on other sites
HappyHippyHippo

quase

isso realmente é uma pesquisa em profundidade da árvore de forma recursiva, no entanto, é uma pesquisa que para quando encontra uma entrada que valida a condição.

necessitas de obter uma lista e não somente um único resultado


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.