Помогите написать ДБ- дерево(нужное описание есть в к ниге Никлауса Вирта "Алгоритмы и структуры данных" стр 307) на си++,ПОЖАЛУЙСТА.Помогите испрамить ошибку в моем коде или если не сложно выложите свой:
Пишите на [email protected]
Заранее благодарен.
| Код |
#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <cstdio>
#define NULL 0
struct DB{
int v;
int h;
DB *l;
DB *r;
};
DB *pt,*root,*tree,*fuck,*derevo,*t;
int help=0,right=0,tab=0,perestanovka=0;
void print(DB *root,int tab)
{
int t=0;
printf("-> %d\n",root->v);
if (root->r!=NULL) {
for(t=0;t<=tab;t++){printf(" ");}
if(root->r->h==1) printf("hR"); //h-zna4it goRizonTal'na9 ssiLka
if(root->r->h==0) printf("vR"); //v-verTikal'na9
print(root->r,tab+1);
}
if (root->l!=NULL) {
for(t=0;t<=tab;t++){printf(" ");}
printf("L");
print(root->l,tab+1);
}
}
void addroot(DB *root, int v){root->v=v;root->l=NULL;root->r=NULL;root->h=0;} //sozdaem koren'
DB* add(DB *root, int v) {
if (root->l==NULL&&root->r==NULL&&v<root->v){ //v -smotri NikLays ViRt str.307(ALGORITMbl i STRYKTYRbl DAHHblX)
root->r=(DB *)malloc((size_t)sizeof(DB));
help=root->v;
root->r->v=v;
root->v=root->r->v;
root->r->v=help;
root->r->r=NULL;
root->r->l=NULL;
root->h=0;
root->r->h=1;
right=root->r->v;
}
if(root->r==NULL&&root->l==NULL&&v>root->v){ //a
root->r=(DB *)malloc((size_t)sizeof(DB));
root->r->v=v;
root->r->r=NULL;
root->r->l=NULL;
root->h=0;
root->r->h=1;
right=root->r->v;
}
if(root->r!=NULL&&root->l==NULL&&v>root->r->v) { //b
root->l=(DB *)malloc((size_t)sizeof(DB));
help=root->v;
root->v=right;
root->l->v=help;
root->r->v=v;
root->l->l=NULL;
root->l->r=NULL;
root->r->l=NULL;
root->r->r=NULL;
root->h=1;
root->r->h=0;
root->l->h=0;
}
if(root->r!=NULL&&root->l==NULL&&v<root->v){ //g
root->l=(DB *)malloc((size_t)sizeof(DB));
root->l->v=v;
root->r->v=right;
root->l->l=NULL;
root->l->r=NULL;
root->r->l=NULL;
root->r->r=NULL;
root->h=1;
root->l->h=0;
root->r->h=0;
}
if(root->l==NULL&&v>root->v&&root->r!=NULL&&v<root->r->v){ // spoRnii' sly4ai'(navernoe vhodit v "b"ili"g")
root->l=(DB *)malloc((size_t)sizeof(DB));
help=root->v;
root->l->v=help;
root->v=v;
root->r->v=right;
root->l->l=NULL;
root->l->r=NULL;
root->r->l=NULL;
root->r->r=NULL;
root->h=1;
root->l->h=0;
root->r->h=0;
}
if(root->r!=NULL&&root->l!=NULL&&root->v<v){ //derevo yveli4ivaets9(Rastet)
add(root->r, v);
}
if(root->l!=NULL&& root->r!=NULL&&root->v>v)
add(root->l, v);
return root;
};
DB* rebild(DB *derevo,int v) { //fynkci9 peresTroeni9 dereva
if(derevo->l!=NULL&&derevo->r!=NULL&&derevo->r->r!=NULL){
if(derevo->l->h==1&&derevo->r->h!=1||derevo->r->h==1&&derevo->r->r->h==1||derevo->r->h==1&&derevo->l->h==1){
perestanovka=1; // proizoi'det perestanovka
if (derevo->l->h==1&&derevo->r->h!=1){ //v
fuck=derevo;
tree=derevo->l->r;
derevo=derevo->l;
derevo->r=fuck;
derevo->r->l=tree;
derevo->r->h=1;
derevo->h=0;
}
if(derevo->r->h==1&&derevo->r->r->h==1) { //b
fuck=derevo;
tree=derevo->r->l;
derevo=derevo->r;
derevo->l=fuck;
derevo->l->r=tree;
derevo->r->h=0;
derevo->l->h=0;
derevo->h=1;
}
if(derevo->r->h==1&&derevo->l->h==1){ //g
derevo->h=1;
derevo->r->h=0;
}
}
if(perestanovka==0){ if(v>derevo->v){ //perestanovki ne BblLo =>prover9eM daL'she
rebild(derevo->r,v);} //!!!!voznikaet problema s vozvrawaeMblM zna4enieM!!!!!
if(v<derevo->v){
rebild(derevo->l,v);}}
}
else return root;
root=derevo;
v=0;
return root;
};
void main(){
int i,f=0;
root=(DB *)malloc((size_t)sizeof(DB));
printf("Vvedite element ili 0 for exit:\n");
cin>>i;
addroot(root,i);
print(root,0);
printf("\n");
cin>>i;
while(i!=0){
add(root, i);
if(f>=3){rebild(root,i);}
print(root,0);
f=f++;
perestanovka=0;
cin>>i;
}
if(i==0)exit(0);
}
|
Модератор: нужно пользоваться тегами code! |