BST and SIGSEGV

[rockberto]

Hi there, I have a problem with a BST program, whenever I try to run this a SIGSEGV error occurs. The files are:

node.pas

Unit Node;

Interface
 Type
   NodePtr = ^TNode;
   TNode = Class
     FData : Integer;
     FLeft,FRight : NodePtr;
     Constructor Create(PData : Integer);
   End;

Implementation
 Constructor TNode.Create(PData : Integer);
   Begin
     FData := PData;
     FLeft := NIL;
     FRight := NIL;
   End;

End.

bst.pas

Unit BST;

Interface
 Uses
   Node;
 Type
   TBST = Class
     Private
       Procedure InsertData(PData : Integer; var PNode : NodePtr);
       Procedure PrintData(var PNode : NodePtr);
       Function Empty(var PNode : NodePtr) : Boolean;
     Public
       FRoot : NodePtr;
       Procedure Insert(PData : Integer);
       Procedure Print;
       Function Delete : Boolean;
       Function Search(PData : Integer) : Boolean;
   End;

Implementation
 Procedure TBST.InsertData(PData : Integer; var PNode : NodePtr);
   Var
     tmpNode : TNode;
   Begin
     if Empty(PNode) then
       begin
         tmpNode.Create(PData);
         PNode := @tmpNode;
       end
     else
      if PData < PNode^.FData then
       InsertData(PData,PNode^.FLeft)
     else
       InsertData(PData,PNode^.FRight)
   End;

 Procedure TBST.PrintData(var PNode : NodePtr);
   Begin
     if not Empty(PNode) then
       begin
         PrintData(PNode^.FLeft);
         write(PNode^.FData,' ');
         PrintData(PNode^.FRight);
       end
   End;

 Function TBST.Empty(var PNode : NodePtr) : Boolean;
   Begin
     Empty := (PNode = NIL)
   End;

 Procedure TBST.Insert(PData : Integer);
   Begin
     InsertData(PData,FRoot)
   End;

 Procedure TBST.Print;
   Begin
     PrintData(FRoot)
   End;

 Function TBST.Delete : Boolean;
   Begin
   End;

 Function TBST.Search(PData : Integer) : Boolean;
   Begin
   End;

End.

tarea2.pas

Program Tarea2;

Uses
 BST;

Var
 miArbol : TBST;

Begin
 miArbol.Create;
 miArbol.Insert(8);
 miArbol.Insert(16);
 miArbol.Insert(5);
 miArbol.Insert(55);
 miArbol.Insert(-1);
 miArbol.Print;
 readln();
End.

When I hit the run button the error appears over

Function TBST.Empty(var PNode : ANode) : Boolean;
...
Empty := (PNode = NIL) <-------

But when I change it to

Empty := TRUE

Now the same error appears over

Constructor TNode.Create(PData : Integer);
...
FData := PData; <-------

I think is something about initializing something but I don't know where. I just started learning this language, so forgive me if it's something stupid.

Any help is a appreciated.

Take care,
Roberto Ramirez

OS: Microsoft Windows XP [Versión 5.1.2600]
IDE: Lazarus Editor v0.9.20 beta

[radu84]

first of all, from where you are getting started, i haven't see the root of your tree. you create something from nothing.

i haven't worked with lazarus but in pascal when a new node is added then a memory zone must be allocated. in pascal this was made through NEW function.

also, try to run your program step by step. in this way you'll see how the program is running.

best regards,

[rockberto]

Lazarus is an IDE from the freepascal project that tries to emulate Delphi but in the end it's a Pascal program, or so I understood.

I use the Create function instead of the New function because this is a class and New expects a pointer. Anyway, you were right, the node isn't initialized because I was using it the wrong way:

miArbol := TBST.Create; <-- Good
miArbol.Create; <-- Bad

tmpNode := TNode.Create(PData) <-- Good
tmpNode.Create(PData) <-- Bad

The root node doesn't exists at the begining (empty tree), there is a FRoot (NodePtr) that points to NIL and when you add a node (Insert(Integer)) it points to it, then when you add another it verifies if it's not empty in wich case creates a new node and points one of its pointers (NodePtr) to it and so on.

Now the problem lies in the PrintData procedure because I get the same message and I'm trying to solve it, but again I don't know where the problem is. Maybe when it reaches PrintData(PNode^.FLeft) it gives PrintData(NIL) then it uses Empty(NIL) and it recives something that is not allocated, but right now is three in the morning so I'll give it a brain tomorrow.

More help is well appreciated.

Thanks