2

我正在阅读一些关于 AVL 树的示例源代码，部分实现是以下函数：

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

在 main 函数中，它的使用如下：

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

这看起来像 c 风格ctor和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的对称方式。通知 MakeEmpty( NULL );返回 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 回答
1

这是我对代码的理解：

“MakeEmpty函数的目的是什么？我知道它是一个递归函数，但我不明白它的目的。”

在 int main() 中，基本上你正在创建一个 AvlTree 对象。MakeEmpty 传递 Null 的原因是因为您想要一个空的树节点，其左右子节点未定义。

湾。为什么它被传递为null？Null 终止递归，因为这个想法是创建一个空树，其中未定义的子节点传入 Null 将创建“emtpy 对象”。

据我所知，基本上这整段代码正在创建一个空的 AvlTree。HTH。谢谢。

于 2013-03-29T19:37:49.880 回答
1

a）它正在清空树 - 即释放所有节点

b) 因为它是一个递归函数，所以它会在到达叶子时传递 null，尽管它可以在下一次递归调用之前轻松检查 null

于 2013-03-29T19:40:30.463 回答