Exercícios de estruturas de dados

[pablomarcolino]

Questão 1

Construa a árvore balanceada AVL de inteiros para a sequência: 2, 1, 0, 3, 4, 9, 5, 6, 8, 10, 7.

Obs. Não é necessário enviar a árvore construída.

Considerando a seguinte estrutura de nós para a árvore AVL construída:

typedef struct s_cel{
 int val,alt;
 struct s_cel *esq,*dir;
} cel;

Mostre o resultado da execução da seguinte rotina caso seja passado como parâmetro a raiz da árvore construída:

int calcula(cel *esse) {
int total;
if(esse == NULL)
		return 0;
total = esse->val;
total += calcula(esse->dir);
  total += calcula(esse->esq);  
  printf(“Subarvore em %d = %d“,esse->val,total);
return total;
}

Questão 2 (1,0 ponto)

Escreva uma rotina que receba a raiz de uma árvore cujos nós têm a estrutura definida na questão 1 e que calcule a altura de cada nó registrando o resultado no campo alt da estrutura.

-------------------------------------------------------------------------------------------------------------------

As questões 3 e 4 se referem ao seguinte problema: deseja-se implementar uma árvore binária de busca para armazenar um conjunto de livros. Os livros são definidos pelo ano da publicação, título, nome do primeiro autor e número de páginas. A árvore binária vai organizar os livros por ano. Cada nó da árvore corresponde a um ano e contém uma lista encadeada com os livros publicados naquele ano. Considere que a árvore esta ordenada por ano. As estruturas de dados da árvore são as seguintes:

typedef struct s_cel{
int ano;
livro *inicio;
struct s_cel *esq,*dir;
} cel;
typedef struct s_livro {
char titulo[100],autor[100];
int pags;
struct s_livro *prox;
} livro;

Questão 3 (3,0 pontos)

Escreva uma rotina recursiva que receba um ano e a raiz da árvore e mostre os dados de todos os livros publicados naquele ano. A busca deve ser otimizada considerando que a árvore está ordenada.

Questão 4 (3,0 pontos)

Escreva uma rotina recursiva que receba a raiz da árvore e que retorne o ano para o qual existem mais livros e quantos livros são.

[lusitan]

Então mas nem tentas começar? Pelo menos escreve aqui o código das estruturas. Ou pensas que alguém vai copiar o código das tuas fotos? Penso que é importante mostrares a questão 1.

Em termos de preguiça é o cúmulo!

Ainda por cima embirro com as pessoas que dizem "rotina" 🙂 Isso é malta que vem do Fortran, não falha...

E o uso das maiúsculas é escusado.

[Rui Carlos]

Para a construção da árvore, tens aqui uma animação que te permite perceber como é que uma árvore é construída.

Depois estás a fazer uma espécie de travessia pos-order, em que para cada nó da árvore, imprimes a soma do seu valor e dos seus descendentes.

Para a questão dois, podes usar a função calcula (questão 1) como ponto de partida.

[pablomarcolino]

Então mas nem tentas começar? Pelo menos escreve aqui o código das estruturas. Ou pensas que alguém vai copiar o código das tuas fotos? Penso que é importante mostrares a questão 1.

Em termos de preguiça é o cúmulo!

Ainda por cima embirro com as pessoas que dizem "rotina" 🙂 Isso é malta que vem do Fortran, não falha...

E o uso das maiúsculas é escusado.

meu brother não estou iniciando, desculpe se dei está transparência!

quero entender a lógica e como se desenvolve!

Para a construção da árvore, tens aqui uma animação que te permite perceber como é que uma árvore é construída.

Depois estás a fazer uma espécie de travessia pos-order, em que para cada nó da árvore, imprimes a soma do seu valor e dos seus descendentes.

Para a questão dois, podes usar a função calcula (questão 1) como ponto de partida.

obrigado estou dando uma olhada agora no link a qual me mandou!

Para a construção da árvore, tens aqui uma animação que te permite perceber como é que uma árvore é construída.

Depois estás a fazer uma espécie de travessia pos-order, em que para cada nó da árvore, imprimes a soma do seu valor e dos seus descendentes.

