How to Implement a Binary Tree Using Pascal

Binary trees can form the building blocks of efficient searching and sorting algorithms and because of this have wide application in computer science. As Pascal has support for records and pointer types, you can elegantly implement binary trees in it. Use your Pascal program as the basis of a binary heap priority queue or modify it to support any kind of comparable data.

Instructions

1. Open a new Pascal file in your text editor or IDE.

2. Add following line to the file:
   program bintree;

3. Type the next section of code into your editor to define the basic types for the binary tree:
   Type
   BinTree = ^Node;
   Node = Record
   I: integer;
   L, R: BinTree;
   end;

4. Copy the following into the editor to construct an empty tree:
   function MakeTree: BinTree;
   begin
   MakeTree := nil
   end;

5. Place the following source code into your file to test the tree for emptiness:
   function IsEmptyTree (B: BinTree): Boolean;
   begin
   IsEmptyTree := (B = nil);
   end;

6. Include the following lines in your script to construct a child node with the given integer value:
   function MakeNode (I: integer): BinTree;
   var
   Res: BinTree;
   begin
   New (Res);
   Res^.I := I;
   Res^.L := MakeTree;
   Res^.R := MakeTree;
   MakeNode := Res;
   end;

7. Add these lines to free a tree from the given root node:
   procedure DeallocateTree (var B: BinTree);
   begin
   if not IsEmptyTree (B) then begin
   DeallocateTree (B^.L);
   DeallocateTree (B^.R);
   Dispose (B);
   end
   end;

8. Place the next section of code into your file to insert the given value into its ordered location in the binary tree.:
   procedure InsertInTree (I: integer; var B: BinTree);
   begin
   if IsEmptyTree (B) then
   B := MakeNode (I)
   else if I < B^.I then
   InsertInTree (I, B^.L)
   else
   InsertInTree (I, B^.R)
   end;

9. Add the following source code to search a tree for a given value:
   function FindInTree (S: integer; B: BinTree): Boolean;
   begin
   if IsEmptyTree (B) then
   FindInTree := False
   else if S < B^.I then
   FindInTree := FindInTree (S, B^.L)
   else if B^.I < S then
   FindInTree := FindInTree (S, B^.R)
   else begin
   FindInTree := True
   end
   end;

10. Paste the next procedure into your Pascal program to see the contents of the tree in sorted order:
    procedure PrintTree (B: BinTree);
    begin
    if not IsEmptyTree (B) then begin
    PrintTree (B^.L);
    writeln (B^.I);
    PrintTree (B^.R)
    end
    end;

11. Add these last lines to your file to finish the Pascal program:
    begin
    end.

Resources

• Pascal Central: The Pascal Programming Language