2

私はAVLツリーでいくつかのサンプルソースコードを読んでおり、実装の一部は次の関数です:

AvlTree MakeEmpty( AvlTree T )
{
    if( T != NULL )
    {
        MakeEmpty( T->Left );
        MakeEmpty( T->Right );
        free( T );
    }
    return NULL;
}

メイン関数では、次のように使用されます。

int main()
{
    AvlTree T;

    T = MakeEmpty( NULL );

次に、メイン関数は AVL ツリーへの数値の挿入に移ります。私の主な質問は

a) MakeEmpty 関数の目的は何ですか? 再帰関数であることは理解していますが、その目的がわかりません。

b) この関数に NULL 値が渡されるのはなぜですか?

どうもありがとう！

また、AVLTree はこの構造体へのポインターです。

struct AvlNode
{
    ElementType Element;
    AvlTree  Left;
    AvlTree  Right;
    int      Height;
};
4

4 に答える 4

1

コードの私の理解は次のとおりです。

「MakeEmpty 関数の目的は何ですか? 再帰関数であることは理解していますが、目的がわかりません。」

int main() 内部では、基本的に AvlTree オブジェクトを作成しています。MakeEmpty が Null に渡される理由は、空のツリー ノードが必要であり、左右の子が未定義であるためです。

b. null が渡されるのはなぜですか? Null は再帰を終了し、定義されていない子ノードを持つ空のツリーを作成するだけであるため、Null を渡すと「空のオブジェクト」が作成されます。

基本的に、このコード全体は、私が知る限り、null AvlTree を作成しています。HTH。ありがとう。

于 2013-03-29T19:37:49.880 に答える
1

a）ツリーを空にしています-つまり、すべてのノードを解放しています

b) 再帰関数であるため、リーフに到達すると null を渡しますが、次の再帰呼び出しの前に null を簡単にチェックできます。

于 2013-03-29T19:40:30.463 に答える
1

ctorこれは c-styleとdtorforのように見えますAvlNode。

C++では、次のようなことができます

struct AvlNode
{
    ElementType Element;
    AvlTree  Left;
    AvlTree  Right;
    int      Height;

    AvlNode()
      : Left(NULL), Right(NULL), Height(0)
    {}

    ~AvlNode()
    { 
       // free node
    } 
};

しかし、C ではこれを行うことができませんでした。つまり、基本的には、MakeEmpty両方のポインターがランダムなアドレスを指しているのではなく、NULL.

于 2013-03-29T19:36:11.773 に答える
1

a) MakeEmpty 関数の目的は何ですか? 再帰関数であることは理解していますが、その目的がわかりません。

makeEmpty()その名前が示すように、ポストオーダーで移動しながら、すべてのノードのメモリを解放します。ポスト オーダー トラバーサーでは、一度ノードが処理されると再度参照されないことに注意してください。解放されたノードは再び参照されるべきではないため、free() すべてのノードのポスト オーダーは正しいものになります。

b) この関数に NULL 値が渡されるのはなぜですか?

T を NULLに初期化する対称的な方法です。null が送信されるため、 notice MakeEmpty( NULL );は null を返します。 

        T = MakeEmpty( NULL );
==      T = NULL

編集

MakeEmpty() はどのように機能しますか? （コメントを読む）

AvlTree MakeEmpty( AvlTree T )
{
    if( T != NULL )
    {
        MakeEmpty( T->Left );    // but in stack 
        MakeEmpty( T->Right );   // but in stack 
        free( T );               // free node
    }
    return NULL;    // if T is passed NULL then it returns NULL
}

(B) の場合、答えT = MakeEmpty( NULL );は NULL を返します。

于 2013-03-29T19:36:29.867 に答える