Para a questão dois, podes usar a função calcula (questão 1) como ponto de partida.

muitoo obrigado, consegui intender legal, ele mostra passo a passo para cada ponto que é executado. já intende como faz a 2, más essa 3 e 4 , não faço a minima ideia por onde começar!

[pablomarcolino]

confirme por favor se está certo! a numero 4 não estou conseguindo!

/* PABLO MARCOLINO
Questão 2 (1,0 ponto)
Escreva uma rotina que receba a raiz de uma árvore cujos nós têm a
estrutura definida na questão 1 e que calcule a altura de cada nó
registrando o resultado no campo alt da estrutura.
*/
// rotina que receba uma árvore
void insere(cel **r,int num)
{
cel *novo_no;
novo_no = (cel *)malloc(sizeof(cel));
if(*r == NULL)		//verifica se a raiz da arvore esta vazia
{
	novo_no->info = num;
	novo_no->esq = NULL;
	novo_no->dir = NULL;
	*r = novo_no;
}
else
{
	if((*r)->info < num)	//verifica se é maior que a raiz
	{
		insere(&(*r)->dir,num); // se maior que a raiz, insere no nodo direito.
	}
	else
	{
		insere(&(*r)->esq,num);  // se menor que a raiz, insere no nodo esquerdo.
	}
}
}

// rotina para calcular os nós de uma arvore
void calc_no(cel *r)  
{
if(r != NULL)
	 return -1; // altura de árvore vazia é -1
else {
  int he = altura( r->esq);
  int hd = altura( r->dir);
  if (he < hd) return hd + 1;
  else return he + 1;
  };
}


/* PABLO MARCOLINO
Questão 3 (3,0 pontos)
Escreva uma rotina recursiva que receba um ano e a raiz da árvore
e mostre os dados de todos os livros publicados naquele ano.
A busca deve ser otimizada considerando que a árvore está ordenada.

*/
cel *PR2QST3(cel *raiz, int ano){
lucro *temp;
if(raiz == NULL){
		printf("\n\t\tNão ha nenhum livro para o respectivo ano de %d", ano);return(NULL);
}
if(ano == raiz->ano){
	   temp = raiz->inicio;
	   while(temp != NULL){
				  printf("\nTITULO - %s AUTOR - %s \tQUANTIDADE DE PAGINAS - %d\n \n" temp->titulo, temp-> autor, temp->paginas);
				  temp = temp->prox;
	   } return(raiz);
}
else if(ano < raiz->ano)
return(PR2QST3(raiz->esq, ano));
else
return(PR2QST3(raiz->dir, ano));
}

[Rui Carlos]

Para a questão 4 a função é novamente semelhante à função da questão 1.

Vais ter uma função recursiva que começa nas folhas da árvore, e vai passando um valor acumulado para a raiz. Na questão 1 ela passava uma soma de três valores, e agora queres que passe um máximo de três valores (nó, e filhos).

[HappyHippyHippo]

Questão 2 (1,0 ponto)

... registrando o resultado no campo alt da estrutura.

onde está isto implementado ?

[pablomarcolino]

onde está isto implementado ?

é só para fazer uma rotina mlkin!

Para a questão 4 a função é novamente semelhante à função da questão 1.

Vais ter uma função recursiva que começa nas folhas da árvore, e vai passando um valor acumulado para a raiz. Na questão 1 ela passava uma soma de três valores, e agora queres que passe um máximo de três valores (nó, e filhos).

asssim?

Questão 4

void maisLivros(cel *raiz, int *ano, int *quant)
{
 if(raiz == null)
   return -1;
 int quantLivros = 0;
 livro *temp = raiz -> inicio;
 while(temp != null){
   quantLivros++;
   temp = temp -> prox;
 }
 if(quantLivros > *quant)
 {
   *quant = quantLivros;
   *ano = raiz -> ano;
 }
}

[Rui Carlos]

Onde está a chamada recursiva?

[HappyHippyHippo]

é só para fazer uma rotina mlkin!

como queiras ... a nota é tua ...