时间戳

首页 > 解决方案 > bst insert中第二条return root语句的意义是什么？

c++ - bst insert中第二条return root语句的意义是什么？

问题描述

在插入函数的以下代码中，在bst中插入一个项目我觉得没有使用第二个return语句，因为一个节点总是会添加在叶子节点之后。

struct node* insert(struct node* node, int key)
{
    if (node == NULL)
        return newNode(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    return node;
}

但是，当我删除此返回语句时，我会得到以下驱动程序代码的完全不同的输出

int main()
{
    struct node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    inorder(root);  // A utility function to do inorder traversal of BST
}

对于插入函数中带有第二个返回语句的插入函数，我得到

20 30 40 50 60 70 80

对于没有第二个返回语句的插入函数

40 50 80

这种差异的原因是什么？

以上代码取自https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

PS：我是新手，这是我在平台上的第一个问题。

标签： c++data-structuresbinary-search-tree

解决方案

到达非空函数的结尾，除了main()不执行return语句会调用未定义的行为。因此，没有第二return条语句的任何结果都是允许的。

N3337 6.6.3 返回声明说：

从函数的末尾流出相当于return没有值的 a；这会导致值返回函数中的未定义行为。

N3337 3.6.1 主要功能说：

如果控制到达末尾main没有遇到return语句，效果就是执行

return 0;

推荐阅读