Arvore multidirecional

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1010 palavras )
  • Download(s) : 0
  • Publicado : 4 de junho de 2012
Ler documento completo
Amostra do texto
#include
#include
#include
#define n 4

/*
Geovane Vieira Gomes
Matricula: 200924461
Disciplina: Estrutura de Dados II
Compilador DevC++
Universidade Federal de Roraima – UFRR
*/

struct no {

int chave[n-1];
struct no *pai;
struct no *filhos[n];
}; typedef struct no No;

static int nchaves;


int informarValor() {
int num;
printf("Informeo numero: ");
scanf("%d", &num);
return num;
}

No* gerano (){
int i;
No* arvore = (No*)malloc(sizeof(No));
if (arvore == NULL){
printf ("Nao foi possivel alocar um no'!");
return NULL;
} else {
arvore->pai = NULL;
for(i = 0; i < nchaves; i++) {
arvore->chave[i] = 0;
}
for(i = 0; i < (nchaves+1); i++) {arvore->filhos[i] = NULL;
}
}
return arvore;
}
int busca(int valor, No *arvore) {
int i = 0;
if(arvore == NULL)
return 0;
for(i = 0; i < nchaves; i++){
if(valor == arvore->chave[i]) {
return 1;
} else if(valorchave[i]) {
return busca(valor,arvore->filhos[i]);
} else {
if(i == (nchaves-1)) { //Se chegou no final do vetor
returnbusca(valor, arvore->filhos[i+1]);
}
}
}
return 0;
}
void desenharNo(int valor, int espaco) {
int i;
for (i = 0; i < espaco; i++) printf(" ");
printf("%d\n", valor);
}
void desenharArvore(No *arvore, int espaco) {
int i;
for(i = 0; i < nchaves; i++) {
if (arvore == NULL) {
desenharNo(-1, espaco);
return;
}desenharNo(arvore->chave[i], espaco);
desenharArvore(arvore->filhos[i], espaco+1);
if(i == (nchaves-1)) desenharArvore(arvore -> filhos[i+1], espaco+1);
}
}

int verificaRaiz(No *raiz) {
if(raiz != NULL) {
return 1;
} else {
printf("Raiz vazia!");
return 0;
}
}

No* inserir(int valor, No *arvore) {
if(arvore == NULL) {
arvore = gerano();
arvore->chave[0] = valor;
return arvore;
}else {
int i;
int status = 1; //verifica se o vetor esta cheio
for(i = 0; i < nchaves; i++) {
if(arvore->chave[i] == 0) {
if(arvore->filhos[i] != NULL) {
arvore->filhos[i] = inserir(valor,arvore->filhos[i]);
} else if(arvore->filhos[i+1] != NULL) {
arvore->filhos[i+1] = inserir(valor,arvore->filhos[i+1]);
} else {
arvore->chave[i] = valor;
}status = 0;
break;
}
}

if(status == 1) {
i = 0;
for(i = 0; i < nchaves; i++){
if(valor < arvore->chave[i]) {
arvore->filhos[i] = inserir(valor,arvore->filhos[i]);
break;
} else {
if(i == (nchaves-1)) { //Se ele estiver no ultimo valor arvore->filhos[i+1] = inserir(valor,arvore->filhos[i+1]);
break;
}
}
}
} else {int aux, j, w;
No *aux_no = NULL;
//Ordena o vetor de informação
for(j = 0; j < nchaves; j++){
for(w = j + 1; w < nchaves; w++){
if(arvore->chave[j] > arvore->chave[w]){
//Ordena valor
aux = arvore->chave[j];
arvore->chave[j] = arvore->chave[w];
arvore->chave[w] = aux;//Ordena ponteiro
aux_no = arvore->filhos[j];
arvore->filhos[j] = arvore->filhos[w];
arvore->filhos[w] = aux_no;
}
}
}
}
}
return arvore;
}

No* remover(int valor, No *arvore){
int i = 0;
if(arvore == NULL) return NULL;
for(i = 0; i < nchaves; i++){
if(valor == arvore->chave[i]) {//Verifica se o no ta na folha
if(arvore->filhos[i] == NULL && arvore->filhos[i+1] == NULL) { int j, cont=0;
//Verifica se ele esta sozinho
for(j = 0; j chave[j] != 0) {
cont++;
}
}
if(cont == 1) { //Ele esta sozinho
free(arvore);
return NULL;
} else { //Ele nao esta sozinho
int aux, j, w;
No *aux_no = NULL;
arvore->chave[i] = 0;...
tracking img