14. Binary Tree Lists in Free Pascal

A binary tree is an extension of Link List. Basic Link List has only one link attached to the Node whearas basic Binary tree has two links attached to the Link(Node). The very first link in the tree forms the root of the tree, has a data and two link addresses showing the next links. The rule of Link attachments are: If data in current link(Link to be attached) > root data, current link is attached to the right if not it is attached to the left.

1. First the link is described with a type declaration as having a data and two link pointers right and left. root,temp,current are pointer variables are the type link.

type point = ^link;
link = record
data : integer;
right : point;
left : point;
end;

var i : integer;
root,temp,current : point;

2. The main program is to create tree root and get links to attach to the root.

createroot;
getlink ;

3. Read input integer and create root.

Procedure createroot;
Begin
Write('enter root integer = ');
readln(i);
new(root);
root^.data := i;
root^.right := nil;
root^.left := nil;
end;


4. Make links and attach to the tree. We create a current link and call addnode to add to the tree.

Procedure getlink ;
begin

for i := 1 to 5 do begin

new(current);
current^.data := i;
current^.right := nil;
current^.left := nil;

addnode(i,root);
readln;
end;
end;{end getlink }

6. In addnode we compare data of current node to be attached to the root and attach the node if the next address is vacant. If it can not be attached, start calling addnode with failed node address until vacant node is found for attaching the current node.

Procedure addnode( i : integer; temp : point );
begin
writeln;
write('i=',i,' trying to add node value: ',i,' at as= ',temp^.data,' ',i);


if i > temp^.data then if temp^.right = nil then
begin writeln(' right'); temp^.right := current; end
else addnode(i,temp^.right);

if i <= temp^.data then if temp^.left = nil then
begin writeln(' left'); temp^.left := current; end
else addnode(i,temp^.left);

end;


6. Program follows: If you run the program it will ask you for an integer to create the root node.

Program Program14;
(* Author: Rao S Lakkaraju *)
(* Pointer Basics _ Binary trees *)
uses crt,graph;

type point = ^link;
link = record
data : integer;
right : point;
left : point;
end;

var i : integer;
root,temp,current : point;


Procedure createroot;
Begin
Write('enter root integer = ');
readln(i);
new(root);
root^.data := i;
root^.right := nil;
root^.left := nil;
end;

Procedure addnode( i : integer; temp : point );
begin
writeln;
write('i=',i,' trying to add node value: ',i,' at as= ',temp^.data,' ',i);


if i > temp^.data then if temp^.right = nil then
begin writeln(' right'); temp^.right := current; end
else addnode(i,temp^.right);

if i <= temp^.data then if temp^.left = nil then begin writeln(' left'); temp^.left := current; end else addnode(i,temp^.left); end; Procedure getlink ; begin for i := 1 to 5 do begin new(current); current^.data := i; current^.right := nil; current^.left := nil; addnode(i,root); readln; end; end;{end getlink } Procedure displayorder (root : Point); begin IF root <> nil then begin

displayorder(root^.Left);
write(root^.Data);
displayorder(root^.Right);

end;
end;
{ Main Program Begins}

begin
clrscr;

createroot;
getlink ;

Write('Display tree Nodes: ');
Displayorder(root);
writeln;
Writeln('My fourteenth Pascal Program');

readln;
end.

Summary: Binary Trees in Pascal are just ordered Link Lists. The order is if the data in the current link is greater than the data in the last link, it is attached to the right of the last link otherwise attached to the left. With this rule in mind we traverse the tree(visit the links) starting from the root for a vacant spot to hang the branch(Link).