Using a recursive procedure
and dispose to destroy
a binary tree and free its memory

     The following function demonstrates (visually) how to dispose of a binary tree using a recursive method. After the tree has been destroyed it is ready to be reused, and the memory it was allocated has been freed. The code uses three buttons (add, to add a string to the tree, show to output to the tree to a memo, and a destroy button to dispose of the binary tree. The input string is taken from an edit box, and a the form requires a memo both to print out the tree, and to print out the disposal of the tree (allowing visual comfirmation that the code is working properly and the tree is in fact being completely disposed of). In truth, if the code is not working correctly the program will crash with a pointer error before it leaves any nodes 'hanging in space' (cut off from the root of the tree, and also consuming memory after they are no longer needed). If you have a program that will be using the binary tree again and again, it is important to free up the resources being used by the tree.

     You can download the code for the unit as a text file by right clicking on the following link -> binary_tree_dispose.txt

     You can find further discussion of binary trees by visiting the following page - > Insertion on a binary tree.

     The binary tree is initialized in the FormCreate event handler. Because the 'key' value that will be used to sort entries in the tree is a string the key is set to the lowest possible value on the tree, a string containing nothing. A pointer named 'tail' is used instead of the value 'nil' to indicate a that nothing is contained on a node (the traversal of the tree has reached a dead end). When the first item is inserted onto the 'head' of the tree it will be attached to the right pointer of the tree (less than values are inserted on the left pointer of a binary tree, and values greater than are inserted on the right pointer, a binary tree containing a record of values sandwiched between two pointers by definition.

     An ordered, sorted binary tree is created by the Insertion code (search left on the tree if the insertion value is less than the value of the current node on the tree, otherwise search right until the 'dead end' (the tail or 'nil' condition is reached). Create a new node, and then properly attach the node as a leaf (both pointers set to the 'dead end'). Attach the new leaf on the left if it is less than the insertion value, or on the right if it is greater than the insertion value. In this example the insertion routine is a procedure, but it could easily be made into a function which returns the position of the newly created link if the tree holds records with multiple fields which must be filled in after the key value has been properly inserted into the tree.

     The destroy function, is a recursive function, since disposing of a binary tree lends itself well to recursion as a method. What happens is that the tree is completely traversed, and then the stacked up recursive calls begin to return one after another in proper order and the tree is destroyed starting from the bottom and working back towards the top. In this way leafs are always destroyed first, and no node on the tree is ever destroyed without first destroying all leafs and 'sub-leafs' attached to the node. If you include the memo you can get visual feedback confirming that this is in fact what is happening and that all nodes on the tree are being properly disposed of.

.

unit Unit1;
interface
uses
 Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
 StdCtrls;
type
 link=^node;
 node=record keyname:string;  l, r:link end;
 TForm1 = class(TForm)
   Memo1: TMemo;
   Edit1: TEdit;
   AddButton: TButton;
   DestroyButton: TButton;
   ShowTreeButton: TButton;
   procedure FormCreate(Sender: TObject);
   procedure AddButtonClick(Sender: TObject);
   Procedure TreeInsert(keytext:string; q:link);
   procedure ShowTreeButtonClick(Sender: TObject);
   Procedure PrintTree(q:link);
   procedure DestroyButtonClick(Sender: TObject);
   procedure DestroyTree(q:link);
   procedure FormShow(Sender: TObject);
 private
   { Private declarations }
 public
   { Public declarations }
 end;

var
 Form1: TForm1;
 head, tail:link;

implementation

{$R *.DFM}

procedure TForm1.FormCreate(Sender: TObject);
begin
Memo1.Lines.Clear;
Edit1.Text:='';
new(tail); new(head);
head^.keyname:=''; head^.r:=tail;  head^.l:=tail;
end;


procedure TForm1.AddButtonClick(Sender: TObject);
begin
    If Edit1.Text<>'' then begin
       TreeInsert(Edit1.Text, head);
       Edit1.Text:='';
    end;
    Edit1.SetFocus;
end;

Procedure TForm1.TreeInsert(keytext:string; q:link);
var st:link;
begin
repeat
     st:=q;
     if keytext<q^.keyname then q:=q^.l else q:=q^.r;
until q=tail; {traverse tree left is less than current key, right if greater
               until a 'dead end' is reached, attach node as leaf}

new(q); q^.keyname:=keytext; {new node}
q^.l:=tail; q^.r:=tail; {set pointers of leaf to 'dead end'}
if keytext<st^.keyname then st^.l:=q else st^.r:=q; {attach left is < right if >}
end;

procedure TForm1.ShowTreeButtonClick(Sender: TObject);
begin
Memo1.Lines.Clear;
PrintTree(head);
end;

Procedure Tform1.PrintTree(q:link);
begin
    if q<>tail then begin
       PrintTree(q^.l);
       Memo1.Lines.Append(q^.keyname);
       PrintTree(q^.r);
    end;
end;

procedure TForm1.DestroyButtonClick(Sender: TObject);
begin
DestroyTree(head^.r); {first node > head, don't destroy head}
head^.r:=tail; {head pointing nowhere now, set to dead end}
Edit1.SetFocus;
end;

procedure TForm1.DestroyTree(q:link);
begin
    if q<>tail then begin
       DestroyTree(q^.l);
       DestroyTree(q^.r);
       Memo1.Lines.Append('Destroying ' + q^.keyname);
       Dispose(q);

    end;
end;

procedure TForm1.FormShow(Sender: TObject);
begin
Edit1.SetFocus;
end;
end.