c - 在 C 中使用递归插入二叉搜索树

Question

我正在编写一个程序来制作一个二叉搜索树，它接受用户的输入。 我在下面的代码中特意展示了两个搜索函数。

问题:search function2 正常工作，但search function1 不能正常工作(每次评论对方后使用时)。 为什么会这样？

我尝试进行空运行并构建递归堆栈，这对我来说效果很好。但不知何故，我认为 search function 1 无法在链表中建立链接以插入元素。这就是我在尝试执行 inorder traversal

时无法获得正确输出的原因

非常感谢任何帮助!

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

struct node{
    int data;
    struct node *left;
    struct node *right;
};
struct node *root = NULL;

struct node *newNode(int data){
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

//SEARCH FUNCTION 1: this does not work correctly
void search(struct node *t,int data){
    if(t){
        if(data > t->data){
            search(t->right,data);
        }else{
            search(t->left,data);
        }
    }else{
        t = newNode(data);
    }
}

//SEARCH FUNCTION 2: this works fine and inserts the element correctly
void search(struct node *t, int data){
    if(data < t->data && t->left != NULL){
        search(t->left, data);
    }else if(data < t->data && t->left == NULL){
        t->left = newNode(data);
    }else if(data > t->data && t->right != NULL){
        search(t->right,data);
    }else{
        t->right = newNode(data);
    }
}

void insertNode(int data){
    if(!root){
        root = newNode(data);
        return;
    }
    search(root, data);
}

void inorder(struct node *t){
    if(t){
        if(t->left){
            inorder(t->left);   
        }
        printf("%d ->", t->data);
        if(t->right){
            inorder(t->right);  
        }
    }
}

int main(){
    int step, data;
    while(1){
        printf("1. Insert element\n");
        printf("2. Print tree\n");
        scanf("%d",&step);
        switch(step){
            case 1: printf("enter element to be inserted\n");
                scanf("%d",&data);
                insertNode(data);
                break;
            case 2:inorder(root); 
                printf("\n");
                break;
        }
    }
    return 0;
}

Answer 1

问题是 t = newNode(data) 赋值给了一个局部变量，所以函数返回后结果立即丢失。

在这种情况下，一种解决方案是双重间接寻址，因为您不仅要修改指针指向的内容，还要修改指针本身。

void search(struct node **pt,int data)
{
    struct node *t = *pt;
    if (t) {
        if (data > t->data) {
            search(&t->right,data);
        } else {
            search(&t->left,data);
        }
    } else {
        *pt = newNode(data);
    }
}