ArvoreB

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

// ArvoreB.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
//---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define ordem 2
//---------------------------------------------------------------------------
typedef int tipoElemento;
typedef struct tipoPagina *apontaPagina;
typedef struct tipoItem{
 tipoElemento elemento;
 apontaPagina filho;
} tipoItem;
typedef struct tipoPagina{
 int numElementos;
 apontaPagina pagina0;
 tipoItem itens[2*ordem+1];
} tipoPagina;
void fazVazia(tipoPagina **A){
}
void pesquisa(tipoPagina *A, tipoElemento e, int h, tipoElemento *u){
}
tipoItem insere(tipoPagina *A,tipoElemento e, int *h){
 int i,j;
 tipoItem novoItem;
 tipoPagina *novaPagina;
 *h=1;
 if (A == NULL){
 novoItem.elemento=e;
 novoItem.filho=NULL;
 }
 else{
 i=0;
 while ((i < A->numElementos) && (e > A->itens[i].elemento))
 i++;
 i--;
 if (i <= 2*ordem){
 if (i==-1)
 novoItem = insere(A->pagina0, e, h);
 else
 if (e > A->itens[i].elemento)
 novoItem = insere(A->itens[i].filho, e, h);
 else
 *h=0;
 if (*h == 1){
 for(j=A->numElementos; j>i+1; j--)
 A->itens[j]=A->itens[j-1];
 A->itens[j]=novoItem;
 if (A->numElementos < 2*ordem){
 *h=0;
 (A->numElementos)++;
 }else{
 novaPagina=(tipoPagina *)malloc(sizeof(tipoPagina));
 novaPagina->pagina0=A->itens[ordem].filho;
 j=0;
 for (i=ordem+1; i<=2*ordem; i++){
 novaPagina->itens[j]=A->itens[i];
 j++;
 }
 novoItem=A->itens[ordem];
 novoItem.filho=novaPagina;
 A->numElementos=ordem;
 novaPagina->numElementos=ordem;
 *h=1;
 }
 }
 }
 }
 return novoItem;
}
void insereArvoreB(tipoPagina **P,tipoElemento e){
 tipoPagina *novaRaiz;
 tipoItem novoItem;
 int h;
 novoItem=insere(*P, e, &h);
 if (h != 0){
 novaRaiz=(tipoPagina *)malloc(sizeof(tipoPagina));
 novaRaiz->pagina0 = *P;
 novaRaiz->itens[0] = novoItem;
 novaRaiz->numElementos=1;
 *P = novaRaiz;
 }
}
void underflow(tipoPagina *C, tipoPagina *A, int s, int *h){
 tipoPagina *b;
 int i,k,mb,mc;
 mc=C->numElementos;
 if (s < mc-1){ // Verifica se página a dir. pode emprestar
 s=s+1;
 b=C->itens[s].filho;
 mb=b->numElementos;
 k=(mb-ordem+1)/2;
// A->itens[ordem-1]=C->itens[s-1];
 A->itens[ordem-1]=C->itens[s];
 A->itens[ordem-1].filho=b->pagina0;
 if (k > 0){ // aqui trata caso possa emprestar
 for(i=0;i<k-2;i++)
 A->itens[i+ordem]=b->itens[i];
 C->itens[s]=b->itens[k];
 C->itens[s].filho=b;
 b->pagina0=b->itens[k].filho;
 mb=mb-k;
 for(i=0;i<mb;i++)
 b->itens[i]=b->itens[i+k];
 b->numElementos=mb;
 A->numElementos=ordem-1+k;
 *h=0;
 }else{ // aqui trata a fusao das paginas
 for(i=0;i<ordem;i++)
 A->itens[i+ordem]=b->itens[i];
 for(i=s;i<mc-1;i++)
 C->itens[i]=C->itens[i+1];
 A->numElementos=2*ordem;
 C->numElementos=mc-1;
 *h=mc<=ordem;
 free(b);
 }
 }else{ // neste caso a página da direita não pode emp. ou não existe
 if (s==0)
 b=C->pagina0;
 else
 b=C->itens[s-1].filho;
 mb=b->numElementos+1;
 k=(mb-ordem)/2;
 if (k > 0){ // a página da esquerda pode emprestar
 for (i=ordem-1-1;i>=0;i--)
 A->itens[i+k]=A->itens[i];
 A->itens[k-1]=C->itens[s];
 A->itens[k-1].filho=A->pagina0;
 mb=mb-k;
 for (i=k-1;i>=1;i--)
 A->itens[i]=b->itens[i+mb];
 A->pagina0=b->itens[mb].filho;
 C->itens[s]=b->itens[mb-1];
 C->itens[s].filho=A;
 b->numElementos=mb-1;
 A->numElementos=ordem-1+k;
 *h=0;
 }else{ // a página da esquerda não pode emprestar. Funde com a esquerda
 b->itens[mb]=C->itens[s];
 b->itens[mb].filho=A->pagina0;
 for (i=0;i<ordem;i++)
 b->itens[i+mb+1]=A->itens[i];
 b->numElementos=2*ordem;
 C->numElementos=mc-1;
 if (C->numElementos<ordem)
 *h=1;
 else
 *h=false;
 free(A);
 }
 }
}
void del(tipoPagina *P, tipoPagina *A, int R, int *h){
 tipoPagina *q;
 q=P->itens[P->numElementos-1].filho;
 if (q != NULL){
 del(q,A,R,h);
 if (*h == 1)
 underflow(P,q,P->numElementos,h);
 }else{
// P->itens[P->numElementos-1].filho=A->itens[R].filho;
	 A->itens[R].elemento=P->itens[P->numElementos-1].elemento;
 P->numElementos=P->numElementos-1;
 *h=P->numElementos < ordem;
 }
}
void remove(tipoPagina *A, tipoElemento e, int *h){
 int i,j;
 tipoPagina *temp;
 if (A == NULL)
 *h=0;
 else{
 i=0;
 while ((i < A->numElementos) && (e > A->itens[i].elemento))
 i++;
// if (i>=A->numElementos-1)
// i--;
 if (i==0)
 temp=A->pagina0;
 else
 temp=A->itens[i-1].filho;
 if (e == A->itens[i].elemento){
 if (temp==NULL){
 for (j=i;j<A->numElementos-1;j++)
 A->itens[j]=A->itens[j+1];
 (A->numElementos)--;
 if (A->numElementos < ordem)
 *h=1;
 else
 *h=0;
 }
 else{
 del(temp,A,i,h);
 if (*h == 1)
 underflow(A, temp, i-1, h);
 }
 }else{
 remove(temp, e, h);
 if (*h == 1)
 underflow(A, temp, i-1, h);
 }
 }
}
void removeArvoreB(tipoPagina **A, tipoElemento e){
 int h;
 tipoPagina *q;
 remove(*A, e, &h);
 if (h == 1)
 if ((*A)->numElementos == 0){
 q = *A;
 *A = (*A)->pagina0;
 free(q);
 }
}
void imprimeArvoreB(tipoPagina *A){
 int i;
 if (A!=NULL){
 imprimeArvoreB(A->pagina0);
 for(i=0; i<A->numElementos;i++){
 printf("%d \n",A->itens[i].elemento);
 imprimeArvoreB(A->itens[i].filho);
 }
 }
}
int _tmain(int argc, _TCHAR* argv[])
{
 tipoPagina *arvore = NULL;
 int opcao, posicao;
 char caracter;
 tipoElemento elemento;
 opcao=1;
 insereArvoreB(&arvore, 10);
 insereArvoreB(&arvore, 20);
 insereArvoreB(&arvore, 30);
 insereArvoreB(&arvore, 35);
 insereArvoreB(&arvore, 40);
 insereArvoreB(&arvore, 50);
 insereArvoreB(&arvore, 60);
 insereArvoreB(&arvore, 65);
 insereArvoreB(&arvore, 72);
 insereArvoreB(&arvore, 75);
 insereArvoreB(&arvore, 80);
 insereArvoreB(&arvore, 68);
 removeArvoreB(&arvore,72);
 removeArvoreB(&arvore,68);
// removeArvoreB(&arvore,12);
// removeArvoreB(&arvore,15);
// removeArvoreB(&arvore,10);
// removeArvoreB(&arvore,70);
// removeArvoreB(&arvore,58);
 fflush(stdin);
 while (opcao!=0){
 printf("\n");
 printf("M E N U\n");
 printf("1 - Faz arvore vazia\n");
 printf("2 - Insere elemento\n");
 printf("3 - Remove elemento\n");
 printf("4 - Caminha em ordem\n");
 printf("0 - Termina\n");
 scanf("%d",&opcao);
 switch (opcao){
 case 1:
 fazVazia(&arvore);
 break;
 case 2:
 printf("qual elemento a inserir: ");
 scanf("%d",&elemento);
 fflush(stdin);
 insereArvoreB(&arvore,elemento);
 break;
 case 3:
 printf("qual elemento a remover: ");
 scanf("%d",&elemento);
 removeArvoreB(&arvore,elemento);
 break;
 case 4:
 printf("\n");
 imprimeArvoreB(arvore);
 break;
 }
 }
 return 0;
}