Baixe o app para aproveitar ainda mais
Prévia do material em texto
public class ArvoreArvore { private No raiz; public ArvoreArvore() { raiz = null; inserir('M'); inserir('T'); inserir('F'); } public void inserir(char letra){ } public void inserir(String s){ inserir(s, raiz); } public void inserir(String s, No i) throws Exception { if (i == null) { throw new Exception("Erro ao inserir: caractere invalido!"); } else if (s.charAt(0) < i.elemento) { inserir(x, i.esq); } else if (s.charAt(0) > i.elemento) { inserir(x, i.dir); } else { i.outro = inserir(s, i.outro); } } private No2 inserir(String s, No2 i) throws Exception { if (i == null) { i = new No2(x); } else if (s.compareTo(i.elemento) < 0) { i.esq = inserir(x, i.esq); } else if (s.compareTo(i.elemento) > 0) { i.dir = inserir(x, i.dir); } else { throw new Exception("Erro ao inserir: elemento existente!"); } return i; } public void mostrar(){ mostrar(raiz); } public void mostrar(No i){ if (i != null){ mostrar(i.esq); mostrar(i.outra); mostrar(i.dir); } } public void mostrar(No2 i){ if (i != null){ mostrar(i.esq); System.out.println(i.elemento); mostrar(i.dir); } } public boolean hasStringTam10(){ return hasStringTam10(raiz); } public boolean hasStringTam10(No i){ boolean resp = false; if(i != null){ resp = hasStringTam10(i.outro) || hasStringTam10(i.esq) || hasStringTam10(i.dir); } return resp; } public boolean hasStringTam10(No2 i){ boolean resp = false; if(i != null){ resp = i.elemento.length() == 10 || hasStringTam10(i.esq) || hasStringTam10(i.dir); } return resp; } public boolean hasStringTam10(char c){ return hasStringTam10(raiz, c); } public boolean hasStringTam10(No i, char c){ boolean resp; if (i == null) { resp = false; } else if (c < i.elemento) { resp = hasStringTam10(i.esq, c); } else if (c > i.elemento) { resp = hasStringTam10(i.dir, c); } else { resp = hasStringTam10(i.outro); } return resp; } public boolean pesquisar(String elemento) { return pesquisar(raiz, elemento); } private boolean pesquisar(No no, String x) { boolean resp; if (no == null) { resp = false; } else if (x.charAt(0) < no.elemento) { resp = pesquisar(no.esq, x); } else if (x.charAt(0) > no.elemento) { resp = pesquisar(no.dir, x); } else { resp = pesquisarSegundaArvore(no.outro, x); } return resp; } private boolean pesquisarSegundaArvore(No2 no, String x) { boolean resp; if (no == null) { resp = false; } else if (x.compareTo(no.elemento) < 0) { resp = pesquisarSegundaArvore(no.esq, x); } else if (x.compareTo(no.elemento) > 0) { resp = pesquisarSegundaArvore(no.dir, x); } else { resp = true; } return resp; } public int contPalavra(char letra){ return contPalavra(letra, raiz); } public int contPalavra(char letra, No i) throws Exception { int resp = 0; if (i == null) { throw new Exception("Erro ao pesquisar: caractere invalido!"); } else if (letra < i.elemento) { resp = contPalavra(letra, i.esq); } else if (letra > i.elemento) { resp = contPalavra(letra, i.dir); } else { resp = contPalavra(i.outro); } return resp; } public int contPalavra(No2 i){ int resp = 0; if(i != null){ resp = 1 + contPalavra(i.esq) + contPalavra(i.dir); } return resp; } } —---------------------------------------------------------------------------------------------------- class ArvoreTrie { private No raiz; public ArvoreTrie(){ raiz = new No(); } public boolean pesquisar(String s) throws Exception { return pesquisar(s, raiz, 0); } public boolean pesquisar(String s, No no, int i) throws Exception { boolean resp; public class ArvoreBinaria { private No raiz; public ArvoreBinaria() { raiz = null; } public boolean pesquisar(int x) { return pesquisar(x, raiz); } private boolean pesquisar(int x, No i) { boolean resp; if (i == null) { resp = false; } else if (x == i.elemento) { resp = true; } else if (x < i.elemento) { resp = pesquisar(x, i.esq); } else { resp = pesquisar(x, i.dir); } return resp; } public void caminharCentral() { System.out.print("[ "); caminharCentral(raiz); System.out.println("]"); } private void caminharCentral(No i) { if (i != null) { caminharCentral(i.esq); System.out.print(i.elemento + " "); caminharCentral(i.dir); } } public void caminharPre() { System.out.print("[ "); caminharPre(raiz); System.out.println("]"); } private void caminharPre(No i) { if (i != null) { System.out.print(i.elemento + " "); caminharPre(i.esq); caminharPre(i.dir); } } public void caminharPos() { System.out.print("[ "); caminharPos(raiz); System.out.println("]"); } private void caminharPos(No i) { if (i != null) { caminharPos(i.esq); caminharPos(i.dir); System.out.print(i.elemento + " "); } } public void inserir(int x) throws Exception { raiz = inserir(x, raiz); } private No inserir(int x, No i) throws Exception { if (i == null) { i = new No(x); } else if (x < i.elemento) { i.esq = inserir(x, i.esq); } else if (x > i.elemento) { i.dir = inserir(x, i.dir); } else { throw new Exception("Erro ao inserir!"); } return i; } public void inserirPai(int x) throws Exception { if(raiz == null){ raiz = new No(x); } else if(x < raiz.elemento){ inserirPai(x, raiz.esq, raiz); } else if(x > raiz.elemento){ inserirPai(x, raiz.dir, raiz); } else { throw new Exception("Erro ao inserirPai!"); } } private void inserirPai(int x, No i, No pai) throws Exception { if (i == null) { if(x < pai.elemento){ pai.esq = new No(x); } else { pai.dir = new No(x); } } else if (x < i.elemento) { inserirPai(x, i.esq, i); } else if (x > i.elemento) { inserirPai(x, i.dir, i); } else { throw new Exception("Erro ao inserirPai!"); } } public void remover(int x) throws Exception { raiz = remover(x, raiz); } private No remover(int x, No i) throws Exception { if (i == null) { throw new Exception("Erro ao remover!"); } else if (x < i.elemento) { i.esq = remover(x, i.esq); } else if (x > i.elemento) { i.dir = remover(x, i.dir); } else if (i.dir == null) { i = i.esq; } else if (i.esq == null) { i = i.dir; } else { i.esq = maiorEsq(i, i.esq); } return i; } private No maiorEsq(No i, No j) { if (j.dir == null) { i.elemento = j.elemento; j = j.esq; } else { j.dir = maiorEsq(i, j.dir); } return j; } public int getMaior(){ int resp = -1; if(raiz != null){ No i; for(i = raiz; i.dir != null; i = i.dir); resp = i.elemento; } return resp; } public int getMenor(){ int resp = -1; if(raiz != null){ No i; for(i = raiz; i.esq != null; i = i.esq); resp = i.elemento; } return resp; } public int getAltura(){ return getAltura(raiz, 0); } public int getAltura(No i, int altura){ if(i == null){ altura--; public class Alvinegra { private NoAN raiz; public Alvinegra() { raiz = null; } public boolean pesquisar(int elemento) { return pesquisar(elemento, raiz); } private boolean pesquisar(int elemento, NoAN i) { boolean resp; if (i == null) { resp = false; } else if (elemento == i.elemento) { resp = true; } else if (elemento < i.elemento) { resp = pesquisar(elemento, i.esq); } else { resp = pesquisar(elemento, i.dir); } return resp; } public void caminharCentral() { System.out.print("[ "); caminharCentral(raiz); System.out.println("]"); } private void caminharCentral(NoAN i) { if (i != null) { caminharCentral(i.esq); System.out.print(i.elemento + ((i.cor) ? "(p) " : "(b) ")); caminharCentral(i.dir); } } public void caminharPre() { System.out.print("[ "); caminharPre(raiz); System.out.println("]"); } private void caminharPre(NoAN i) { if (i != null) { System.out.print(i.elemento + ((i.cor) ? "(p) " : "(b) ")); caminharPre(i.esq); caminharPre(i.dir); } } public void caminharPos() { System.out.print("[ "); caminharPos(raiz); System.out.println("]"); } private void caminharPos(NoAN i) { if (i != null) { caminharPos(i.esq); caminharPos(i.dir); System.out.print(i.elemento + ((i.cor) ? "(p) " : "(b) ")); } } public void inserir(int elemento) throws Exception { if (raiz == null) { raiz = new NoAN(elemento); System.out.println("Antes, zero elementos. Agora, raiz(" + raiz.elemento + ")."); } else if (raiz.esq == null && raiz.dir == null) { if (elemento < raiz.elemento) { raiz.esq = new NoAN(elemento); System.out.println("Antes, um elemento. Agora, raiz(" + raiz.elemento+ ") e esq(" + raiz.esq.elemento + ")."); } else { raiz.dir = new NoAN(elemento); System.out.println("Antes, um elemento. Agora, raiz(" + raiz.elemento + ") e dir(" + raiz.dir.elemento + ")."); } } else if (raiz.esq == null) { if (elemento < raiz.elemento) { raiz.esq = new NoAN(elemento); System.out.println("Antes, dois elementos(A). Agora, raiz(" + raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento + ")."); } else if (elemento < raiz.dir.elemento) { raiz.esq = new NoAN(raiz.elemento); raiz.elemento = elemento; System.out.println("Antes, dois elementos(B). Agora, raiz(" + raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento + ")."); } else { raiz.esq = new NoAN(raiz.elemento); raiz.elemento = raiz.dir.elemento; raiz.dir.elemento = elemento; System.out.println("Antes, dois elementos(C). Agora, raiz(" + raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento + ")."); } raiz.esq.cor = raiz.dir.cor = false; } else if (raiz.dir == null) { if (elemento > raiz.elemento) { raiz.dir = new NoAN(elemento); System.out.println("Antes, dois elementos(D). Agora, raiz(" + raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento + ")."); } else if (elemento > raiz.esq.elemento) { raiz.dir = new NoAN(raiz.elemento); raiz.elemento = elemento; System.out.println("Antes, dois elementos(E). Agora, raiz(" + raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento + ")."); } else { raiz.dir = new NoAN(raiz.elemento); raiz.elemento = raiz.esq.elemento; raiz.esq.elemento = elemento; System.out.println("Antes, dois elementos(F). Agora, raiz(" + raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento + ")."); } raiz.esq.cor = raiz.dir.cor = false; } else { System.out.println("Arvore com tres ou mais elementos..."); inserir(elemento, null, null, null, raiz); } raiz.cor = false; } private void balancear(NoAN bisavo, NoAN avo, NoAN pai, NoAN i) { if (pai.cor == true) { if (pai.elemento > avo.elemento) { if (i.elemento > pai.elemento) { avo = rotacaoEsq(avo); } else { avo = rotacaoDirEsq(avo); } } else { if (i.elemento < pai.elemento) { avo = rotacaoDir(avo); } else { avo = rotacaoEsqDir(avo); } } if (bisavo == null) { raiz = avo; } else if (avo.elemento < bisavo.elemento) { public class AVL { private No raiz; public AVL() { raiz = null; } public boolean pesquisar(int x) { return pesquisar(x, raiz); } private boolean pesquisar(int x, No i) { boolean resp; if (i == null) { resp = false; } else if (x == i.elemento) { resp = true; } else if (x < i.elemento) { resp = pesquisar(x, i.esq); } else { resp = pesquisar(x, i.dir); } return resp; } public void caminharCentral() { System.out.print("[ "); caminharCentral(raiz); System.out.println("]"); } private void caminharCentral(No i) { if (i != null) { caminharCentral(i.esq); System.out.print(i.elemento + " "); caminharCentral(i.dir); } } public void caminharPre() { System.out.print("[ "); caminharPre(raiz); System.out.println("]"); } private void caminharPre(No i) { if (i != null) { System.out.print(i.elemento + "(fator " + (No.getNivel(i.dir) - No.getNivel(i.esq)) + ") "); // Conteudo do no. caminharPre(i.esq); caminharPre(i.dir); } } public void caminharPos() { System.out.print("[ "); caminharPos(raiz); System.out.println("]"); } private void caminharPos(No i) { if (i != null) { caminharPos(i.esq); caminharPos(i.dir); System.out.print(i.elemento + " "); } } public void inserir(int x) throws Exception { raiz = inserir(x, raiz); } private No inserir(int x, No i) throws Exception { if (i == null) { i = new No(x); } else if (x < i.elemento) { i.esq = inserir(x, i.esq); } else if (x > i.elemento) { i.dir = inserir(x, i.dir); } else { throw new Exception("Erro ao inserir!"); } return balancear(i); } public void remover(int x) throws Exception { raiz = remover(x, raiz); } private No remover(int x, No i) throws Exception { if (i == null) { throw new Exception("Erro ao remover!"); } else if (x < i.elemento) { i.esq = remover(x, i.esq); } else if (x > i.elemento) { i.dir = remover(x, i.dir); } else if (i.dir == null) { i = i.esq; } else if (i.esq == null) { i = i.dir; } else { i.esq = maiorEsq(i, i.esq); } return balancear(i); } private No maiorEsq(No i, No j) { if (j.dir == null) { i.elemento = j.elemento; j = j.esq; } else { j.dir = maiorEsq(i, j.dir); } return j; } private No balancear(No no) throws Exception { if (no != null) { int fator = No.getNivel(no.dir) - No.getNivel(no.esq); if (Math.abs(fator) <= 1) { no.setNivel(); } else if (fator == 2) { int fatorFilhoDir = No.getNivel(no.dir.dir) - No.getNivel(no.dir.esq); if (fatorFilhoDir == -1) { no.dir = rotacionarDir(no.dir); } no = rotacionarEsq(no); } else if (fator == -2) { int fatorFilhoEsq = No.getNivel(no.esq.dir) - No.getNivel(no.esq.esq); if (fatorFilhoEsq == 1) { no.esq = rotacionarEsq(no.esq); } no = rotacionarDir(no); } else { throw new Exception( "Erro no No(" + no.elemento + ") com fator de balanceamento (" + fator + ") invalido!"); } } return no; } private No rotacionarDir(No no) { System.out.println("Rotacionar DIR(" + no.elemento + ")"); No noEsq = no.esq; No noEsqDir = noEsq.dir; noEsq.dir = no; no.esq = noEsqDir; no.setNivel(); noEsq.setNivel(); return noEsq; } private No rotacionarEsq(No no) { System.out.println("Rotacionar ESQ(" + no.elemento + ")"); No noDir = no.dir; No noDirEsq = noDir.esq; noDir.esq = no; no.dir = noDirEsq; no.setNivel(); noDir.setNivel(); return noDir; } } if(no.prox[s.charAt(i)] == null){ resp = false; } else if(i == s.length() - 1){ resp = (no.prox[s.charAt(i)].folha == true); } else if(i < s.length() - 1 ){ resp = pesquisar(s, no.prox[s.charAt(i)], i + 1); } else { throw new Exception("Erro ao pesquisar!"); } return resp; } public void inserir(String s) throws Exception { inserir(s, raiz, 0); } private void inserir(String s, No no, int i) throws Exception { System.out.print("\nEM NO(" + no.elemento + ") (" + i + ")"); if(no.prox[s.charAt(i)] == null){ System.out.print("--> criando filho(" + s.charAt(i) + ")"); no.prox[s.charAt(i)] = new No(s.charAt(i)); if(i == s.length() - 1){ System.out.print("(folha)"); no.prox[s.charAt(i)].folha = true; }else{ inserir(s, no.prox[s.charAt(i)], i + 1); } } else if (no.prox[s.charAt(i)].folha == false && i < s.length() - 1){ inserir(s, no.prox[s.charAt(i)], i + 1); } else { throw new Exception("Erro ao inserir!"); } } public void mostrar(){ mostrar("", raiz); } public void mostrar(String s, No no) { if(no.folha == true){ System.out.println("Palavra: " + (s + no.elemento)); } else { for(int i = 0; i < no.prox.length; i++){ if(no.prox[i] != null){ System.out.println("ESTOU EM (" + no.elemento + ") E VOU PARA (" + no.prox[i].elemento + ")"); mostrar(s + no.elemento, no.prox[i]); } } } } public int contarAs(){ int resp = 0; if(raiz != null){ resp = contarAs(raiz); } return resp; } public int contarAs(No no) { int resp = (no.elemento == 'A') ? 1 : 0; if(no.folha == false){ for(int i = 0; i < no.prox.length; i++){ if(no.prox[i] != null){ resp += contarAs(no.prox[i]); } } } return resp; } } —---------------------------------------------------------------------------------------------------- public class Hash { int tabela[]; int m1, m2, m, reserva; final int NULO = -1; public Hash() { this(13, 7); } public Hash(int m1, int m2) { this.m1 = m1; this.m2 = m2; this.m = m1 + m2; this.tabela = new int[this.m]; for (int i = 0; i < m1; i++) { tabela[i] = NULO; } reserva = 0; } public int h(int elemento) { return elemento % m1; } public boolean inserir(int elemento) { boolean resp = false; if (elemento != NULO) { int pos = h(elemento); if (tabela[pos] == NULO) { tabela[pos] = elemento; resp = true; } else if (reserva < m2) { tabela[m1 + reserva] = elemento; reserva++; resp = true; } } return resp; } public boolean pesquisar(int elemento) { boolean resp = false; int pos = h(elemento); if (tabela[pos] == elemento) { resp = true; } else if (tabela[pos] !=NULO) { for (int i = 0; i < reserva; i++) { if (tabela[m1 + i] == elemento) { resp = true; i = reserva; } } } return resp; } boolean remover(int elemento) { boolean resp = false; return resp; } } } else { int alturaEsq = getAltura(i.esq, altura + 1); int alturaDir = getAltura(i.dir, altura + 1); altura = (alturaEsq > alturaDir) ? alturaEsq : alturaDir; } return altura; } public void remover2(int x) throws Exception { if (raiz == null) { throw new Exception("Erro ao remover2!"); } else if(x < raiz.elemento){ remover2(x, raiz.esq, raiz); } else if (x > raiz.elemento){ remover2(x, raiz.dir, raiz); } else if (raiz.dir == null) { raiz = raiz.esq; } else if (raiz.esq == null) { raiz = raiz.dir; } else { raiz.esq = maiorEsq(raiz, raiz.esq); } } private void remover2(int x, No i, No pai) throws Exception { if (i == null) { throw new Exception("Erro ao remover2!"); } else if (x < i.elemento) { remover2(x, i.esq, i); } else if (x > i.elemento) { remover2(x, i.dir, i); } else if (i.dir == null) { pai = i.esq; } else if (i.esq == null) { pai = i.dir; } else { i.esq = maiorEsq(i, i.esq); } } public int getRaiz() throws Exception { return raiz.elemento; } public static boolean igual (ArvoreBinaria a1, ArvoreBinaria a2){ return igual(a1.raiz, a2.raiz); } private static boolean igual (No i1, No i2){ boolean resp; if(i1 != null && i2 != null){ resp = (i1.elemento == i2.elemento) && igual(i1.esq, i2.esq) && igual(i1.dir, i2.dir); } else if(i1 == null && i2 == null){ resp = true; } else { resp = false; } return resp; } public int soma(){ return soma(raiz); } public int soma(No i){ int resp = 0; if(i != null){ resp = i.elemento + soma(i.esq) + soma(i.dir); } return resp; } public int quantidadePares(){ return quantidadePares(raiz); } public int quantidadePares(No i){ int resp = 0; if(i != null){ resp = ((i.elemento % 2 == 0) ? 1 : 0) + quantidadePares(i.esq) + quantidadePares(i.dir); } return resp; } public boolean hasDiv11(){ return hasDiv11(raiz); } public boolean hasDiv11(No i){ boolean resp = false; if(i != null){ resp = (i.elemento % 11 == 0) || hasDiv11(i.esq) || hasDiv11(i.dir); } return resp; } } —---------------------------------------------------------------------------------------------------- public class HashIndiretoLista { Lista tabela[]; int tamanho; final int NULO = -1; public HashIndiretoLista() { this(7); } public HashIndiretoLista(int tamanho) { this.tamanho = tamanho; tabela = new Lista[tamanho]; for (int i = 0; i < tamanho; i++) { tabela[i] = new Lista(); } } public int h(int elemento) { return elemento % tamanho; } boolean pesquisar(int elemento) { int pos = h(elemento); return tabela[pos].pesquisar(elemento); } public void inserirInicio(int elemento) { int pos = h(elemento); tabela[pos].inserirInicio(elemento); } public int remover(int elemento) { int resp = NULO; if (pesquisar(elemento) == false) { throw new Exception("Erro ao remover!"); } else { int pos = h(elemento); resp = tabela[pos].remover(elemento); } return resp; } } bisavo.esq = avo; } else { bisavo.dir = avo; } avo.cor = false; avo.esq.cor = avo.dir.cor = true; System.out.println("Reestabeler cores: avo(" + avo.elemento + "->branco) e avo.esq / avo.dir(" + avo.esq.elemento + "," + avo.dir.elemento + "-> pretos)"); } } private void inserir(int elemento, NoAN bisavo, NoAN avo, NoAN pai, NoAN i) throws Exception { if (i == null) { if (elemento < pai.elemento) { i = pai.esq = new NoAN(elemento, true); } else { i = pai.dir = new NoAN(elemento, true); } if (pai.cor == true) { balancear(bisavo, avo, pai, i); } } else { if (i.esq != null && i.dir != null && i.esq.cor == true && i.dir.cor == true) { i.cor = true; i.esq.cor = i.dir.cor = false; if (i == raiz) { i.cor = false; } else if (pai.cor == true) { balancear(bisavo, avo, pai, i); } } if (elemento < i.elemento) { inserir(elemento, avo, pai, i, i.esq); } else if (elemento > i.elemento) { inserir(elemento, avo, pai, i, i.dir); } else { throw new Exception("Erro inserir (elemento repetido)!"); } } } private NoAN rotacaoDir(NoAN no) { System.out.println("Rotacao DIR(" + no.elemento + ")"); NoAN noEsq = no.esq; NoAN noEsqDir = noEsq.dir; noEsq.dir = no; no.esq = noEsqDir; return noEsq; } private NoAN rotacaoEsq(NoAN no) { System.out.println("Rotacao ESQ(" + no.elemento + ")"); NoAN noDir = no.dir; NoAN noDirEsq = noDir.esq; noDir.esq = no; no.dir = noDirEsq; return noDir; } private NoAN rotacaoDirEsq(NoAN no) { no.dir = rotacaoDir(no.dir); return rotacaoEsq(no); } private NoAN rotacaoEsqDir(NoAN no) { no.esq = rotacaoEsq(no.esq); return rotacaoDir(no); } } —---------------------------------------------------------------------------------------------------- public class HashRehash { int tabela[]; int m; final int NULO = -1; public Hash() { this(13); } public Hash(int m) { this.m = m; this.tabela = new int[this.m]; for (int i = 0; i < m; i++) { tabela[i] = NULO; } } public int h(int elemento) { return elemento % m; } public int reh(int elemento) { return ++elemento % m; } public boolean inserir(int elemento) { boolean resp = false; if (elemento != NULO) { int pos = h(elemento); if (tabela[pos] == NULO) { tabela[pos] = elemento; resp = true; } else { pos = reh(elemento); if (tabela[pos] == NULO) { tabela[pos] = elemento; resp = true; } } } return resp; } public boolean pesquisar(int elemento) { boolean resp = false; int pos = h(elemento); if (tabela[pos] == elemento) { resp = true; } else if (tabela[pos] != NULO) { pos = reh(elemento); if (tabela[pos] == elemento) { resp = true; } } return resp; } boolean remover(int elemento) { boolean resp = false; return resp; } } —---------------------------------------------------------------------------------------------------- class Patricia { No raiz; String[] array; public Patricia(){ raiz = new No(); array = null; } public void setArray(String[] array) throws Exception { this.array = array; for(int i = 0; i < array.length; i++){ inserir(i); } } private String string(No no){ return (no == raiz) ? " " : string(no.i, no.j, no.k); } private String string(int i, int j, int k){ return array[i].substring(j,k+1); } public void inserir(int i) throws Exception { System.out.print("\n=========================================== ========= INSERINDO : " + array[i]); inserir(raiz, i, 0); mostrar(); } private void inserir(No no, int i, int j) throws Exception { System.out.println("\nEM NO(" + string(no) + ") i("+ i +") j(" + j + ")"); if(no.prox[array[i].charAt(j)] == null){ no.prox[array[i].charAt(j)] = new No(i, j, array[i].length()-1, true); System.out.print("--> criando folha(" + array[i].charAt(j) + "/" + string(no.prox[array[i].charAt(j)]) + ")"); } else { String prox = string(no.prox[array[i].charAt(j)]); String inserindo = array[i].substring(j); System.out.println("prox(" + prox + ") e inserindo(" + inserindo + ")"); int k; for(k = 1; k < prox.length() && k < inserindo.length() && prox.charAt(k) == inserindo.charAt(k); k++); System.out.println("k (" + k + ")"); if(k == prox.length()){ if(no.prox[array[i].charAt(j)].folha == true){ throw new Exception("Erro: exite um prefixo de [" + array[i] + "] na arvore"); } else { inserir(no.prox[array[i].charAt(j)], i, j + k); } } else if (k == inserindo.length()){ throw new Exception("Erro: [" + array[i] + "] é prefixo de outra palavra da árvore"); } else { No novo = new No(i, j, j + k - 1, false); novo.prox[prox.charAt(k)] = no.prox[array[i].charAt(j)]; novo.prox[prox.charAt(k)].j = j + k; novo.prox[inserindo.charAt(k)] = new No(i, j + k, array[i].length()-1, true); no.prox[array[i].charAt(j)] = novo; System.out.println("no(" + string(no) + ") e filhoNOVO(" + string(novo) + ") neto1(" + string(novo.prox[inserindo.charAt(k)]) + ") neto2(" + string(novo.prox[prox.charAt(k)]) + ")"); } } } public boolean pesquisar(String s){ System.out.println("\n========================================== ========== PESQUISAR: " + s); return pesquisar (raiz, s, 0); } public boolean pesquisar (No no, String s, int cont){ boolean resp; System.out.println("EM NO(" +string(no) + ") s("+ s +") cont(" + cont + ") prox(" + no.prox[s.charAt(cont)] + ")"); if(no.prox[s.charAt(cont)] == null){ System.out.println("não existe filho para [" + s.charAt(cont) + "]"); resp = false; } else { String prox = string(no.prox[s.charAt(cont)]); System.out.println("prox: " + prox); int i1, i2; for(i1 = 0, i2 = cont; i1 < prox.length() && i2 < s.length() && prox.charAt(i1) == s.charAt(i2); i1++, i2++); if(i2 == s.length()){ System.out.println("resp = consumiuTodosOsCaracteresDeProx(" + (i1 == prox.length()) + ") and proxFolha(" + (no.prox[s.charAt(cont)].folha) + ")"); resp = i1 == prox.length() && no.prox[s.charAt(cont)].folha; } else { resp = pesquisar(no.prox[s.charAt(cont)], s, i2); } } return resp; } public void mostrar(){ System.out.println("\n========================================== ========== MOSTRAR: "); mostrar("", raiz); } public void mostrar(String s, No no) { if(no.folha == true){ System.out.println("Palavra: " + (s + string(no))); } else { for(int i = 0; i < no.prox.length; i++){ if(no.prox[i] != null){ System.out.println("ESTOU EM (" + string(no) + ") E VOU PARA (" + string(no.prox[i]) + ")"); mostrar(s + string(no), no.prox[i]); } } } } public int contarAs(){ int resp = 0; if(raiz != null){ resp = contarAs(raiz); } return resp; } public int contarAs(No no) { int resp = 0; String palavra = string(no); for(int i = 0; i < palavra.length(); i++){ if(palavra.charat(i) == 'A'){ resp++; } } if(no.folha == false){ for(int i = 0; i < no.prox.length; i++){ if(no.prox[i] != null){ resp += contarAs(no.prox[i]); } } } return resp; } }
Compartilhar