delphi - 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;

此代码假定树为非空。因此，您需要一个外层来检测头节点指针为nil并将其初始化。也许像这样：

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;