-1

在这个视频（一个名为 CS50 的在线课程的部分/背诵）中，大约 1h00m00s，学生讲师进入指针到指针以及为什么以这种方式在二叉树上实现插入更有效 。至少，这是我从争论中得到的。

我以两种方式进行了递归实现。我不明白为什么选项 A 比下面的选项 B 更好......如果我被误解了，也许你可以帮我推理或指出正确的方向？

选项 A（带有指向指针的指针）

bool insert(int value, node* tree)
    {
        node** tmptree = &tree;
        // make sure the tree itself isn't null
        if(*tmptree != NULL)
        {
            if(value == (*tmptree)->value)
            {
                return false;
            }
            else if(value < (*tmptree)->value)
            {
                tmptree = &(*tmptree)->left;
                // we must be at a null leaf!
                if(*tmptree == NULL)
                {
                    // make sure we built a leaf
                    *tmptree = build_node(value);
                    if(*tmptree == NULL)
                    {
                        return false;
                    }
                    return true;
                }
                else
                {
                    return insert(value, *tmptree);
                }
            }
            else
            {
                tmptree = &(*tmptree)->right;
                if(*tmptree == NULL)
                {
                    *tmptree = build_node(value);
                    if(*tmptree == NULL)
                    {
                        return false;
                    }
                    return true;
                }
                else
                {
                    return insert(value, *tmptree);
                }
            }
        }
        return false; // if the tree is null
    }

选项 B（常规 ptrs）

    bool insert(int value, node* tree)
    {
        if(tree != NULL)
        {
            if(value == tree->value)
            {
                return false;
            }
            else if(value < tree->value)
            {
                if(tree->left == NULL)
                {
                    node* tmp = build_node(value);
                    if(tmp != NULL)
                    {
                        tree->left = tmp;
                        return true;
                    }
                    return false;
                }
                else
                {
                    return insert(value, tree->left);
                }
            }
            else
            {
                if(tree->right == NULL)
                {
                    node* tmp = build_node(value);
                    if(tmp != NULL)
                    {
                        tree->right = tmp;
                        return true;
                    }
                    return false;
                }
                else
                {
                    return insert(value, tree->right);
                }
            }
        }
        return false; // if the tree is null
    }

build_node 函数：

    node* build_node(int value)
    {
        node* node = malloc(sizeof( node ));
        if(node == NULL)
            return NULL;
        node->value = value;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
4

1 回答 1

1

我相信你误解了为什么原始代码中有一个指向指针的指针。“选项 a”没有任何意义，仅仅为了它而使用指针对指针没有任何好处。

您使用指针到指针的唯一原因是您想要更改指向的地址并将其返回给调用者。

例如

void func (int** ptr)
{
  *ptr = something;
}

func(&my_ptr);

// is the very thing same as

int* func (int* ptr)
{
  return something;
}

my_ptr = func(my_ptr);

您不能使用第二个版本并ptr = something在函数内键入，因为ptr它是一个局部变量，一旦您离开函数，它将不复存在。为其分配某些内容不会影响调用方的原始指针。

指针对指针版本的唯一优点是返回的类型可以用于其他用途，例如返回错误代码。

这似乎正是那个视频中的那个人使用它的原因。他的功能看起来像

bool insert (int value, node** tree);

其中，*tree分配给函数内部的另一个地址，当他到达树枝的末端时，布尔值用作状态码。

于 2013-12-19T07:25:31.747 回答