0

こんにちは、私はパスカルを学んでおり、いくつかの機能
をテストしています。このような再帰的な挿入手順を作成しました。ノードが存在する場合は 2 つのキーを比較し、存在しない場合は新しいノード用のスペースを作ります。

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-loopに変更することです。
ノードが存在する場合は、ノードが空になるまで 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

最終的にノード接続がなくなり、このプログラムは新しいノードを作成し続けます。
私が逃したものはありますか？または2番目のコードについての即興？前もって感謝します ：）

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 に答える