2014/1: PA: Árvore digital em Java

package pa.arvore.digital01;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author aluno
 */
public class NoArvoreDigital {
    
    char caractere;
    List<NoArvoreDigital> nos;
    
    // construtor
    public NoArvoreDigital(char a)
    {
        this.caractere = a;
        nos = new ArrayList<NoArvoreDigital>();
    }
    
    // inserir palavra
    public boolean inserirPalavra(String palavra)
    {    // 1) obter a primeira letra
        if (palavra.length() == 0)
            return true;
        char letra = palavra.charAt(0);        
        if (palavra.length() > 1)
            palavra = palavra.substring(1);
        else
            palavra = "";
        // 2) verificar se a letra existe na arvore
        NoArvoreDigital no = obterNo(letra);
        if (no != null){// 3) Se ela existir
        // 3.1) obter o no correspondente                
        // 3.2) inserir o resto da palavra neste no
            return no.inserirPalavra(palavra);
        } else {  // 4) Se ela nao existir
        // 4.1) criar um novo nó com o caractere corrente                
            no = new NoArvoreDigital(letra);
            nos.add(no); // 4.2) Adicionar o no na lista de nos
        // 4.3) inserir o resto da palavra neste no
            return no.inserirPalavra(palavra);
        }       
    }
    
    public NoArvoreDigital obterNo(char letra)
    {
        for (NoArvoreDigital no: nos)
        {
            if (no.caractere == letra)
                return no;
        }
        return null;
    }

    @Override
    public String toString() {
        
        return "[" + caractere +"] -> " + 
                nos.toString();
    }
    
    // metodo que verifica se a palavra existe dentro da
    // arvore digital
    public boolean existe(String palavra)
    {
        // 1) obter o primeiro caractere
        if (palavra.length() == 0)
            return true;
        char letra = palavra.charAt(0);
        // 2) obter o restante da palavra
        if (palavra.length() > 1)
            palavra = palavra.substring(1);
        else
            palavra = "";
        // 3) Se o caractere existir no nó
        NoArvoreDigital no = obterNo(letra);
        if (no != null){
        // 3.1) buscar no nó que contem o caractere
            return no.existe(palavra);
        } else {// 4) Senao
        // 4.1) informar que a palavra não existe      
            return false;
        }
    }
    
    public void imprimir()
    {
        for (NoArvoreDigital no:nos)
        {
            System.out.print ("["+no.caractere+"] -> ");
            no.imprimir();
            System.out.println();
        }
    }
    
}

---

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package pa.arvore.digital01;

/**
 *
 * @author aluno
 */
public class PaArvoreDigital01 {

    /**
     * @param args the command line arguments
     */
    public static void main(String [] args)
    {
        NoArvoreDigital no = new NoArvoreDigital('*');
        no.inserirPalavra("texto");
        no.inserirPalavra("teste");
        no.inserirPalavra("casa");
        no.inserirPalavra("tomate");
        System.out.println(no);     
        no.imprimir();
        
        String palavra = "teste";
        System.out.println(palavra + "-> " + no.existe(palavra));
        palavra = "cas";
        System.out.println(palavra + "-> " + no.existe(palavra));
        palavra = "teto";
        System.out.println(palavra + "-> " + no.existe(palavra));
        
    }
    
}