Delphi中的二叉树实现

Question

首先我写了这个记录：

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;

一切都很好。然后我将Parent添加到Structure:

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

现在我不知道如何&在哪里可以初始化父级（尤其是在插入函数中）？

插入功能：

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;

Answer 1

我不明白为什么要制作GUI表单的这些方法，因为它们与GUI无关。这些应该是独立的程序。

初始化功能可以简单地写成这样：

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

至于插入，通常会这样做：

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;

此代码假定树不是空的。因此，你需要一个外层来检测头节点指针为零，并对其进行初始化

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

如果你想避免递归，这很容易：

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;

然后可以很容易地在单独的Add函数中进行合并。

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;