{Insert values into a binary tree using a recursive disk file search as an example}
{uncommented source code followed by commented source code}

{http://www.awitness.org/delphi_pascal_tutorial/source/insert_binary_tree.html}

unit disk_search;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, FileCtrl;

type
  link=^node;
  node=record filename:string; ModTime:integer; l, r:link end;
  TForm1 = class(TForm)
    FileSearch: TButton;
    TreePrint: TButton;
    procedure FormCreate(Sender: TObject);
    procedure FileSearchClick(Sender: TObject);
    function FileLook(Filespec:string):boolean;
    Function TreeInsert(Fname:string; q:link):link;
    procedure TreePrintClick(Sender: TObject);
    Procedure PrintTree(q:link);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  head, tail: link;


implementation

{$R *.DFM}

procedure TForm1.FormCreate(Sender: TObject);
begin
new(tail); new(head);
head^.filename:=''; head^.r:=tail;  head^.l:=tail;

end;

procedure TForm1.FileSearchClick(Sender: TObject);
var
found:boolean;
begin
Found:=FileLook('f:\somefiles\*.*');
If found then MessageDlg('DUN!', mtInformation, [mbOk], 0)
   else MessageDlg('Directory does not exist', mtError, [mbOk], 0);

end;


Function TForm1.FileLook(Filespec:string):boolean;
var
  x:link;
  validres, ModifiedTime:integer;
  SearchRec  : TSearchRec;
  DirPath, FullName, Flname : string;
begin

     DirPath:=ExtractFilePath(FileSpec);
     Result:= DirectoryExists(DirPath);
     If not Result then exit;
     Flname:=ExtractFileName(FileSpec);
     validres := FindFirst(FileSpec, faAnyFile, SearchRec);
     while validres=0 do begin
          If (SearchRec.Name[1] <> '.') then begin {not a directory}

               FullName:=DirPath + LowerCase(SearchRec.Name);
               x:=TreeInsert(FullName, head);
               ModifiedTime:=FileAge(FullName);
                x^.ModTime:=ModifiedTime;
               If (SearchRec.Attr and faDirectory>0) then
                 FileLook(FullName+'\'+Flname);

          end;
          validres:=FindNext(SearchRec);

     end;

end;

Function TForm1.TreeInsert(Fname:string; q:link):link;
var st:link;
begin
repeat
      st:=q;
      if fname<q^.filename then q:=q^.l else q:=q^.r;
until q=tail;
new(q); q^.filename:=fname;
q^.l:=tail; q^.r:=tail;
if fname<st^.filename then st^.l:=q else st^.r:=q;
TreeInsert:=q;
end;



procedure TForm1.TreePrintClick(Sender: TObject);
var fs:textfile;
begin
assignfile(fs, 'c:\treeprint.txt');
rewrite(fs);
PrintTree(head);
CloseFile(fs);
MessageDlg('TREE DUN!', mtInformation, [mbOk], 0);
end;
Procedure Tform1.PrintTree(q:link);
begin
     if q<>tail then begin
        PrintTree(q^.l);
        Writeln(fs, q^.filename);
        PrintTree(q^.r);
     end;
end;

end.

{commented source code}




     Function TForm1.FileLook(Filespec:string):boolean;
     var
     x:link;

     {declare a local binary tree link...this will be used to receive the return value from the
     TreeInsert function so that the ModifiedDate value can be inserted into the correct node
     next to the filespec}

     validres, ModifiedTime:integer; {create integer for modtime}
     SearchRec : TSearchRec;
     DirPath, FullName, Flname : string;
     begin
        DirPath:=ExtractFilePath(FileSpec);
        Result:= DirectoryExists(DirPath);
        If not Result then exit;
        Flname:=ExtractFileName(FileSpec);
        validres := FindFirst(FileSpec, faAnyFile, SearchRec);
        while validres=0 do begin
           If (SearchRec.Name[1] <> '.') then begin 
              FullName:=DirPath + LowerCase(SearchRec.Name);
              x:=TreeInsert(FullName, head);

     {pass the filename and the 'head' (or 'root) pointer to the binary tree to the tree insert
     routine, and receive back in 'x' pointer the location at which the filename was inserted into
     the tree}

              ModifiedTime:=FileAge(FullName);{find mod date of file}

              x^.ModTime:=ModifiedTime;

     {use the 'x' pointer value returned by the TreeInsert function to insert the value into the
     last modified time of the file into the correct node of the tree beside the filename}

              If (SearchRec.Attr and faDirectory>0) then
                FileLook(FullName+'\'+Flname);
           end; {end if}
        validres:=FindNext(SearchRec);
     end; {end while}
     end;





     Function TForm1.TreeInsert(Fname:string; q:link):link;

     {pass the tree insert function the name of the file, and the 'head' or root pointer to the tree.
     The filename will function as the 'key' or sorting value for insertion into the tree for
     example 'apple' would be less than 'orange' files on the 'c:\' drive less than the 'd:\' drive
     etc.}

     var st:link; 

     {create a local binary link to keep track of the position in the tree just before the spot
     where the insertion will take place...The search will continue as long as the insertion key
     value is less than or greater than the value in the 'q' pointer. The new value will be inserted
     as a 'leaf' in the tree at the spot where there is no 'branch' attached to the insertion node
     (the node then will be equal to the tail which is the signal to insert the new value ... to
     understand how this works you might try diagraming a very simply tree and then stepping
     through the code to see what happens graphically... It will be neccesary to have the
     address of the preceding link stored in 'st' so that it can then be adjusted to point to the
     inserted link}

     begin
     repeat
        st:=q;
        if fname<q^.filename then q:=q^.l else q:=q^.r;

     {traverse the tree left (if the new value is less than current key in the tree, or right until it is
     greater until a 'dead end' is reached}

     until q=tail; {'dead end' virtual null pointer}
     new(q); q^.filename:=fname; {create a new node, insert key}
     q^.l:=tail; q^.r:=tail;

     {since the new key is inserted as a 'dead end' or 'leaf' node, set both pointers on the new
     node to point to 'tail'}

     if fname<st^.filename then st^.l:=q else st^.r:=q; 

     {when 'q' became equal to 'tail' this is a signal that the previously stored pointer address
     in 'st' must be set to point to 'q' which takes the place in that position previously occupied
     by 'tail' - all new leaf nodes have their pointers set to 'tail' ... therefore one of the links of
     this stored previous value must now be set to point to this new 'q' node so that it becomes
     attached as a leaf on the tree ... if the value in 'q' is less than the value (filename) in this
     previously stored st pointer node then it is attached to the left pointer of 'st' (keep in mind
     that 'st' was previously pointing at 'tail' or nothing, and vice versa if the value is greater...}

     TreeInsert:=q;

     {return the pointer to the address of the new node so that the 'modified date' can be
     inserted next to the filename in the correct spot on the tree...}

     end;




     procedure TForm1.TreePrintClick(Sender: TObject);
     var fs:textfile; begin
     AssignFile(fs, 'c:\treeprint.txt');
     Rewrite(fs);
     PrintTree(head);
     CloseFile(fs);
     MessageDlg('TREE PRINT DUN!', mtInformation, [mbOk], 0);
     end;


     Procedure Tform1.PrintTree(q:link); {pass the 'head' pointer}
     begin
     if q<>tail then begin 

     {when the recursive calls finally hit a 'dead end' (the tail) the stacked up calls will begin
     returning and depending on whether or not they were called from the left or the right they
     will on returning hit the appropriate print statement}

     PrintTree(q^.l);
     Writeln(fs, q^.filename);
     PrintTree(q^.r);
     end; {end if}
     end;