VPF::Пожалуйста помогите с деревом

tor1988

Дата 17.8.2006, 16:10 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 17.8.2006

Репутация: нет
Всего: нет

Помогите написать ДБ- дерево(нужное описание есть в к ниге Никлауса Вирта "Алгоритмы и структуры данных" стр 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!

Это сообщение отредактировал(а) Earnest - 17.8.2006, 16:57

Earnest

Дата 17.8.2006, 16:57 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 2
Всего: 183

Для домашних заданий, курсовых, существует "Центр Помощи"

Тема перенесена!

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

...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »