unit IterTree;
//*******************************************************
// Complete binary tree class plus its iterator classes.
//*******************************************************
// Copyright (C) 1998 John Wiley & Sons, Inc.
// All rights reserved. See additional copyright
// information in Readme.txt.
//*******************************************************

interface

uses
    Windows, Graphics, Math, SysUtils;

type
    TIteratorType = (itPreorder, itInorder, itPostorder,
        itBreadthFirst);

    TIterator = class;
    TPreorderIterator = class;
    TInorderIterator = class;
    TPostorderIterator = class;
    TBreadthFirstIterator = class;

    // Complete binary tree class.
    TCompleteTree = class(TObject)
        private
            Nodes    : array [1..1000] of Integer;
            NumNodes : Integer;

        public
            procedure MakeTree(hgt : Integer);
            procedure Draw(cvs : TCanvas; x, y, xmax, ymax : Integer);
            procedure DrawNode(cvs : TCanvas; node, x1, x2, y : Integer);
            function InTree(index : Integer) : Boolean;
            function NodeValue(index : Integer) : Integer;
            function CreateIterator(it_type : TIteratorType) : TIterator;
    end;

    // Iterator base class.
    TIterator = class(TObject)
        protected
            TheTree      : TCompleteTree;
            CurrentIndex : Integer;
            NodeIndexes : array[0..1000] of Integer;

            procedure OrderNodes; virtual; abstract;

        public
            constructor Create(tree : TCompleteTree);
            function EndOfTree : Boolean;
            procedure MoveNext;
            function CurrentNode : Integer;
    end;

    // Preorder tree iterator.
    TPreorderIterator = class(TIterator)
        protected
            procedure OrderNodes; override;

        private
            procedure AddNodeToList(var index : Integer; node : Integer);
    end;

    // Inorder tree iterator.
    TInorderIterator = class(TIterator)
        protected
            procedure OrderNodes; override;

        private
            procedure AddNodeToList(var index : Integer; node : Integer);
    end;

    // Postorder tree iterator.
    TPostorderIterator = class(TIterator)
        protected
            procedure OrderNodes; override;

        private
            procedure AddNodeToList(var index : Integer; node : Integer);
    end;

    // Breadth first tree iterator.
    TBreadthFirstIterator = class(TIterator)
        protected
            procedure OrderNodes; override;
    end;

implementation

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

// -------------------------------------------------------
// TCompleteTree
// -------------------------------------------------------
// Make a tree of the indicated size.
procedure TCompleteTree.MakeTree(hgt : Integer);
var
    i : Integer;
begin
    NumNodes := Round(IntPower(2, hgt) - 1);

    // Fill in node values.
    for i := 0 to NumNodes - 1 do Nodes[i] := i;
end;

// Draw the tree on the canvas.
procedure TCompleteTree.Draw(cvs : TCanvas; x, y, xmax, ymax : Integer);
var
    rect   : TRect;
    x1, x2 : Integer;
begin
    // Erase the canvas.
    rect.Left := 0;
    rect.Right := xmax;
    rect.Top := 0;
    rect.Bottom := ymax;
    cvs.Brush.Color := clSilver;
    cvs.FillRect(rect);

    // Draw the tree.
    x1 := x + HGAP;
    x2 := x1 + ((NumNodes + 1) div 2) * (WID + HGAP) - HGAP;
    DrawNode(cvs, 0, x1, x2, y);
end;

// Recursively draw this node and its children.
procedure TCompleteTree.DrawNode(cvs : TCanvas; 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;
    cvs.Rectangle(xmid - WID div 2, y,
        xmid + WID div 2, y + HGT);

    // Draw the label.
    txt := IntToStr(Nodes[node]);
    txt_size := cvs.TextExtent(txt);
    ymid := y + HGT div 2;
    cvs.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 >= NumNodes) 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;
    cvs.MoveTo(xmid, y);
    cvs.LineTo(childx, y2);

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

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

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

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

// Return True if the node is in the tree.
function TCompleteTree.InTree(index : Integer) : Boolean;
begin
    Result := ((index >= 0) and (index < NumNodes));
end;

