Технический форум

Технический форум (http://www.tehnari.ru/)
-   C/C++/С# (http://www.tehnari.ru/f42/)
-   -   Бинарные деревья (http://www.tehnari.ru/f42/t78707/)

Fenix 25.09.2012 19:07

Бинарные деревья
 
Вложений: 1
Доброго времени суток! Собственно прошу указать на ошибку (что-то идиотское упускаю)
Ошибка в том, что после выполнения процедуры итеративного построения случайного дерева поиска затирается адрес корня дерева.
vertex *AddVertex - процедура итеративного построения
//create BST - после этого комментария идет косячный блок

В работоспособности процедуры построения уверен на 95%.
За ранее спасибо!

Код:

/*** sapd - lab_2 ***/
#include <stdio.h>
#include <stdlib.h>
#define SIZE 100

struct vertex //структура дерева
            {
            vertex *left;
            vertex *right;
            int data;
            } *root,*sroot, *sroot1 ; 
int array[SIZE];

//create tree
vertex *IDSP(int L, int R)
{
 int i;     
 vertex *r;
 if(L>R) return NULL;
 else
 {
  i=(L+R)/2;
  r=new vertex;
  r->data=array[i];
  r->left=IDSP(L,i-1);
  r->right=IDSP(i+1,R);
  return r;
 }
}

//create binare search tree
vertex *AddVertex(int data, vertex *root)
{
 vertex **p;
 p=&root;
 while(*p!=NULL)
 {
  if(data<(*p)->data) p=&((*p)->left);
  if(data>(*p)->data) p=&((*p)->right);
  else break;
 }
 if(*p==NULL)
 {
  *p=new vertex;
  if((*p)==NULL) 
  {
  printf("Error 0x42! Not enought memory!\n");
  }
  (*p)->data=data;
  (*p)->right=NULL;
  (*p)->left=NULL;
  //printf("%4d",(*p)->data);
 }
}

vertex *AddVertexRec(int data, vertex *&p)
{
 if(!p)
 {
  p=new vertex;
  if(p==NULL) 
  {
  printf("Error 0x42! Not enought memory!\n");
  }
  p->data=data;
  p->left=NULL;
  p->right=NULL;
 }
 else
 {
  if(data<p->data) AddVertexRec(data,p->left);
  else
  if(data>p->data) AddVertexRec(data,p->right);
 }
}

//detour
void Detour(vertex *p)
{
 if(!p) return;
 Detour(p->left);
 printf("%4d",p->data);
 Detour(p->right);
}


//size
int Size(vertex *p)
{
 if(!p) return 0;
 return 1+Size(p->left)+Size(p->right);
}

//max
int max(int a, int b)
{
 if(a>b)return a;
 return b;
}

//height
int Height(vertex *p)
{
 if(!p)return 0;
 return 1+max(Height(p->left),Height(p->right));
}

//midheight
float MidHeight(vertex *p, int layer)
{
 if(!p) return 0;
 return layer+MidHeight(p->left,layer+1)+MidHeight(p->right,layer+1);
}



//MAIN
int main()
{
//create array
 printf("array:\n");
 for(int i=0;i<SIZE;i++)
 {
  array[i]=array[i-1]+rand()%10;
  printf("%4d",array[i]);
 }
 
//create IBST
 printf("\n");
 root=IDSP(0,SIZE-1);
 printf("tree:\n");
 Detour(root);
 printf("\ntree size: %4d",Size(root));         
 printf("\ntree height: %4d",Height(root));
 float Mheight=MidHeight(root,1)/Size(root);
 printf("\ntree midheight: %4.2f",Mheight);
 printf("\n");
 
 
//create BST rec
 printf("array:\n");
 for(int i=0;i<SIZE;i++)
 {
  array[i]=rand()%100;
  printf("%4d",array[i]);
 }
 printf("\n");
 printf("tree:\n");
 sroot=NULL;
 for(int i=0;i<SIZE;i++)
  AddVertexRec(array[i],sroot); 
 Detour(sroot);
 printf("\ntree size: %4d",Size(sroot));         
 printf("\ntree height: %4d",Height(sroot));
 Mheight=MidHeight(sroot,1)/Size(sroot);
 printf("\ntree midheight: %4.2f",Mheight);
 printf("\n");
 

//create BST
 printf("\n");
 printf("array:\n");
 for(int i=0;i<SIZE;i++)
 {
  array[i]=rand()%100;
  printf("%4d",array[i]);
 }
 printf("\n");
 printf("tree:\n");
 sroot1=NULL;
 for(int j=0;j<SIZE;j++)
  AddVertex(array[j],sroot1); 
 Detour(sroot1);
 printf("\ntree size: %4d",Size(sroot1));         
 printf("\ntree height: %4d",Height(sroot1));
 Mheight=MidHeight(sroot,1)/Size(sroot1);
 printf("\ntree midheight: %4.2f",Mheight);
 printf("\n");
 
 
 printf("\nProgramm complite successfull.Stop 0x00\n");
 system("PAUSE");     
 return 0;
}

Исходник в аттаче.

Gruvi 26.09.2012 23:08

Эмм а ты попробуй обратный выход сделать через рекурсию. обычно все бинарные деревья строятся на рекурсии.

Fenix 27.09.2012 07:04

Блин, еще раз:
не работает именно итеративный метод и именно он нужен по лабораторке.
Где-то при вызове процедуры косяк, а где не вижу.

Fenix 01.10.2012 18:26

HEEEEEELLP! tehno028:tehnari_ru_281:

Fenix 05.10.2012 11:07

Вложений: 1
Всем большое спасибо за помощь! Разобрался в проблеме.
Исправлена процедура AddVertex:
Код:

void AddVertex(int data, vertex *&root)
{
 vertex **p;
 p=&root;
 while((*p)!=NULL)
 {
  if(data<(*p)->data) p=&((*p)->left);
  else
  if(data>(*p)->data) p=&((*p)->right);
  else
    if(data==(*p)->data) break;

 }
 if((*p)==NULL)
 {
  *p=new vertex;
  if((*p)==NULL) 
  {
  printf("Error 0x42! Not enought memory!\n");
  }
  (*p)->data=data;
  (*p)->right=NULL;
  (*p)->left=NULL;
 
 }
}

Красным выделены изменения в коде.
Переработанный исходник в аттаче:


Часовой пояс GMT +4, время: 09:19.

Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.