二进制搜索树插入代码意外行为

Question

我正在向二叉搜索树中插入一个节点，但遇到了意外行为。

我的问题是 - 为什么 insert 函数中的最后一行是可选的？最后一行处理递归情况，它应该是强制性的，但是当我运行没有最后一行时它也可以工作。

It works 意味着，它成功地向 BST 中插入了一个节点。

#include<stdio.h>
#include<stdlib.h>

struct node {
    int data;
    struct node *left;
    struct node *right;

};

typedef struct node Node;


struct node *insert(Node *root, int val)
{

    if(root == NULL){
   
        struct node *root = malloc(sizeof(struct node));
        root->data   = val;
        root->left  = root->right = NULL;
        return root;
    }
   
    if(root->data < val)
        root->right = insert(root->right,val);
   
    else if(root->data > val)
        root->left = insert(root->left,val);
    
    //return root; //WHY THIS LINE IS OPTIONAL
}

int main(){
    
    Node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 5);
    root = insert(root, 1);
}

Answer 1

insert() 中的最后一行是非常可选的，但前提是您愿意忍受未定义的行为。在您的特定情况下，UB 似乎可以正常工作，这肯定是 UB 的一种可能性。

事实上，这是它更隐蔽的功能之一，因为看似正确的行为可能会导致您的错误代码被释放给毫无戒心的可怜用户:-)

例如，由于函数调用导致堆栈上下移动，可能只是 root 的先前值被 returned，因为您没有加载新的它的价值。而且，如果新值与堆栈中已有的值相同，它可能看起来有效。

但是，它在一种特定情况下有效的事实不使依赖它成为一个好主意。

进一步扩展任意值，考虑以下代码：

#include<stdio.h>

int get42(void) { return 42; }
int getX(void) {}

int main(){
    int x = get42();
    //printf("123456789\n");
    int y = getX();
    printf("%d\n", x);
    printf("%d\n", y);
}

请记住这是 UB，因此对您来说可能会有所不同，这对我来说是：

prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
    4 | int getX(void) {}
      |                 ^
42
42

所以尽管有警告，它似乎给出了与之前的函数调用相同的值。您可以通过取消注释 printf() 并查看：

来验证这一点

prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
    4 | int getX(void) {}
      |                 ^
123456789
42
10

10 有来自 printf 调用的 return 值（它 return 打印的字符数，九位数字和 \n ).

因此，在这种情况下，跳过 return 语句似乎只会让调用者从上一次调用中获取堆栈中的任何内容（或者一些任意值，如果这是首先调用那个深度），例如：

#include<stdio.h>

int get42(void) { return 42; }
int getX(void) {}

int main(){
    int x = 42;//get42();
    //printf("123456789\n");
    int y = getX();
    printf("%d\n", x);
    printf("%d\n", y);
}

为我制作：

prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
    4 | int getX(void) {}
      |                 ^
42
-1539029341

但是，如前所述，不要依赖于此。当您切换到新编译器、新编译器版本、新机器，甚至决定在星期六而不是工作日编译它时，行为可能会发生变化:-)

二进制搜索树插入代码意外行为

Binary Search Tree insertion Code UNEXPECTED behavior

c

tree

binary-tree

binary-search-tree

data-structures