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.

instruction:

1. • Open a new Pascal file in your text editor or IDE.
   • Add following line to the file:
     program bintree;
   • 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;
     
      
   • Copy the following into the editor to construct an empty tree:
     function MakeTree: BinTree;
     begin
     MakeTree := nil
     end;
   • Place the following source code into your file to test the tree for emptiness:
     function IsEmptyTree (B: BinTree): Boolean;
     begin
     IsEmptyTree := (B = nil);
     end;
   • 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;
   • 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;
   • 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;
   • 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;
   • 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;
   • Add these last lines to your file to finish the Pascal program:
     begin
     end.

take from : http://www.ehow.com/how_12173168_implement-binary-tree-using-pascal.html