with Ada.Text_IO; use Ada.Text_IO;
with ada.integer_text_io; use ada.integer_text_io;
with ada.characters.handling;
package body binarysearchtree is
count:integer:=0;
function toLower (c : character) return character renames Ada.characters.handling.to_lower;
-- tolower - translates all alphabetic, uppercase characters
-- in str to lowercase
function toLower (Str : String) return String is
convert : String (str'Range);
begin
for x in convert'Range loop
convert (x) := toLower (str (x));
end loop;
return convert;
end toLower;
procedure InsertBinarySearchTree(Root: in out BinarySearchTreePoint; custName: in String10; custPhone: String10 ) is
p:binarySearchTreePoint:=root;
q:binarySearchTreePoint:=root;
t:binarySearchTreePoint;
begin
count:=count+1;
t:=new node;
t.info.name:=custName;
t.info.phoneNumber:=custPhone;
t.rLink:=t;
t.rLink:=t;
if root = null then
root:=t;
else
loop
if q/=null then
if toLower(custName) < toLower(q.info.name) then
if q.lLink=p then
p:=q;
exit;
end if;
p:=q;
q:=q.lLink;
elsif q.rTag = true then
p:=q;
q:=q.rLink;
else
p:=q;
exit;
end if;
else
exit;
end if;
end loop;
if toLower(p.info.name) > toLower(custName) then
t.lLink:=p.lLink;
p.lTag := true;
t.rLink:=p;
t.rTag:=false;
if t.lTag=true then
t.lLink.rLink:=t; --check for child and rethread tree
end if;
elsif toLower(p.info.name) <= toLower(custName) then
p.rLink:=t;
p.rTag:=true;
t.lLink:=p;
t.lTag:=false;
if t.rTag=true then
t.rLink.lLink:=t; --check for child and rethread tree
end if;
end if;
end if;
end InsertBinarySearchTree;
-- This procedure locates a customer using a binary search. A pointer is returned to the
-- customer record if they exist, otherwise a Null pointer is returned (in CustomerPoint).
-- The search must be implemented iteratively.
procedure FindCustomerIterative(Root: in BinarySearchTreePoint; CustomerName: in String10; CustomerPoint: out BinarySearchTreePoint) is
p:binarySearchTreePoint:=root;
temp:integer:=count;
begin
loop
if temp = 0 then
p:=null;
exit;
elsif toLower(p.info.name) = toLower(customerName) then
customerPoint:=p;
exit;
elsif toLower(p.info.name) > toLower(customerName) then
p:=p.lLink;
elsif toLower(p.info.name) <= toLower(customerName) then
p:=p.rLink;
end if;
temp:=temp-1;
end loop;
customerPoint:=p;
end FindCustomerIterative;
-- This procedure locates a customer using a binary search. A pointer is returned to the
-- customer record if they exist, otherwise a Null pointer is returned (in CustomerPoint).
-- The search must be implemented recursively.
procedure FindCustomerRecursive(Root: in BinarySearchTreePoint; CustomerName: in String10) is
p:binarysearchtreepoint;
begin
p:=root;
if p = null then
return;
elsif toLower(p.info.name) > toLower(customerName) then
findCustomerRecursive(p.lLink, customerName);
elsif toLower(p.info.name) < toLower(customerName) then
findCustomerRecursive(p.rLink, customerName);
elsif toLower(p.info.name) = toLower(customerName) then
put_line(p.info.phoneNumber);
return;
end if;
end FindCustomerRecursive;
-- This function returns the address of the next node in inorder taking advantage of threads.
-- The user may enter the tree at any random location. This is sometimes called an iteration
-- function or iterater (no recursion).
function InOrderSuccessor(TreePoint: in BinarySearchTreePoint) return BinarySearchTreePoint is
p:binarySearchTreePoint;
q:binarySearchTreePoint;
begin
p:=treePoint;
q := p.rLink;
if p.rTag = false then
p:=q;
else
while q.lTag = true loop
q := q.lLink;
end loop;
p:=q;
end if;
return p;
end InOrderSuccessor;
-- Access functions to return customer names and phone numbers.
function CustomerName(TreePoint: in BinarySearchTreePoint) return String10 is
begin
return treePoint.info.name;
end customerName;
function CustomerPhone(TreePoint: in BinarySearchTreePoint) return String10 is
begin
return treePoint.info.phoneNumber;
end customerPhone;
procedure init is
root:binarySearchTreePoint;
t:binarySearchTreePoint;
selection:integer:=0;
s:string10:=(others=>' ');
p:string10:=(others=>' ');
temp:integer:=0;
begin
loop
put_line("::Binary Search Tree Program::");
put_line("1)insert into binary search tree");
put_line("2)find customer iteratively");
put_line("3)find customer recursively");
put_line("4)inoder successor");
put_line("5)traverse inorder");
put_line("6)exit");
put("enter selection::");
get(selection);
if selection = 1 then
put("Please enter name::");
get(s);
put_line(s);
put("Please enter phone number::");
get(p);
put_line(p);
insertBinarySearchTree(root,s,p);
s:=(others=>' ');
p:=(others=>' ');
elsif selection = 2 then
put("Please enter name::");
get(s);
put_line(" ");
findCustomerIterative(root,s,t);
if t/=null then
put_line("Customer Phone::" & customerPhone(t));
else put_line("Customer not found in Tree");
end if;
elsif selection = 3 then
put("Please enter name::");
get(s);
put_line(" ");
findCustomerRecursive(root,s);
elsif selection = 4 then
put("Please enter name::");
get(s);
put_line(" ");
findCustomerIterative(root,s,t);
root:=inOrderSuccessor(t);
put_line("In order successor::");
put(root.info.name);
put_line(" ");
elsif selection = 5 then
put_line("Please enter starting point::");
put_line("1)start at root");
put_line("2)give node to start at");
get(selection);
if selection = 1 then
s:=customerName(root);
loop
t:=inOrderSuccessor(root);
root:=t;
if toLower(s) = toLower(root.info.name) then
exit;
else
put_line(root.info.name);
end if;
end loop;
elsif selection = 2 then
temp:=count;
put("Enter customer name::");
get(s);
findCustomerIterative(root,s,t);
put_line(customerName(t));
put_line(customerPhone(t));
root:=inOrderSuccessor(t);
loop
t:=inorderSuccessor(t);
put_line(customerName(t));
put_line(customerPhone(t));
temp:=temp-1;
exit when temp = 1;
end loop;
end if;
elsif selection = 6 then
exit;
end if;
end loop;
end init;
end binarysearchtree;