// Return the value of the indeicated node.
function TCompleteTree.NodeValue(index : Integer) : Integer;
begin
    Result := Nodes[index];
end;

// This factory method creates and returns an
// appropriate iterator.
function TCompleteTree.CreateIterator(it_type : TIteratorType) : TIterator;
begin
    case (it_type) of
        itPreorder:
            Result := TPreorderIterator.Create(Self);
        itInorder:
            Result := TInorderIterator.Create(Self);
        itPostorder:
            Result := TPostorderIterator.Create(Self);
        itBreadthFirst:
            Result := TBreadthFirstIterator.Create(Self);
    else
            Result := nil;
    end;
end;

// -------------------------------------------------------
// TIterator
// -------------------------------------------------------
// Save the tree and order its nodes for the traversal.
constructor TIterator.Create(tree : TCompleteTree);
begin
    inherited Create;
    TheTree := tree;
    OrderNodes;
    CurrentIndex := 0;
end;

// Return True if we're past the end of the tree.
function TIterator.EndOfTree : Boolean;
begin
    Result := (not TheTree.InTree(CurrentIndex));
end;

// Move to the next node.
procedure TIterator.MoveNext;
begin
    if (TheTree.InTree(CurrentIndex)) then
        CurrentIndex := CurrentIndex + 1;
end;

// Return the index of the current node.
function TIterator.CurrentNode : Integer;
begin
    Result := TheTree.NodeValue(NodeIndexes[CurrentIndex]);
end;

// -------------------------------------------------------
// TPreorderIterator
// -------------------------------------------------------
// Order the tree's nodes for traversal.
procedure TPreorderIterator.OrderNodes;
var
    index : Integer;
begin
    index := 0;
    AddNodeToList(index, 0);
end;

procedure TPreorderIterator.AddNodeToList(var index : Integer; node : Integer);
var
    child : Integer;
begin
    // Visit the node.
    NodeIndexes[index] := node;
    index := index + 1;

    // Recursively visit the left child.
    child := 2 * node + 1;
    if (TheTree.InTree(child)) then
        AddNodeToList(index, child);

    // Recursively visit the right child.
    child := child + 1;
    if (TheTree.InTree(child)) then
        AddNodeToList(index, child);
end;

// -------------------------------------------------------
// TInorderIterator
// -------------------------------------------------------
// Order the tree's nodes for traversal.
procedure TInorderIterator.OrderNodes;
var
    index : Integer;
begin
    index := 0;
    AddNodeToList(index, 0);
end;

procedure TInorderIterator.AddNodeToList(var index : Integer; node : Integer);
var
    child : Integer;
begin
    // Recursively visit the left child.
    child := 2 * node + 1;
    if (TheTree.InTree(child)) then
        AddNodeToList(index, child);

    // Visit the node.
    NodeIndexes[index] := node;
    index := index + 1;

    // Recursively visit the right child.
    child := child + 1;
    if (TheTree.InTree(child)) then
        AddNodeToList(index, child);
end;

// -------------------------------------------------------
// TPostorderIterator
// -------------------------------------------------------
// Order the tree's nodes for traversal.
procedure TPostorderIterator.OrderNodes;
var
    index : Integer;
begin
    index := 0;
    AddNodeToList(index, 0);
end;

procedure TPostorderIterator.AddNodeToList(var index : Integer; node : Integer);
var
    child : Integer;
begin
    // Recursively visit the left child.
    child := 2 * node + 1;
    if (TheTree.InTree(child)) then
        AddNodeToList(index, child);

    // Recursively visit the right child.
    child := child + 1;
    if (TheTree.InTree(child)) then
        AddNodeToList(index, child);

    // Visit the node.
    NodeIndexes[index] := node;
    index := index + 1;
end;

// -------------------------------------------------------
// TBreadthFirstIterator
// -------------------------------------------------------
// Order the tree's nodes for traversal. For complete
// trees the breadth first traversal is the same as the
// tree's natural ordering.
procedure TBreadthFirstIterator.OrderNodes;
var
    i : Integer;
begin
    i := 0;
    while (TheTree.InTree(i)) do
    begin
        NodeIndexes[i] := i;
        i := i + 1;
    end;
end;

end.
