0

嗨，我正在学习帕斯卡并测试一些函数
，我做了一个这样的递归插入过程。如果节点存在比较两个键，如果不存在，则为新节点腾出空间。

procedure INSERT (KEY : integer; var NODE : NODEPTR);
begin 
    if NODE = Nil then  
    begin
        New (NODE); 
        NODE^.KEY := KEY; 
        NODE^.LEFT  := Nil;
        NODE^.RIGHT  := Nil
    end
    else            
        if KEY < NODE^.KEY then
            INSERT (KEY, NODE^.LEFT)
        else
            INSERT (KEY, NODE^.RIGHT)   
end;

我想要做的是将递归函数更改为while循环。所以我做了这样的过程，
如果节点存在做while循环，直到节点为空。在while循环结束后，创建一个新节点

procedure INSERT (KEY : integer; var NODE : NODEPTR);
begin 
    while NODE <> nil do
    begin
        if KEY < NODE^.KEY then
            NODE:=NODE^.LEFT
        else
            NODE:=NODE^.RIGHT
    end;

    New (NODE); 
    NODE^.KEY := KEY; 
    NODE^.LEFT  := Nil;
    NODE^.RIGHT  := Nil

end;

当第一个节点是根节点时，while 循环为 true 并执行此代码，但此后，while 循环变为 false 并创建一个新节点。

        if KEY < NODE^.KEY then
            NODE:=NODE^.LEFT
        else
            NODE:=NODE^.RIGHT

最终没有节点连接，这个程序只是不断地创建新节点。
有什么我错过的吗？或者关于第二个代码的任何即兴创作？提前致谢 ：）

4

1 回答 1

1

您错过的事情是您永远不会链接节点（并且在当前设置中，您实际上无法链接节点）。您的记录中有节点的左右节点的字段，但您没有分配它们。因此，您最终只是创建节点而没有将它们链接起来；您有一个缺少链接的链接列表。

在某一时刻，您将需要类似于NODE^.RIGHT := NEWNODE（或NODE^.LEFT := NEWNODE，当然）的东西。

你需要一些东西（我的 Pascal 有点生疏，所以要小心语法错误；））：

    procedure INSERT(key: Integer; var NODE: NODEPTR)
    begin
        NODEPTR root := NODE;
        if (key < root^.KEY) then begin
            while (root^.LEFT <> nil) do begin
                root := root^.LEFT;
            end;
            new(NODE);
            NODE^.KEY := key;
            root^.LEFT := NODE;
            node^.RIGHT := root;
        end else begin
            while (root^.Right <> nil) do begin
                root^ := root^.RIGHT;
            end;
            new(NODE);
            NODE^.KEY := key;
            root^.RIGHT := NODE;
            NODE^.LEFT := root;
        end;
    end;

上面的例子有很多改进和美化，但我认为它显示了总体思路。

于 2012-12-12T08:50:30.340 回答