LINUX.ORG.RU

Построение бинарного дерева


0

0

Всем привет!
Вот решил использовать в программе структуру бинарного дерева, и чтобы проверить правильность его построения построил его визуальное представление с помощью OpenGL. Как оказалось оно строится неправильно - как-то однобоко, хотя алгоритм построения вроде был правильный :(
А в последнее время вообще вылетает с SEGFAULT в _int_malloc в libc...
Уже целый день парюсь - не могу понять в чем ошибка!
Вот полный текст программы:

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <GL/gl.h>
#include <GL/glu.h>
#include <GL/glut.h>

typedef struct
{
GLdouble x;
GLdouble y;
GLdouble z;
} TreeVertex;

typedef struct node *link;
struct node
{
TreeVertex vertex;
int flag;
link l;
link r;
link parent;
};

static int lf = 0;
static int rf = 0;

void TreeINIT(link TreeObject, int deep)
{
if( TreeObject == NULL ) return;
int count = (int)pow(2, (deep - 1));
if( lf < count )
{
rf = 0;
lf++;
TreeObject->l = malloc(sizeof(*TreeObject));
TreeObject->l->parent = TreeObject;
TreeINIT(TreeObject->l, deep);
}
else
{
TreeObject->l = NULL;
}
if( rf < count )
{
lf = 0;
rf++;
TreeObject->r = malloc(sizeof(*TreeObject));
TreeObject->r->parent = TreeObject;
TreeINIT(TreeObject->r, deep);
}
else
{
TreeObject->r = NULL;
}
};

void TreeCalculate(link TreeObject)
{
TreeObject->vertex.x = TreeObject->parent->vertex.x + TreeObject->flag * drand48() *2;
TreeObject->vertex.y = TreeObject->parent->vertex.y + drand48();
TreeObject->vertex.z = TreeObject->parent->vertex.z + (drand48() - drand48());
printf("X=%f Y=%f Z=%f\n", TreeObject->vertex.x, TreeObject->vertex.y, TreeObject->vertex.z);
};

void TreeBASE(link TreeObject, void (*TreeCalculate)(link))
{
if (TreeObject == NULL) return;
(*TreeCalculate)(TreeObject);
if (TreeObject->l != NULL)
{
TreeObject->l->flag = -1;
TreeBASE(TreeObject->l, TreeCalculate);
}
if (TreeObject->r != NULL)
{
TreeObject->r->flag = 1;
TreeBASE(TreeObject->r, TreeCalculate);
}
return;
};

void xvTreeDraw(link TreeObject)
{
glBegin(GL_LINES);
glVertex3d(TreeObject->parent->vertex.x, TreeObject->parent->vertex.y, TreeObject->parent->vertex.z);
glVertex3d(TreeObject->vertex.x, TreeObject->vertex.y, TreeObject->vertex.z);
glEnd();
};

void TreeDraw(link TreeObject, void (*xvTreeDraw)(link))
{
if(TreeObject == NULL) return;
(*xvTreeDraw)(TreeObject);
TreeDraw(TreeObject->l, xvTreeDraw);
TreeDraw(TreeObject->r, xvTreeDraw);
};

void xvTree(GLdouble member_height, int deep)
{
link TreeObject = NULL;

lf = 0;
rf = 0;
glLineWidth(3);
glColor3d(0, 1, 0);
glBegin(GL_LINES);
glVertex3d(0, 0, 0);
glVertex3d(0, 2, 0);
glEnd();
TreeObject = malloc(sizeof(*TreeObject));
if (TreeObject != NULL)
{
TreeObject->vertex.x = 0;
TreeObject->vertex.y = 2;
TreeObject->vertex.z = 0;
TreeObject->parent = TreeObject;
TreeObject->flag = -1;
TreeINIT(TreeObject, deep);
TreeBASE(TreeObject, TreeCalculate);
TreeDraw(TreeObject, xvTreeDraw);
free(TreeObject);
}
};

void Display(void)
{
static int time = 0;

glClear( GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT );
glPushMatrix();
//glTranslated(0, -4, 2);
glRotated(time / 2, 0, 1, 0);
glLineWidth(5);
glColor3d(0,0,1);
xvTree(0, 5);
glPopMatrix();
glutSwapBuffers();
time++;
};

void Idle(void)
{
};

void Reshape(int width,int height)
{
glViewport(0,0,width,height);
glMatrixMode( GL_PROJECTION );
glLoadIdentity();
glOrtho(-5,5, -5,5, 2,12);
gluLookAt( 0,0,5, 0,0,0, 0,1,0 );
glMatrixMode( GL_MODELVIEW );
};

int main(int argc, char* argv[])
{
float pos[4] = {3,3,3,1};
float dir[3] = {-1,-1,-1};

GLfloat mat_specular[] = {1,1,1,1};

glutInitWindowPosition(50, 10);
glutInitWindowSize(400, 400);
glutInitDisplayMode( GLUT_RGB | GLUT_DEPTH | GLUT_DOUBLE );
glutCreateWindow( "GLUT Template" );
glutReshapeFunc(Reshape);
glutDisplayFunc(Display);
//glutIdleFunc(Idle);

glEnable(GL_DEPTH_TEST);
glEnable(GL_COLOR_MATERIAL);
glEnable(GL_LIGHTING);
glEnable(GL_LIGHT0);
glEnable(GL_SMOOTH);
glLightfv(GL_LIGHT0, GL_POSITION, pos);
glLightfv(GL_LIGHT0, GL_SPOT_DIRECTION, dir);
glMaterialfv(GL_FRONT, GL_SPECULAR, mat_specular);
glMaterialf(GL_FRONT, GL_SHININESS, 128.0);

glutMainLoop();
return EXIT_SUCCESS;
};

★★★★

Re: Построение бинарного дерева

А о балансировке что-то слышал?

Код для дерева уже написан, например в Glib из GTK+ - http://developer.gnome.org/doc/API/2.0/glib/glib-Balanced-Binary-Trees.html или map из STL для C++

Если погуглить то можно найти статьи как их балансировать. Еще лучше купить какой-нибудь учебник на эту тему. Видел на раскладках книгу Кнута и еще была книга его ученика (фамилию не помню) с примерами на C.

kosmonavt ()
Ответ на: Re: Построение бинарного дерева от kosmonavt

Re: Построение бинарного дерева

>и еще была книга его ученика (фамилию не помню) с примерами на C.

Р. Седжвик. "Фундаментальные алгоритмы на С++" и то же самое на Java. В обеих книгах НЕ C, что плохо. IMHO лучше Кнута читать.

CyberCoder ()

Re: Построение бинарного дерева

> Уже целый день парюсь - не могу понять в чем ошибка!

Бывает и дольше. В M$ с 1998 не могут найти ошибку на FAT32.

В чем смысл этого дерева? И в чем заключается алгоритм?

kosmonavt ()

Re: Построение бинарного дерева

Со всем кодом разбираться лень, но, судя по бэктрейсу, прога уходит в бесконечную рекурсию (gdb backtrace, смотрите сами). 
Предполагаю, что в строке 
---
TreeINIT(TreeObject->l, deep); 
---
должно быть deep-1 или deep+1, например.

phoenix ★★★★ ()
Ответ на: Re: Построение бинарного дерева от phoenix

Re: Построение бинарного дерева

По-моему здесь:

rf = 0; lf++; ... } ... if( rf < count ) { lf = 0; rf++; ...

Ошибка в том, что rf и lf обнуляются на каждом вызове.

kosmonavt ()
Ответ на: Re: Построение бинарного дерева от kosmonavt

Re: Построение бинарного дерева

Без обнуление дерево получается совсем не того размера что надо, да и еще все левые ветки, и только по одной правой. Да и использовать glib не хочется...

XVilka ★★★★ ()
Ответ на: Re: Построение бинарного дерева от CyberCoder

Re: Построение бинарного дерева

> В обеих книгах НЕ C, что плохо. IMHO лучше Кнута читать.

Есть версия и на C. Но Кнут, конечно, лучше.

Cantor ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.