C Exibir elementos de Árvore AVL

[Junior Conceição]

Pessoal, estou tendo problemas para exibir dados de um funcionário cadastrado numa árvore AVL, consigo exibir se a árvore tiver apenas inteiros, mas se for uma árvore de estruturas o programa não exibe os dados, alguém pode me ajudar?

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h>
#include <stdbool.h>
#define tam 0

typedef struct Funcionario{
    char nome[50];
    int id;
    int idade;
    struct Funcionario *prox;
    struct Funcionario *ant;
} func;

typedef struct fil{
    int id;
    func *prim;
    func *ult;
} Fila;

struct Node{ 
	int key;
	char nome[50];
	int idade;
	struct Node *left; 
	struct Node *right; 
	int height; 
};

Fila *fila;
int id_avl = 0;

//inicializa fila
void iniciafila(){
    fila = (Fila *) malloc(sizeof(Fila));
    fila->prim = NULL;
    fila->ult = NULL;
}

//libera fila
void liberafila(){
    free(fila);
}
 
int height(struct Node *N) { 
	if (N == NULL) 
		return 0; 
	return N->height; 
} 

int max(int a, int b) { 
	return (a > b)? a : b; 
} 

struct Node* newNode(func *f){ 
	struct Node* node = (struct Node*) malloc(sizeof(struct Node)); 
	node->key = f->id;
	strcpy(node->nome, f->nome);
	node->idade = f->idade; 
	node->left = NULL; 
	node->right = NULL; 
	node->height = 1;
	return(node); 
} 

struct Node *rightRotate(struct Node *y) { 
	struct Node *x = y->left; 
	struct Node *T2 = x->right; 
	x->right = y; 
	y->left = T2; 
	y->height = max(height(y->left), height(y->right))+1; 
	x->height = max(height(x->left), height(x->right))+1; 
	return x; 
} 

struct Node *leftRotate(struct Node *x) { 
	struct Node *y = x->right; 
	struct Node *T2 = y->left; 
	y->left = x; 
	x->right = T2; 
	x->height = max(height(x->left), height(x->right))+1; 
	y->height = max(height(y->left), height(y->right))+1; 
	return y; 
} 

int getBalance(struct Node *N) { 
	if (N == NULL) 
		return 0; 
	return height(N->left) - height(N->right); 
}

struct Node* insert(struct Node* node, func *f) { 
	int key = f->id;
	if (node == NULL) 
		return(newNode(f)); 
	if (key < node->key) 
		node->left = insert(node->left, f); 
	else if (key > node->key) 
		node->right = insert(node->right, f); 
	else  
		return node;
	node->height = 1 + max(height(node->left), height(node->right)); 
	int balance = getBalance(node);
	if (balance > 1 && key < node->left->key) 
		return rightRotate(node); 
	if (balance < -1 && key > node->right->key) 
		return leftRotate(node); 
	if (balance > 1 && key > node->left->key){ 
		node->left = leftRotate(node->left); 
		return rightRotate(node); 
	}
	if (balance < -1 && key < node->right->key){ 
		node->right = rightRotate(node->right); 
		return leftRotate(node); 
	}
	return node; 
}

void preOrder(struct Node *root){ 
	if(root != NULL){
		printf("Id: %d\n", root->key);
		printf("Nome: ");
		puts(root->nome);
		printf("Idade: %d\n", root->idade); 
		preOrder(root->left); 
		preOrder(root->right); 
	} 
}

//fila de funcionarios
void enfileira(func *f){
	fila->id++;
	if (fila->prim == NULL){
		fila->prim = f;
		fila->ult = f;
	}else{
		fila->ult->prox = f;
		f->ant = fila->ult;
		fila->ult = f;
		fila->ult->prox = fila->prim;
	}
}

//insere funcionário
func *novofunc(char *nome, int idade){
	id_avl++;
	func *f = (func *)malloc(sizeof(func));
	strcpy(f->nome, nome);
	f->idade = idade;
	f->prox = NULL;
	f->ant = NULL;
	f->id = id_avl;
	return f;
}

