关于函数的返回值问题，在用递归的形式书写二叉搜索树的查找时候的问题

Question

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

}

这是在二叉树中插入元素的代码，在这里省略了key所对应的value的值，此形式是递归写的。

如果现在，在一个空二叉树中开始插入元素，第一个插入10，第二个插入9。

则形成了靠左有两个元素的树，当我插入第三个元素8的时候。

node->left=insert(node->left,key);

还是需要向左插入，但是这行代码将会在递归过程中返回给第一个节点的左指针一个数值，但是并没有显示的写出来返回值是什么。

那么作指针将被赋予什么样的地址，但是实际运行时并未造成什么错误，这是为什么？此外我写了一个例子。

int *fun(int *root1,int *root2)

{

    if(*root1>*root2)

            return root1;

}

int *root=NULL,root1=10,root2=20;

 printf("%d     ",root);

fun(&root1,&root2);

printf("%d",root);          

在我的电脑上这两个输出的数值是不一样的。。。

Answer 1

liuyubobobo 2017-02-13 12:29:01

insert的正确代码见这里https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/03-Binary-Search-Tree-Insert/main.cpp

注意，insert要返回一个Node*，所以要保证对于每一种情况，都有返回值哦：）注意下面代码标粗的地方，尤其是最后一句：）

Node* insert(Node *node, Key key, Value value){    

  

    if( node == NULL ){    

        count ++;    

        return new Node(key, value);    

    }    

  

    if( key == node->key )    

        node->value = value;    

    else if( key < node->key )    

        node->left = insert( node->left , key, value);    

    else    // key > node->key    

        node->right = insert( node->right, key, value);    

    return node;    

}    

Answer 2

liuyubobobo 2017-02-13 00:25:44

这是因为C++编译器不做过多的安全检查，很多诸如数组越界，指针越界的问题，是需要开发着自己处理的。

举个最简单的例子，试试下面的代码：

int *a = new int[2];
a[100] = 42;

这个代码是明显错误的，但是编译器是不报任何错误的，执行也没有任何问题。但是，这是一个错误的代码！我们相当于将a+100这个地址的位置写成了42。当你的逻辑更复杂的时候，这句话就是一个隐患，很有可能会导致莫名的错误！虽然在编译和运行的时候都没有问题。

同理，在你的insert代码中，没有正确的返回node，此时我们无法预测代码的行为。即使不报错。因为C++不做这种错误检查。但是你的代码是错误的，是极度不安全的！此时我们分析这个没有返回值的函数到底返回了什么意义是不大的。是系统运行相关的，但不管怎样，都是错误的。

所以使用C++要小心。

• 提问者 笛梦少年 #1

  这段代码是我看你的视频中的代码，你的代码就是这样写的。如果执行了node->left=insert(node->left,key);这条语句那么这个函数将没有返回值。。。但是我要怎么修改呢。。。

• liuyubobobo 回复 提问者 笛梦少年 #2

  我的代码，insert的最后，要return node啊：）