unit Trav1F;
//*******************************************************
// Example program demonstrating tree traversal for
// complete binary trees.
//*******************************************************
// Copyright (C) 1998 John Wiley & Sons, Inc.
// All rights reserved. See additional copyright
// information in Readme.txt.
//*******************************************************

interface

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

type
    // The complete tree is stored in an integer array.
    TIntArray = array [0..100000000] of Integer;
    PIntArray = ^TIntArray;

  TTrav1Form = class(TForm)
    MainMenu1: TMainMenu;
    File1: TMenuItem;
    mnuExit: TMenuItem;
    Help1: TMenuItem;
    mnuAbout: TMenuItem;
    CmdCreate: TButton;
    CmdPreorder: TButton;
    Label1: TLabel;
    HeightText: TEdit;
    CmdInorder: TButton;
    CmdPostorder: TButton;
    CmdBreadthFirst: TButton;
    ResultLabel: TLabel;
    procedure mnuExitClick(Sender: TObject);
    procedure mnuAboutClick(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure FormPaint(Sender: TObject);
    procedure DrawNode(node, x1, x2, y : Integer);
    procedure HeightTextChange(Sender: TObject);
    procedure CmdCreateClick(Sender: TObject);
    procedure CmdPreorderClick(Sender: TObject);
    procedure CmdInorderClick(Sender: TObject);
    procedure CmdPostorderClick(Sender: TObject);
    procedure CmdBreadthFirstClick(Sender: TObject);
    function PreorderTraverse(node : Integer) : String;
    function InorderTraverse(node : Integer) : String;
    function PostorderTraverse(node : Integer) : String;
    function BreadthFirstTraverse : String;
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Trav1Form: TTrav1Form;

implementation

const
    WID = 25;
    HGT = 16;
    HGAP = 2;
    VGAP = 6;

var
    tree      : PIntArray;
    num_nodes : Integer;

{$R *.DFM}

procedure TTrav1Form.mnuExitClick(Sender: TObject);
begin
    Close;
end;

procedure TTrav1Form.mnuAboutClick(Sender: TObject);
const
    CRCR = #13#10#13#10;
begin
    MessageDlg(
        'This program demonstrates different traversal orders for a full, complete binary tree.' + CRCR +
        'Enter the tree''s height and click the Create Tree button. Then click one of the traversal buttons to display the tree''s nodes in different traversal orders.'
        , mtInformation, [mbOK], 0);
end;

// Create the root node.
procedure TTrav1Form.FormCreate(Sender: TObject);
begin
    // Create a one node tree.
    CmdCreateClick(Sender);
end;

// Draw the tree.
procedure TTrav1Form.FormPaint(Sender: TObject);
var
    rect      : TRect;
    x1, x2, y : Integer;
begin
    // Erase the canvas.
    rect.Left := 0;
    rect.Right := Width;
    rect.Top := 0;
    rect.Bottom := Height;
    Canvas.Brush.Color := clLtGray;
    Canvas.FillRect(rect);

    // Draw the tree.
    x1 := CmdCreate.Left + CmdCreate.Width + HGAP;
    x2 := x1 + ((num_nodes + 1) div 2) * (WID + HGAP) - HGAP;
    y := HeightText.Top;
    DrawNode(0, x1, x2, y);
end;

// Recursively draw this node and its children.
procedure TTrav1Form.DrawNode(node, x1, x2, y : Integer);
var
    xmid, ymid, y2, child, childx : Integer;
    txt_size                      : TSize;
    txt                           : String;
begin
    // Draw a box for the node.
    xmid := (x1 + x2) div 2;
    Canvas.Rectangle(
        xmid - WID div 2, y, xmid + WID div 2, y + HGT);

    // Draw the label.
    txt := IntToStr(tree^[node]);
    txt_size := Canvas.TextExtent(txt);
    ymid := y + HGT div 2;
    Canvas.TextOut(
        xmid - (txt_size.cx div 2),
        ymid - (txt_size.cy div 2),
        txt);

    // If the node has no children, we're done.
    child := 2 * node + 1;
    if (child >= num_nodes) then exit;

    // Draw lines to the node's children.
    y := y + HGT;
    y2 := y + VGAP;

    // Draw a line to the first child.
    childx := (x1 + (xmid - HGAP div 2)) div 2;
    Canvas.MoveTo(xmid, y);
    Canvas.LineTo(childx, y2);

    // Recursively draw the first child.
    DrawNode(child, x1, (xmid - HGAP div 2), y2);

    // If the node has no second child, we're done.
    child := child + 1;
    if (child >= num_nodes) then exit;

    // Draw a line to the second child.
    childx := (x2 + (xmid + HGAP div 2)) div 2;
    Canvas.MoveTo(xmid, y);
    Canvas.LineTo(childx, y2);

    // Recursively draw the second child.
    DrawNode(child, (xmid + HGAP div 2), x2, y2);
end;

// Disable the traversal buttons.
procedure TTrav1Form.HeightTextChange(Sender: TObject);
begin
    CmdCreate.Enabled := True;
    CmdPreorder.Enabled := False;
    CmdInorder.Enabled := False;
    CmdPostorder.Enabled := False;
    CmdBreadthFirst.Enabled := False;
end;

// Create the complete binary tree.
procedure TTrav1Form.CmdCreateClick(Sender: TObject);
var
    i : Integer;
begin
    // Free the old tree memory.
    if (num_nodes > 0) then FreeMem(tree);

    // Allocate new tree memory.
    num_nodes := Round(IntPower(2, StrToInt(HeightText.Text)) - 1);
    GetMem(tree, num_nodes * SizeOf(Integer));

    // Fill in node values.
    for i := 0 to num_nodes - 1 do tree^[i] := i;

    Refresh;

    // Enabled the traversal buttons.
    CmdCreate.Enabled := False;
    CmdPreorder.Enabled := True;
    CmdInorder.Enabled := True;
    CmdPostorder.Enabled := True;
    CmdBreadthFirst.Enabled := True;
end;

// Display the preorder traversal.
procedure TTrav1Form.CmdPreorderClick(Sender: TObject);
begin
    ResultLabel.Caption := PreorderTraverse(0);
end;

// Display the inorder traversal.
procedure TTrav1Form.CmdInorderClick(Sender: TObject);
begin
    ResultLabel.Caption := InorderTraverse(0);
end;

// Display the postorder traversal.
procedure TTrav1Form.CmdPostorderClick(Sender: TObject);
begin
    ResultLabel.Caption := PostorderTraverse(0);
end;

// Display the breadth first traversal.
procedure TTrav1Form.CmdBreadthFirstClick(Sender: TObject);
begin
    ResultLabel.Caption := BreadthFirstTraverse;
end;

// Perform a preorder traversal of the tree.
function TTrav1Form.PreorderTraverse(node : Integer) : String;
begin
    Result := '';
    Result := Result + ' ' + IntToStr(tree^[node]);
    if (2 * node + 1 < num_nodes) then
        Result := Result + PreorderTraverse(2 * node + 1);
    if (2 * node + 2 < num_nodes) then
        Result := Result + PreorderTraverse(2 * node + 2);
end;

// Perform an inorder traversal of the tree.
function TTrav1Form.InorderTraverse(node : Integer) : String;
begin
    Result := '';
    if (2 * node + 1 < num_nodes) then
        Result := Result + InorderTraverse(2 * node + 1);
    Result := Result + ' ' + IntToStr(tree^[node]);
    if (2 * node + 2 < num_nodes) then
        Result := Result + InorderTraverse(2 * node + 2);
end;

// Perform a postorder traversal of the tree.
function TTrav1Form.PostorderTraverse(node : Integer) : String;
begin
    Result := '';
    if (2 * node + 1 < num_nodes) then
        Result := Result + PostorderTraverse(2 * node + 1);
    if (2 * node + 2 < num_nodes) then
        Result := Result + PostorderTraverse(2 * node + 2);
    Result := Result + ' ' + IntToStr(tree^[node]);
end;

// Perform a breadth first traversal of the tree.
function TTrav1Form.BreadthFirstTraverse : String;
var
    node : Integer;
begin
    Result := '';
    for node := 0 to num_nodes - 1 do
        Result := Result + ' ' + IntToStr(tree^[node]);
end;

end.
