Usar Árvores

[jncevcosta]

Boas minha gente.

Estou aqui com um problema e não encontro nada que me ajude a resolver este problema.

Tenho um enunciado que diz que tenho que imprimir a profundidade de uma certa árvore.

O input da árvore é dada na forma de pré-order.

O Problema é este:

http://www.dcc.fc.up.pt/~fds/aulas/EDados/1011/Praticas/problemas/prob11.html

Já tenho a função para calcular a profundidade e métodos construtores. Não estou a conseguir perceber é como é que eu construo a árvore 😞

cumprimentos

[HappyHippyHippo]

Já tenho a função para calcular a profundidade e métodos construtores. Não estou a conseguir perceber é como é que eu construo a árvore 😞

?? afinal não percebes o que é uma árvore ou como se lê a linha ??

[jncevcosta]

?? afinal não percebes o que é uma árvore ou como se lê a linha ??

Eu já resolvi alguns exercícios de árvores binárias sem qualquer problema. Mas essa árvore não é binária e não estou a perceber como é que eu faço o método para criar uma árvore.

Por exemplo para resolver um exercicio usando árvores binárias usei o seguinte código:

/**
*
* @author José Nuno Costa
* @num 090316010
*/
import java.util.*;
//Classe que define o Nó
class BTNode{
int val;
BTNode dir;
BTNode esq;
BTNode(int v, BTNode d, BTNode e){
	val = v;
	dir = d;
	esq = e;
}
}
//Classe que define a árvore binária
class BTree{
BTNode root;
BTree(){
	root = null;
}
//Método para inserir um inteiro na árvore
public void insertNode(int k){
	root = insertBTNode(root, k);
}
private BTNode insertBTNode(BTNode t, int k){
	if(t==null)
		return new BTNode(k,null, null);
	else{
		if(k<=t.val)
			t.esq=insertBTNode(t.esq, k);
		else
			t.dir=insertBTNode(t.dir,k);
	}
	return t;
}
//Procura determinado valor na arvore
String  procuravalor(int v){
	if(root.val==v)
		return "R";
	return caminho (root, v);
}
//Devolve o caminho ate ao valor pretendido
//Caso nao encontre o caracter final sera igual a X
String caminho(BTNode t, int v){
	if(t==null)
		return "X";
	if(t.val==v)
		return "";
	if(v<t.val)
		return "E"+caminho(t.esq, v);
	else
		return "D"+caminho(t.dir, v);
}
}
public class ArvBin {
public static void main(String[] args){
	Scanner leitura = new Scanner(System.in);
	int ncasos = leitura.nextInt();
	for(int i = 0; i<ncasos; i++){
		int insere = leitura.nextInt();
		BTree t = new BTree();
		for(int j = 0; j<insere; j++){
			t.insertNode(leitura.nextInt());
		}
		int procurados = leitura.nextInt();
		System.out.println("#Output da Arvore "+(i+1));
		for(int j = 0; j<procurados; j++){
			int val = leitura.nextInt();
			String resultado = t.procuravalor(val);
			if(resultado.charAt((resultado.length())-1)=='X')
				System.out.println("No "+val+" = Nao Encontrado");
			else
				System.out.println("No "+val+" = "+resultado);
		}
	}
}
}

Mas esta árvore pelo menos o input é diferente e não estou a conseguir sair do sítio.

Para já tenho o seguinte código:

/**
*
* @author Jose Nuno Costa
* @num 090316010
*/
import java.util.*;
import java.lang.Math;
class BTNode{
int val;
BTNode dir;
BTNode esq;

BTNode(int v, BTNode d, BTNode e){
	val = v;
	dir = d;
	esq = e;
}
}
class Tree{
BTNode root;
Tree(){
	root = null;
}
public void cria(String a){
//metodo para criar a árvore					
}
public int prof(BTNode t){
	if(t==null)
		return -1;
	else
		return 1 + Math.max(prof(t.esq), prof(t.dir));
}
}
public class Profundidade {
public static void main(String[] args){
	Scanner leitura = new Scanner (System.in);
	int ncasos = leitura.nextInt();
	for (int i = 0; i<ncasos; i++){
		int p;
		Tree t = new Tree();
		boolean dir = true;
		boolean esq = false;
		while(leitura.hasNextLine()){
			t.cria(leitura.nextLine());
			p=t.prof(t.root);
		}
		System.out.println(p);
	}
}
}

Edited May 20, 2012 at 03:37 PM by Baderous
geshi

[HappyHippyHippo]

nao ... isto é uma árvore binária ...

[jncevcosta]

nao ... isto é uma árvore binária ...

É?

Mas se fosse uma árvore binária os valores maiores não deviam estar à esquerda? =/

Edited May 19, 2012 at 10:22 PM by jncevcosta

[HappyHippyHippo]

o enunciado não indica nada sobre a ordenação de valores ... somente que são árvores binárias e como se deve ler o ficheiro/linhas

[jncevcosta]

o enunciado não indica nada sobre a ordenação de valores ... somente que são árvores binárias e como se deve ler o ficheiro/linhas

Tens razão 🙂

Agora o problema é como é que eu faço a leitura dos dados para construir a árvore? Como é que tem que ser o método? :s Isso é o que eu não estou a conseguir perceber =/

[HappyHippyHippo]

Nota : este código implica teres uma flag em cada nó ou usares uma stack para as flags

Pseudo-código:

- se o primeiro valor for um V então a árvore está vazia

- caso contrário, guardas o valor na raiz

- no actual = raiz

- flag para ler para a parte esquerda do nó actual

// ciclo de leitura

- se o valor lido for um V então

- se a flag é para ler para a esquerda então

- flag para ler à direita do nó actual

- caso contrário

// ciclo interno

- se no actual é o no raiz

- fim

- caso contrario

- no actual = no pai

- se flag for para ler à esquerda

- flag para ler à direita

- fim de ciclo

- caso contrário

caso contrário

- criar nó no ramo dependente da flag

- guardar o valor no nó criado

- marcar a flag para ler à esquerda