//rotacionar fila de funcionarios
void rotacionaFila(){
	func *aux = fila->prim;
	if (aux->prox != NULL){
		fila->prim = fila->prim->prox;
		fila->prim->ant = NULL;
		fila->ult->prox = aux;
		aux->ant = fila->ult;
		aux->prox = fila->prim;
		fila->ult = aux;
	}else
		return;
}

void menu(){
	printf("Escolha uma opcao:\n");
	printf("1. Cadastrar funcionario\n");
	printf("2. Exibir Funcionários\n");
}

int main(){
	int opcao, idade;
	char nome[50];
	iniciafila();
	struct Node *raiz = NULL;
	menu();
	while (opcao != 0){
		scanf("%d", &opcao);
		switch (opcao){
		case 1:
			printf("Digite o nome do funcionario que deseja cadastrar:\n");
			setbuf(stdin, NULL);
			scanf("%s", nome);
			printf("Digite a idade:\n");
			scanf("%d", &idade);
			enfileira(novofunc(nome, idade));
			insert(raiz, novofunc(nome, idade));
			break;
		case 2:
			printf("\nArvore AVL - Pré Ordem:\n");
			preOrder(raiz);
			break;
		default:
			break;
		}
	}
	liberafila();
	return 0;
}

 

[arfneto]

1 hora atrás, Junior Conceição disse:

consigo exibir se a árvore tiver apenas inteiros, mas se for uma árvore de estruturas o programa não exibe os dados

 

Não entendi. preOder() recebe o endereço de um nó. Você quer dizer que se mudar  node para conter apenas um int ao invés da estrutura de funcionário aí roda? Mas não teria nada a ver com a estrutura então...

 

De todo modo, talvez fosse mais seguro --- e certamente mais útil --- se usasse em node apenas um (void*). Assim poderia usar a estrutura com qualquer conteúdo

[Junior Conceição]

@arfneto sim, se eu inserir inteiros na árvore ao invés da estrutura, ele exibe normalmente.

2 minutos atrás, arfneto disse:

De todo modo, talvez fosse mais seguro --- e certamente mais útil --- se usasse em node apenas um (void*). Assim poderia usar a estrutura com qualquer conteúdo

Você diz se eu tirar as variáveis de dentro da estrutura Node e colocar uma variável (void*)? Dessa forma pode funcionar?

[arfneto]

Sim.

 

Pode ter algo errado ainda, não testei o código. É complexo como você sabe --- ao menos eu acho complexo. Mas o fato de estar funcionando para algum tipo de dado é importante. O difícil nessa estrutura é programar as rotações direito, para manter a árvore balanceada. E parece que você já passou desta fase.

 

Por outro lado, essa estrutura é só um container e compare

struct Node{ 
	int key;
	char nome[50];
	int idade;
	struct Node *left; 
	struct Node *right; 
	int height; 
};

com

struct Node{ 
	struct Node *left; 
	struct Node *right; 
	int height; 

    void*    conteudo;  
};

ou mesmo algo assim

struct node
{ 
	struct node  *left; 
	struct node  *right; 
	unsigned int height; 
    void*        conteudo;  
};
typedef struct node Node;

E aí fica claro que Node é um container.

E aí você pode colocar as funções por exemplo em um header, o código em um arquivo .c

E aí você pode compilar esse arquivo para uma biblioteca, um arquivo .lib ou .so ou sei lá

 

E daí pra diante você pode usar essa estrutura em qualquer programa, sem precisar sequer ter o arquivo .c. Esse afinal é o propósito dessas coisas.

 

Ao colocar os dados misturados com a estrutura você não poderá usar depois sem alterar, e vai ter que alterar o código da árvore toda vez que mudar alg nos dados, certo? 

 

 

adicionado 21 minutos depois

Acho melhor deixar um exemplo...

 

Claro que para a primeira implementação isso implica em algumas mudanças na filosofia, mas depois compensa muito. Veja por exemplo como funciona o qsort() em C e acho que vai entender porque estou falando isso.

 

qsort() é declarada assim:

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

E graças a isso classifica qualquer coisa. Isso porque não misturou os dados na estrutura. É a mesma noção.