Thread: problem in freeing a "tree" of stuctures

the original program is not that old, anyway as I've said I'm far from being a good programmer and for sure I don't have any idea of obsolete or update notations

but the problem I guess isn't the notation

thanks for your reply but that won't work
it is my fault, I haven't explained how this sort of tree is implemented

let me do a scheme of that (the vertical bars are NextLevel pointers and the horizontal ones are NextSame Level pointers)

0
|
0 - 0 - 0
|
0 - 0 - 0 - 0
|
0 - 0

and all the nodes are linked with PreviousLevel pointer to the first of the previous level
the top one has a NULL pointer to previous level and the last ones of each level has a NULL pointer to NextSameLevel

I hope this is clear enough

Originally Posted by Salem

> Edit: It assumes that there are no links downwards from the second, third,
Each curs tests curs->NextLevel, so that wouldn't be a problem AFAIK.

Well, what I mean is, you go down all the way and kill the bottom level just fine. But as you go across the level above that, if each node going across tries to go down and kill the bottom level again, bad things could happen. But as you said, that's not how it's drawn and it's not what I expect, so hey.

probably I still wasn't clear enough
I have also tried it anyway and it is not working
I don't know if tabstop was saying something like this but anyway what I was trying to say is that at a certain level all the nodes are linked with a nextsamelevel relationship even if they belong to different father nodes
I guess the code you wrote is going to try to free some node more than once
after that the last level has not a netxlevel null pointer assigned so I think maxlev is necessary

No null pointers at the bottom of the tree? Yikes.

Anyway, the question is, do you have a way to make sure you get the entire level? (I.e., do you know a "left-most" node like you have in your drawing?) And if you don't have nulls at the right to stop nextsamelevel, things could get really sticky. If so, then you're golden:

Code:

if (n>0)
    call recursively with child node and n-1
clear out current level (set temp = nextsamelevel, free this, set this to temp, lather, rinse, repeat)

Originally Posted by tabstop

No null pointers at the bottom of the tree? Yikes.

the reason they are not needed in the program is that you know exactly how many levels you have and you use that sort of tree always backward from the last level to the root (so there is a NULL previous level pointer in the root)

Originally Posted by tabstop

Anyway, the question is, do you have a way to make sure you get the entire level? (I.e., do you know a "left-most" node like you have in your drawing?) And if you don't have nulls at the right to stop nextsamelevel, things could get really sticky.

the last node of a certain level has a NULL nextsamelevel pointer
about the leftmost node in a level I would say that for the first level is the one pointed with nextlevel by the root, for the second level is the one pointed with next level by the one pointed with nextlevel by the root and so on

Originally Posted by Salem

So you have complicated traversal code in other places as well?

IMO, you have an unnecessarily complicated linking structure when you have that kind of special case. Do you have a good reason for it?
I mean, what happens when you want another level, don't you have to go all through the tree and pick apart the lowest level so it's no longer the lowest level?


I just looked at your initial example and assumed it would be a regular tree where each Next pointer pointed to NULL if there was no more tree in that particular direction.

well I called that "a sort of tree" because it was not a regular tree and I had no idea if it had other names

so how is this thing used in the program and why it has to be in that way?

Code:

while (level<ordmax)
   {
   curs = (DBimages*)curs->NextLevel; 
   level++;
   }

ordmax is the height of the tree so with that as I've said in the previous answer you go to the last level

Code:

right = curs;
back = curs;
while (right) 
   {
   back = right;
   while (back->PreviousLevel != NULL) 
      {     
       do something;
       back = (DBimages*)back->PreviousLevel;
       }
    do something else;
    right = (DBimages*)right->NextSameLevel;
}

it is complicated I guess because it has to be
of course I have no idea if there is a easier way to do that, as I've said I'm not the one who wrote the program, but it works and that is enough for me

but now to add what I need to add if I don't free those trees when I don't use them anymore I'll run short of memory and since what I've tried to write to free it it doesn't work I'm here to ask some help

I'm sorry again if my previous explanations weren't clear enough

I've also tried with this:

Code:

void FreeDBimages (ptr,maxlev)
DBimages *ptr;
int maxlev;

{
DBimages *curs,*temp;
int level;
level=0;
curs=ptr;

while(level<maxlev){
  curs=(DBimages*)curs->NextLevel;
  level++;
}

while(curs!=NULL){
  temp=(DBimages*)curs->NextSameLevel;
  FreedVector(curs->point,3);
  FreeiVector(curs->face,2);
  free(curs);
  curs=temp;
}

printf("%d\n",maxlev);

if(maxlev>0)
	FreeDBimages(ptr,maxlev-1);
}

freeing level by level starting from the last one, but it does not work

And how does it "not work"?