The Binary Tree Data Structure

A binary tree structure is a dynamic structure that can grow to any size. It has two pointers in each node, known as the left and right pointers as this is the way that trees are generally drawn.

Nodes in a binary tree are defined in the following way:

type
 datatype=string;
 treepointer=^treenode;
 treenode=record
                dataitem:datatype;
                leftchild, rightchild: treepointer;
               end;

The datatype in this model can be easily changed and further data fields could be added to the record.

When items are inserted into a tree the approach followed is to place items less than the current data item in the next left hand node and items greater than the current data item in the next right hand node. If a node is full this rule is applied again in a recursive fashion.

Thus if 'p' is inserted into an empty tree it can be represented as:

             p
          /     \
       nil        nil

If 'a' is added the tree becomes:

             p
          /     \
        a        nil

If 'b' is added the tree becomes

             p
          /     \
        a        nil
          \
           b

If 's' is added the tree becomes

             p
           /   \
        a        s
          \
           b

And so on.

When data has been entered the tree may be traversed in one of three main ways:

• inorder - visit left node;  display data in node;  visit right node.
• pre-order - display data in node;  visit left node;  visit right node.
• post-order - visit left node;  visit right node;  display data in node.

An in-order traversal of the tree above is: a b p s

A pre-order traversal of this tree is: p a b s

A post-order traversal of this tree is: b a s p

You should check these patterns for yourself and also verify that the program produces correct results.

Programming a binary tree is not as hard as it might seem, once the recursive nature of the structure is understood. To insert an item into a tree we must look for an empty node, calling the insert procedure recursively until one is found:

procedure TForm1.Button1Click(Sender: TObject);

procedure insertitem(var rootpointer: treepointer; item:datatype);
begin
 if rootpointer=nil then //new empty tree node
 begin
  new(rootpointer);
  with rootpointer^ do
  begin
   dataitem:=item;
   leftchild:=nil;
   rightchild:=nil;
  end;
 end
 else
  if item < rootpointer^.dataitem then
  insertitem(rootpointer^.leftchild, item)
  else
   insertitem(rootpointer^.rightchild, item);
end;

begin
 insertitem(rootpointer, edit1.text);
 edit1.Text:='';
 edit1.SetFocus;
end;

Variables are declared in either the public section of the class or in the var section immediately after it:

Form1: TForm1;
rootpointer:treepointer;
item:datatype;
traversal:string;

To traverse a tree in the sorted order of the items:

procedure TForm1.Button2Click(Sender: TObject);

procedure inorder(rootpointer:treepointer);
begin
 if not (rootpointer = nil) then
 with rootpointer^ do
 begin
  inorder(leftchild); //these three instructions do the business
  traversal:=traversal+dataitem +' ';
  inorder(rightchild)
end;

end;

begin
 traversal:='';
 inorder(rootpointer);
 memo1.Text:=traversal;
end;

To perform the pre-order traversal we only need to change the order of the three instructions in the respective procedures:

procedure TForm1.Button3Click(Sender: TObject);

procedure preorder(rootpointer:treepointer);
begin
 if not (rootpointer = nil) then
 with rootpointer^ do
 begin
  traversal:=traversal+dataitem +' ';  //these three instructions are put in different order
  preorder(leftchild);
  preorder(rightchild)
end;

end;

begin
 traversal:='';
 preorder(rootpointer);
 memo2.Text:=traversal;
end;


procedure TForm1.Button4Click(Sender: TObject);

procedure postorder(rootpointer:treepointer);
begin
 if not (rootpointer = nil) then
 with rootpointer^ do
 begin
  postorder(leftchild);  //these three instructions are put in different order
  postorder(rightchild);
  traversal:=traversal+dataitem +' ';
end;

end;

begin
 traversal:='';
 postorder(rootpointer);
 memo3.Text:=traversal;
end;

Each of the traversals is a variation on the others and each one is recursive, visiting the nodes and outputting the results according to the requirements of the traversal.

We can add a routine to clear the tree and the displays:

procedure TForm1.Button6Click(Sender: TObject);
begin
 rootpointer:=nil;
 memo1.Clear;
 memo2.clear;
 memo3.clear;
end;

Here is a possible implementation with items entered in order: nigel, ann, kate, mary, suzanne, david:

Back