Arvore binaria (Pré ordem

import java.util.ArrayList;

[code]
public class ArvoreGenerica {

private Node raiz;

public ArvoreGenerica(){
raiz=null;
}
public Node raiz(){
return raiz;

}

public ArrayList filhos(Node n){
return n.getFilhos();
}

public boolean verificaInterno(Node n){
int numeroFilhos = n.getFilhos().size();
if(numeroFilhos==0)
return false;

return true;
}

public boolean verificaExterno(Node n){
return !verificaInterno(n);
}

public boolean verificaRaiz(Node n){
if (n==raiz)
return true;

return false;

}

public ArrayList elementos(){
ArrayList vetor = new ArrayList();

vetor.add(raiz);

int i = 0;

//Navega pelo vetor adicionando os filhos. - Em Profundidade
while(i < vetor.size()){
Node atual = vetor.get(i);
for(Node n: atual.getFilhos()){
vetor.add(n);
}
i++;
}
return vetor;

}
public int tamanho(){
return elementos().size();
}
public int atualizaElemento(Node antigo, Node novo){
int aux = antigo.getValor();
antigo.setValor(novo.getValor());

return aux;
}
public void insere(Node pai, Node filho){
if(raiz == null)
raiz = filho;
else {
filho.setPai(pai);
pai.getFilhos().add(filho);
}
}
//Emplementar
public ArrayListpreOrdem(Node filho){

}
}

[code]import java.util.ArrayList;

public class Node {

private int valor;
private Node pai;
private ArrayList filhos;

public Node(){
valor = 0;
pai = null;
filhos = new ArrayList();
}

public Node(int v){
valor = v;
pai = null;
filhos = new ArrayList();

}

public int getValor() {
return valor;
}

public void setValor(int valor) {
this.valor = valor;
}

public Node getPai() {
return pai;
}

public void setPai(Node pai) {
this.pai = pai;
}

public ArrayList getFilhos() {
return filhos;
}

public void setFilhos(ArrayList filhos) {
this.filhos = filhos;
}

}

Estou com difciculdade de fazer o método pré ordem, preciso de ajudaa!!!
obrigadoo

1 Resposta

davidtiagoconceicao 16 de abr. de 2009

Ok, e qual sua dúvida? Tentou implementar algo? Por favor, seja mais específico.

Estava observando o seu código e fiquei com uma dúvida: esta deve ser uma árvore binária ou n-ária? Pela sua descrição deve ser binária, mas pela implementação ela será n-ária, já que você utiliza um List para guardar os filhos. Se a idéia é torná-la binária, utilze dois atributos para guardar os nós à esquera e à direita ou um vetor de duas posições. Na minha opinião isto é mais vantajoso do que um List.

Sobre a implementação do método de impressão, segue o código que fiz para implementação de pré-ordem em uma árvore binária e depois em uma árvore n-ária:

// Para árvore binária
	private String imprimePre(NoArvoreBinaria no) {

		if (no != null) {
			// Se não for nulo, efetua as operações.
			StringBuilder s = new StringBuilder("");
			s.append("<");
			s.append(no.getInfo());
			s.append(imprimePre(no.getEsq()));  // Note a recursão
			s.append(imprimePre(no.getDir()));
			s.append(">");
			return s.toString();
		}
		// Se for nulo, retorna como folha.
		return "<>";

	}

//Para árvore n-ária

	private String imprime(NoArvore no) {
		StringBuilder retorno = new StringBuilder();
		retorno.append("<");
		retorno.append(no.getInfo());
		for (NoArvore atual = no.getPrim(); atual != null; atual = atual.getProx()) {
			retorno.append(imprime(atual));
		}
		retorno.append(">");
		return retorno.toString();
	}

Para transformar em pós ordem ou ordem simétrica, basta alterar os apends de info e "<" de ordem.

PS.: Utilize as tags de código em seus próximos posts.

1 Resposta

Topicos relacionados