Escreva um programa em Java que leia uma seqüência de pares (chave: int, elemento: string) fornecidos pelo usuário e monte uma árvore de pesquisa genérica atendendo às regras da estrutura.
O programa deve permitir:
* Inserção, remoção e busca de elementos informados pelo usuário;
* Exibir a árvore na tela, de modo que a estrutura possa ser visualizada, ou seja, de maneira que possamos conferir a estrutura da árvore.
Estou colocando a resoluções que consegui fazer, não digo que esteja certo, mais pelos teste que fiz os erros encontrados foram solucionados.
Para ilustrar segue a arvoré resultante do exemplo:
([10, 22])
([3, 8, 9][11, 15, 16][])
([][4, 5, 7][][])([][12, 14][][17])
([][][][])([][13][])([][])
([][])
App
package ArvoreGenerica;
import java.util.ArrayList;
public class app {
public static void main (String arg[]){
ArrayList imp;
String r;
Arvore arv = new Arvore();
arv.novoFilho(22, "el:22");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(10, "el:10");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(15, "el:15");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(16, "el:16");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(9, "el:9");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(8, "el:8");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(3, "el:3");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(5, "el:5");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(7, "el:7");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(11, "el:11");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(4, "el:4");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(12, "el:12");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(14, "el:14");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(13, "el:13");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
arv.novoFilho(17, "el:17");
imp = arv.ImpAravore();
for (int i=0;i
System.out.println("-------------");
r = arv.getElemento(9);
System.out.println(r);
r =arv.removeKey(10);
r =arv.removeKey(9);
r =arv.removeKey(3);
r =arv.removeKey(7);
r =arv.removeKey(4);
System.out.println("removido "+r);
imp = arv.ImpAravoreElemento();
for (int i=0;i
System.out.println("-------------");
}
}
Arvore
package ArvoreGenerica;
import java.util.ArrayList;
public class Arvore {
//Nó raiz
private Nodo root;
//quantidade de nos
private int size;
//para armazenar os elementos quando usado os metodos de percorrer
private ArrayList
//Altura é o nivel do nodo mais externo + 1
public int altura;
//Construtor sem Nó raiz
public Arvore(){
root = null;
size = 0;
lista = new ArrayList();
}
//Construtor passando o Nó raiz
public Arvore(int k, String x){
root = new Nodo(k,x,null);
size = 0;
lista = new ArrayList();
}
public Nodo getRoot() {
return root;
}
public void setRoot(int k, String x){
root = new Nodo(k,x,null);
}
public void setSize(int size) {
this.size = size;
}
public int Size() {
return size;
}
//Se possui algum filho o Nó é interno
public boolean isInternal(Nodo n){
if (n.possuiFilho())
return true;
return false;
}
//Se não possuir filho é Nó externo (folha)
public boolean isExternal(Nodo n){
if (n.possuiFilho()==false)
return true;
return false;
}
public boolean isRoot(Nodo n){
if (n.getPai()==null)
return true;
return false;
}
public boolean isEmpty(){
if (getRoot()==null)
return true;
return false;
}
/**
* Partindo da raiz irá verificar o valor do nó para adicionar o novo nó
* @param n
* @param v
*/
private void addOrder(Nodo n, int k, String x){
if (n.possuiFilho()==false)
n.setElemento(k, x, n);
else{
//informa a chave e recebe qual o filho
Filho f = n.getFilho(k);
//Se o filho for nulo insere este nete filho o novo nodo
//se o filho não nulo chama novamente o metodo addOrder
if (f.getElemento()==null){
Nodo novo = new Nodo(k,x,n);
f.setElemento(novo);
altura = novo.getNivel()+1;
}
else{
Nodo novo = (Nodo)f.getElemento();
addOrder(novo,k,x);
}
}
}
public void novoFilho(int k, String x){
if (isEmpty()==false){
addOrder(root,k,x);
}
else
setRoot(k,x);
this.size++;
}
public int getAltura(){
return altura;
}
private ArrayList ImpFilho(Nodo n, int lin, ArrayList imp){
lin++;
ListaFilho lF = n.getlFilhos();
Filho f = lF.getHead();
if (imp.size()==lin){
imp.add("");
}
imp.set(lin,imp.get(lin)+"(");
while (f!=lF.getTail()){
if (f.getElemento()==null){
imp.set(lin, imp.get(lin)+"[]");
}
else{
imp.set(lin,imp.get(lin)+""+((Nodo)f.getElemento()).getChave());
imp = ImpFilho((Nodo)f.getElemento(),lin,imp);
}
f=f.getProximo();
}
if (f.getElemento()==null){
imp.set(lin, imp.get(lin)+"[]");
}
else{
imp.set(lin,imp.get(lin)+""+((Nodo)f.getElemento()).getChave());
imp = ImpFilho((Nodo)f.getElemento(),lin,imp);
}
imp.set(lin,imp.get(lin)+")");
return imp;
}
public ArrayList ImpAravore(){
ArrayList imp = new ArrayList();
Nodo n = getRoot();
if (n!=null){
int lin=0;
imp.add("("+n.getChave()+")");
imp = ImpFilho(n,lin,imp);
}else
imp.add("[Vasio]");
return imp;
}
private ArrayList ImpFilhoElemento(Nodo n, int lin, ArrayList imp){
lin++;
ListaFilho lF = n.getlFilhos();
Filho f = lF.getHead();
if (imp.size()==lin){
imp.add("");
}
imp.set(lin,imp.get(lin)+"(");
while (f!=lF.getTail()){
if (f.getElemento()==null){
imp.set(lin, imp.get(lin)+"[]");
}
else{
imp.set(lin,imp.get(lin)+""+((Nodo)f.getElemento()).getElemento());
imp = ImpFilhoElemento((Nodo)f.getElemento(),lin,imp);
}
f=f.getProximo();
}
if (f.getElemento()==null){
imp.set(lin, imp.get(lin)+"[]");
}
else{
imp.set(lin,imp.get(lin)+""+((Nodo)f.getElemento()).getElemento());
imp = ImpFilhoElemento((Nodo)f.getElemento(),lin,imp);
}
imp.set(lin,imp.get(lin)+")");
return imp;
}
public ArrayList ImpAravoreElemento(){
ArrayList imp = new ArrayList();
Nodo n = getRoot();
if (n!=null){
int lin=0;
imp.add("("+n.getElemento()+")");
imp = ImpFilhoElemento(n,lin,imp);
}else
imp.add("[Vasio]");
return imp;
}
private String findElemento(int k, Nodo n, int cc){
Filho f = n.getFilho(k);
if (f.getElemento()!=null){
n = (Nodo)f.getElemento();
for(int i=0;i
Nodo
package ArvoreGenerica;
import java.util.ArrayList;
public class Nodo {
private ArrayList
private ArrayList elemento;
private Nodo pai;
private ListaFilho lFilhos;
private int nivel;
public Nodo(int k, String x, Nodo Pai){
chave = new ArrayList
chave.add(k);
elemento = new ArrayList();
elemento.add(x);
this.pai = Pai;
lFilhos = new ListaFilho();
lFilhos.insertFist(null);
lFilhos.insertFist(null);
if (Pai!=null)
nivel = Pai.getNivel()+1;
}
public boolean chaveMenor(int k){
if (chave.get(0)>k)
return true;
return false;
}
public boolean chaveMaior(int k){
if (chave.get(chave.size()-1)
this.chave.add(null);
this.elemento.add(null);
for(int i=this.chave.size()-1;i>0;i--){
this.chave.set(i,this.chave.get(i-1));
this.elemento.set(i, this.elemento.get(i-1));
}
this.chave.set(0,k);
this.elemento.set(0, x);
lFilhos.insertFist(null);
}
else
if (chave.get(chave.size()-1)
pos++;
}
Filho f = lFilhos.getHead();
for (int i=0;i
return chave;
}
public ListaFilho getlFilhos(){
return lFilhos;
}
}
ListaFilho
package ArvoreGenerica;
public class ListaFilho {
private Filho Head;
private Filho Tail;
private int Size;
public ListaFilho(){
Head = null;
Tail = null;
Size = 0;
}
public void insertFist(Object elemento){
Filho novo = new Filho(elemento);
novo.setProximo(Head);
Head = novo;
Size++;
if (Tail==null)
Tail=novo;
}
public void insertLast(Object elemento){
Filho novo = new Filho(elemento);
if (Tail!=null){
Tail.setProximo(novo);
Tail = novo;
Size++;
}
else
{
insertFist(elemento);
Tail=Head;
}
}
public Object removeFirst(){
Filho nodo = Head;
Head = nodo.getProximo();
Size--;
return nodo;
}
public Object removeLast(){
Filho nodo = Head;
while (nodo.getProximo()!=null){
Tail = nodo;
nodo = nodo.getProximo();
}
Tail.setProximo(null);
Size--;
return nodo;
}
public Object [] RetornaLista(){
Object [] lista = new Object[Size];
Filho nodo = Head;
int i=0;
while(nodo!=null){
lista[i]=nodo.getElemento();
i++;
nodo = nodo.getProximo();
}
return lista;
}
public Filho getHead(){
return this.Head;
}
public Filho getTail(){
return this.Tail;
}
public int getSize(){
return Size;
}
}
Filho
package ArvoreGenerica;
public class Filho {
private Object Elemento;
private Filho Proximo;
public Filho(Object elemento){
Elemento = elemento;
Proximo = null;
}
public Object getElemento(){
return Elemento;
}
public void setElemento(Object elemento){
Elemento = elemento;
}
public Filho getProximo(){
return Proximo;
}
public void setProximo(Filho proximo){
Proximo = proximo;
}
}
