код:
задача:
создание дерева, добавление в него листов удаление листа дерева, на лишние записи в структуре и в коде, не относящееся к дереву просьба внимания не обращать.
проблема:
при удалении листа сначала находится адрес удаляемого листа функцией поиска search, которая возвращает указатель на удаляемый лист, затем функция Delete в зависимости от случая обрубает указатели на удаляемый лист, и связывает оставшиеся после удаления листы в зависимости от случая.
-> функция delete выполняется, по завершении выполнения выводится результат что адрес удалённого листа = 0, тобиш он якобы удалён, но после удаления выведя дерево на экран функцией Print дерево целёхонько. я вот непойму, там вроде не создаётся дубликата передаваемого указателя *s в Delete, но получается так что удаляется всё локально, только в функции...
подпроблема:
не могу освободить память выделенную new с помощью операции delete, причём new было использовано в функции создания листа дерева, а delete в функции удаления, но delete действия производит но результат нулевой - после неё всё на прежднем месте - и адрес указателя и адреса переменных, выделенные new.
Код:
#include <cstdlib>
#include <iostream>
typedef struct tree{ // обьявляем тип
char data[10]; //дата изьятия в формате xx.xx.xxxx
char naimenovanie[50]; // наименование предмета
int izyatiya; // кол-во изъятых едениц, по кол-ву изьятий будем составлять дерево
int stoimost; // обьявленная стоимость предмета
struct tree *L; // указатель на левый лист
struct tree *R; // указатель на правый лист
struct tree *parent; // указатель на родителя листа
}TREE; // навание типа - TREE
TREE *root=NULL; // задаём глобальные указатели, root- корень дерева, и дополнительные указатели.
int Delete(TREE *s)/*Функция удаления узла из дерева*/
{
TREE *tmp;
printf("OLD:\n");
printf("Delete: s adr= %d;\n",s);
printf("Delete: s parent adr= %d;\n",s->parent);
printf("Delete: s->R adr= %d;\n",s->R);
printf("Delete: s->L adr= %d;\n",s->L);
if( (s->R!=NULL || s->L!=NULL) && s->parent!=NULL )
{
if(s->L==NULL && s->R==NULL)
{
if(s==s->parent->R)
s->parent->R=NULL;
else
s->parent->L=NULL;
s=NULL;
}
else if(s->L==NULL && s->R!=NULL)
{
s->R->parent=s->parent;
s->parent=s->R;
s=NULL;
}
else if(s->L!=NULL && s->R==NULL)
{
s->L->parent=s->parent;
s->parent=s->L;
s=NULL;
}
else if(s->L!=NULL && s->R!=NULL)
{
s->R->parent=s->parent;
tmp=s->R;
while(tmp->L!=NULL)
tmp=tmp->L;
tmp->L=s->L;
s->L->parent=tmp;
s=NULL;
}
}
else
{
if(s->L==NULL && s->R==NULL)
{
s=NULL;
}
else if(s->L!=NULL && s->R==NULL)
{
s->L->parent=NULL;
root=s->L;
s=NULL;
}
else if(s->L==NULL && s->R!=NULL)
{
s->R->parent=NULL;
root=s->R;
s=NULL;
}
else if(s->L!=NULL && s->R!=NULL)
{
s->R->parent=NULL;
root=s->R;
tmp=s->R;
while(tmp->L!=NULL)
tmp=tmp->L;
tmp->L=s->L;
s->L->parent=tmp;
s=NULL;
}
}
printf("NEW:\n");
printf("Delete: s adr= %d;\n",s);
}
int ReturnMax(TREE *s)/*Функция печати максимального элемента дерева*/
{
while(s->R!=NULL )
{
s=s->R;
}
return s->izyatiya;
}
int ReturnMin(TREE *s)/*Функция печати минимпльного элемента*/
{
while(s->L!=NULL)
{
s=s->L;
}
return s->izyatiya;
}
void Insert(TREE *s, int &iz, int &stoim, char dat[], char naim[])
{
TREE *temp,*tmp;
int i=0;
if(s!=NULL) // если звено дерева существует - находим место куда положить новый элемент, сравнивая его с текущими пробираясь по звеньям дерева
{
if(iz < s->izyatiya)
{
if(s->L!=NULL)
Insert(s->L,iz,stoim,dat,naim);
else
{
temp=s;
s->L=new TREE;
if(s->L!=NULL)
{
s=s->L;
s->L=NULL;
s->R=NULL;
s->parent=temp;
s->izyatiya=iz;
s->stoimost=stoim;
i=0;
do
{
s->naimenovanie[i]=naim[i];
i++;
}
while(naim[i]!='\0');
i=0;
do
{
s->data[i]=dat[i];
i++;
}
while(dat[i]!='\0');
}
else // если не хватает памяти - выводим сообщение
printf( "ЌҐ ¤®бв в®з® ®ЇҐа вЁў®© Ї ¬пвЁ!.\n" );
}
}
else
if(iz > s->izyatiya)
{
if(s->R!=NULL)
Insert( s->R,iz,stoim,dat,naim);
else
{
temp=s;
s->R=new TREE;
if(s->R!=NULL)
{
s=s->R;
s->L=NULL;
s->R=NULL;
s->parent=temp;
s->izyatiya=iz;
s->stoimost=stoim;
i=0;
do
{
s->naimenovanie[i]=naim[i];
i++;
}
while(naim[i]!='\0');
i=0;
do
{
s->data[i]=dat[i];
i++;
}
while(dat[i]!='\0');
}
else // если не хватает памяти - выводим сообщение
printf( "ЌҐ ¤®бв в®з® ®ЇҐа вЁў®© Ї ¬пвЁ!.\n" );
}
}
}
}
void Print( TREE *s )/*Функция печати элементов дерева*/
{
if(s!=NULL)
{
if(s->L!=NULL)
Print(s->L);
//printf("Naimenovanie tovara: %s;\n", s->naimenovanie);
//printf("Data: %s;\n", s->data);
printf("-------begin--------\n");
printf("Izuatiya: %d;\n", s->izyatiya );
printf("s adr= %d;\n",s);
printf("s parent adr= %d;\n",s->parent);
printf("s->R adr= %d;\n",s->R);
printf("s->L adr= %d;\n",s->L);
printf("--------end-------\n");
//printf("Stoimost: %d;\n", s->stoimost);
if(s->R!=NULL)
Print(s->R);
}
else
{
printf( "Tree is empty...\n" );
system("PAUSE");
}
}
TREE *Search( TREE *koren, int element )/* рекурсивная функция поиска узла по значению*/
{
if (koren==NULL) return NULL;
else if (koren->izyatiya==element){ printf("Search adr =%d\n;",koren); return koren;}
else if (element < koren->izyatiya) return Search(koren->L, element);
else return Search(koren->R, element);
}
int main()
{
TREE *temp;
int choice = 0, item;
int iz, stoim;
char dat[10], naim[50];
while( choice != 7 ){
printf( "\n1 to insert new element\n2 to print the tree\n3 to delete element"
"\n4 to find the element\n5 to find max element\n6 to find min element\n7 for exit\nEnter your choice...\n" );
scanf( "%d", &choice );
switch( choice ){
case 1:
if(root==NULL) // если дерева не существует - создаём его корень
{
root=new TREE;
root->L = NULL;
root->R = NULL;
root->parent = NULL;
printf( "Enter iz...\n" );
scanf( "%d", &root->izyatiya);
//printf( "Enter stoim...\n" );
//scanf( "%d", &root->stoimost);
//printf( "Enter data...\n" );
//scanf( "%s", &root->data );
//printf( "Enter naim...\n" );
//scanf( "%s", &root->naimenovanie);
}
else // если дерево уже существует, то добавляем новые элементы посредством функции
{
printf( "Enter iz...\n" );
scanf( "%d", &iz );
//printf( "Enter stoim...\n" );
//scanf( "%d", &stoim );
//printf( "Enter data...\n" );
//scanf( "%s", &dat );
//printf( "Enter naim...\n" );
//scanf( "%s", &naim );
Insert(root,iz,stoim,dat,naim);
}
break;
case 2:
Print(root);
break;
case 3:
printf( "Enter te item...\n" );
scanf( "%d", &item );
Delete(Search(root,item));
break;
case 4:
printf( "Enter the item you want to find...\n" );
scanf( "%d", &item );
if((temp=Search(root,item))!=NULL)
printf("%d",temp->izyatiya);
else
{
printf( "No such element...\n" );
system("PAUSE");
}
break;
case 5:
printf("%d",ReturnMax(root));
break;
case 6:
printf("%d",ReturnMin(root));
break;
case 7:
break;
default:
printf("Wrong key. Try again...\n");
system("PAUSE");
break;
}
}
return 0;
}создание дерева, добавление в него листов удаление листа дерева, на лишние записи в структуре и в коде, не относящееся к дереву просьба внимания не обращать.
проблема:
при удалении листа сначала находится адрес удаляемого листа функцией поиска search, которая возвращает указатель на удаляемый лист, затем функция Delete в зависимости от случая обрубает указатели на удаляемый лист, и связывает оставшиеся после удаления листы в зависимости от случая.
-> функция delete выполняется, по завершении выполнения выводится результат что адрес удалённого листа = 0, тобиш он якобы удалён, но после удаления выведя дерево на экран функцией Print дерево целёхонько. я вот непойму, там вроде не создаётся дубликата передаваемого указателя *s в Delete, но получается так что удаляется всё локально, только в функции...
подпроблема:
не могу освободить память выделенную new с помощью операции delete, причём new было использовано в функции создания листа дерева, а delete в функции удаления, но delete действия производит но результат нулевой - после неё всё на прежднем месте - и адрес указателя и адреса переменных, выделенные new.
