Question

How to parse a table into a binary tree in Pascal

Answer 1

program ParseTableToBinaryTree;

{$mode objfpc}{$H+}

uses
    SysUtils;

type
    PNode = ^TNode;
    TNode = record
        Id: Integer;
        Name: string;
        Left: PNode;   // first child
        Right: PNode;  // next sibling
    end;

    TRow = record
        Id: Integer;
        Name: string;
        ParentId: Integer;
    end;

{ -------------------- Print Tree -------------------- }

procedure PrintTree(Node: PNode; Depth: Integer);
var
    i: Integer;
begin
    if Node = nil then Exit;

    // show ROOT explicitly on its own line
    if Depth = 0 then
        WriteLn('ROOT');

    // indentation for the node itself
    for i := 0 to Depth do
        Write('  ');

    // print ID with leading zero if needed
    WriteLn(Format('%.2d - %s', [Node^.Id, Node^.Name]));

    // first child
    PrintTree(Node^.Left, Depth + 1);

    // next sibling (another top-level node)
    if (Depth = 0) and (Node^.Right <> nil) then
        PrintTree(Node^.Right, 0)
    else
        PrintTree(Node^.Right, Depth);
end;

{ -------------------- Build Tree -------------------- }

function BuildTree(const Table: array of TRow; Count: Integer;
                   var Nodes: array of PNode): PNode;
var
    i: Integer;
    Current, Parent, Root, P: PNode;
begin
    // create nodes
    for i := 0 to Count - 1 do
    begin
        New(Nodes[Table[i].Id]);
        Nodes[Table[i].Id]^.Id   := Table[i].Id;
        Nodes[Table[i].Id]^.Name := Table[i].Name;
        Nodes[Table[i].Id]^.Left := nil;
        Nodes[Table[i].Id]^.Right := nil;
    end;

    Root := nil;

    // attach children and siblings
    for i := 0 to Count - 1 do
    begin
        Current := Nodes[Table[i].Id];

        if Table[i].ParentId = 0 then
        begin
            if Root = nil then
                Root := Current
            else
            begin
                P := Root;
                while P^.Right <> nil do
                    P := P^.Right;
                P^.Right := Current;
            end;
        end
        else
        begin
            Parent := Nodes[Table[i].ParentId];

            if Parent^.Left = nil then
                Parent^.Left := Current
            else
            begin
                P := Parent^.Left;
                while P^.Right <> nil do
                    P := P^.Right;
                P^.Right := Current;
            end;
        end;
    end;

    Result := Root;
end;

{ -------------------- Main -------------------- }

var
    Table: array[0..11] of TRow;
    Nodes: array[0..100] of PNode;
    Root: PNode;
begin
    Table[0].Id := 1;  Table[0].Name := 'Node 1';        Table[0].ParentId := 0;
    Table[1].Id := 2;  Table[1].Name := 'Node 1.1';      Table[1].ParentId := 1;
    Table[2].Id := 3;  Table[2].Name := 'Node 2';        Table[2].ParentId := 0;
    Table[3].Id := 4;  Table[3].Name := 'Node 1.1.1';    Table[3].ParentId := 2;
    Table[4].Id := 5;  Table[4].Name := 'Node 2.1';      Table[4].ParentId := 3;
    Table[5].Id := 6;  Table[5].Name := 'Node 2.3.1';    Table[5].ParentId := 3;
    Table[6].Id := 7;  Table[6].Name := 'Node 1.2';      Table[6].ParentId := 1;
    Table[7].Id := 8;  Table[7].Name := 'Node 1.3';      Table[7].ParentId := 1;
    Table[8].Id := 9;  Table[8].Name := 'Node 1.3.1';    Table[8].ParentId := 8;
    Table[9].Id := 10; Table[9].Name := 'Node 2.4';      Table[9].ParentId := 3;
    Table[10].Id := 11;Table[10].Name := 'Node 2.1.1';   Table[10].ParentId := 5;
    Table[11].Id := 12;Table[11].Name := 'Node 2.1.1.6'; Table[11].ParentId := 11;

    FillChar(Nodes, SizeOf(Nodes), 0);

    Root := BuildTree(Table, Length(Table), Nodes);

    PrintTree(Root, 0);
end.



{
run:

ROOT
  01 - Node 1
    02 - Node 1.1
      04 - Node 1.1.1
    07 - Node 1.2
    08 - Node 1.3
      09 - Node 1.3.1
ROOT
  03 - Node 2
    05 - Node 2.1
      11 - Node 2.1.1
        12 - Node 2.1.1.6
    06 - Node 2.3.1
    10 - Node 2.4
}

 

70+ SQL courses for beginners and professionals