Бинарные деревья
Вложений: 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;
}
Исходник в аттаче.
|