1

首先我写了这张唱片：

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

1 回答 1

9

我不明白您为什么要制作 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;
于 2013-08-17T19:08:15.233 回答