Binary tree implementation in Delphi

Question

First i Wrote this record :

type
  PNode = ^Tree;
  Tree = record
  key : Integer;
  left,right : PNode;
end;

function TForm1.TreeInit(key: Integer): PNode;
var
  Head : PNode;
begin

Head := nil;
New(Head);

Head.key   := key;
Head.right := nil;
Head.left  := nil;

Result := Head;
end;

and everything was OK . then i added Parent to Structure :

type
  PNode = ^Tree;
  Tree = record
  key : Integer;
  left,right : PNode;
  parent     : PNode;
end;

and now i don't know how & where can i initialize parent ( especially in Insert Function ) ?

insert function :

function TForm1.NodeInsert(Head: PNode; key: Integer): PNode;
begin

if Head = nil then
begin
Result := TreeInit(key);
end else
begin

if (Head.key > key) then
  Head.left := NodeInsert(Head.left, key)
else
  Head.right := NodeInsert(Head.right,key);

Result := Head;

end;

end;

I've improved readability by fixing the code indentation. Please next time use some code formatting tools to do that. — OnTheFly
– OnTheFly, Commented Aug 17, 2013 at 16:56

David Heffernan · Accepted Answer · 2013-08-17 19:39:53Z

I don't see why you are making these methods of a GUI form because they have nothing to do with GUI. These should be standalone procedures.

The initialisation function could be written simply like this:

function NewNode(key: Integer; parent: PNode): PNode;
begin
  New(Result); 
  Result.key := key; 
  Result.right := nil;
  Result.left  := nil;
  Result.parent := parent;
end;

As for the insertion, that would normally be done like this:

procedure InsertNode(node: PNode: key: Integer);
begin
  if key < node.key then
    if Assigned(node.left) then
      InsertNode(node.left, key)
    else
      node.left := NewNode(key, node)
  else
    if Assigned(node.right) then
      InsertNode(node.right, key)
    else
      node.right := NewNode(key, node)
end;

This code assumes that the tree is non-empty. So, you'll need an outer layer that detects that the head node pointer is nil, and initialises it. Perhaps like this:

procedure Add(var head: PNode; key: Integer);
begin
  if Assigned(head) then
    InsertNode(head, key)
  else
    head := NewNode(key, nil)
end;

If you want to avoid recursion that's easy enough:

procedure InsertNode(node: PNode: key: Integer);
begin
  while True do
     if key < node.key then
       if Assigned(node.left) then
         node := node.left
      else 
      begin
        node.left := NewNode(key, node);
        exit;
      end
    else
      if Assigned(node.right) then
        node := node.right
      else
      begin
        node.right := NewNode(key, node);
        exit;
      end
end;

And then it's easy to merge in the separate Add function.

procedure InsertNode(var head: PNode: key: Integer);
var
  node: PNode;
begin
  if not Assigned(head) then
  begin
    head := NewNode(key, nil);
    exit;
  end;

  node := head;
  while True do
     if key < node.key then
       if Assigned(node.left) then
         node := node.left
      else 
      begin
        node.left := NewNode(key, node);
        exit;
      end
    else
      if Assigned(node.right) then
        node := node.right
      else
      begin
        node.right := NewNode(key, node);
        exit;
      end
end;

Collectives™ on Stack Overflow

Binary tree implementation in Delphi

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related