1   with TEXT_IO ; use TEXT_IO ;
    2   procedure MAIN is  -- NOW, ADD AN  INSERT  PROCEDURE (data abstraction)
    3     type NODE ; -- just introduce type name
    4     type NODE_PTR is access NODE ; -- define an access type
    5                                    -- ie the type of a pointer
    6     type NODE is  -- now, really define the type NODE
    7       record
    8         BF    : INTEGER      ; -- balance factor for later use
    9         LEFT  : NODE_PTR     ; -- this records predecessor
   10         RIGHT : NODE_PTR     ; -- this records sucessor
   11         NAME  : STRING(1..2) ; -- data, the "sort" key
   12         PHONE : STRING(1..2) ; -- more tag along data
   13       end record ;
   14
   15     ROOT_PTR   : NODE_PTR := null ;   -- initially null
   16
   17     DEPTH : INTEGER := 1 ; -- indentation depth
   18
   19     procedure OUTPUT(T : NODE_PTR ) is
   20       procedure INDENT is
   21       begin
   22         for I in 1..DEPTH loop
   23           PUT("    ") ;
   24         end loop ;
   25       end INDENT ;
   26     begin
   27       DEPTH := DEPTH + 1 ;  -- count depth "down" upon entry
   28       if T /= null then
   29         OUTPUT(T.LEFT) ;
   30         INDENT ; PUT(T.NAME) ; PUT_LINE(T.PHONE) ;
   31         OUTPUT(T.RIGHT) ;
   32       end if ;
   33       DEPTH := DEPTH - 1 ;  -- count depth "up" upon exit
   34     end OUTPUT ;
   35
   36     procedure INSERT(T : in out NODE_PTR ; NAME,PHONE : STRING ) is
   37     begin
   38       if T = null then
   39         T := new NODE'(0, null, null, NAME, PHONE) ;
   40       else
   41         if NAME < T.NAME then
   42           INSERT(T.LEFT,NAME,PHONE) ;
   43         else
   44           INSERT(T.RIGHT,NAME,PHONE) ;
   45         end if ;
   46       end if ;
   47     end INSERT ;
   48
   49
   50   begin
   51     PUT_LINE(" TREE INSERTION AND PRINTOUT") ;







   52     -- build a tree using the INSERT procedure
   53     INSERT(ROOT_PTR,"D ","4 ") ; -- initial node at root
   54       -- first tier
   55       INSERT(ROOT_PTR,"B ","2 ") ;
   56         -- replaces  LEFT_PTR := new NODE'(0, null, null, "B ", "2 ") ;
   57       INSERT(ROOT_PTR,"F ","6 ") ;
   58
   59         -- second tier
   60         INSERT(ROOT_PTR,"A ","1 ") ;
   61         INSERT(ROOT_PTR,"C ","3 ") ;
   62         INSERT(ROOT_PTR,"E ","5 ") ;
   63         INSERT(ROOT_PTR,"G ","7 ") ;
   64
   65     OUTPUT(ROOT_PTR) ; -- look at tree produced. The order of the tree
   66                        -- build was carefully planned to get a balanced
   67                        -- binary tree
   68
   69   end MAIN ;

 TREE INSERTION AND PRINTOUT

                A 1 
            B 2 
                C 3 
        D 4 
                E 5 
            F 6 
                G 7