C语言实现二叉搜索树时插入节点无法正确分支的问题

问题描述 #

用C语言实现二叉搜索树时，无法正确生成节点分支。插入新节点时，并未将节点挂载到空分支完成层级扩展，而是始终修改根节点的左右子节点，所有新节点都只在高度为2的位置替换，问题出在代码第85行的addvalue函数中。

错误输出 #

Enter the data of first node: 10
Enter the data of node: 7
 7
 L
10
Do you want to continue: 1
Enter the data of node: 6
6 
L
10
Do you want to continue: 1
Enter the data of node: 11
 11
 R
 10
 Do you want to continue: 0

期望执行流程 #

head node=10
first node=7
L
temp=10  
second node=6
L
L
temp=7
Third node=11
R
Temp=10

问题代码 #

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

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

void createtrees();
void treversetrees();
void addvalue(struct node *temp,struct node *NewNode);
void searchtree(int S,struct node *temp);

void main()
{
    int S;
    createtrees();
    printf("\nData in Trees is\n");
    //treversetrees();
    printf("Enter the integer to search for: ");
    scanf("%d",&S);
    struct node *temp;
    temp=head;
    searchtree(S,temp);
}

void createtrees()
{
    struct node *NewNode,*temp;
    int data,answer=1;
    head=(struct node*)malloc(sizeof(struct node));
    
    if (head==NULL)
    {
        printf("Unable to allocate memory.");
        exit(0);
    }
    
    printf("Enter the data of first node: ");
    scanf("%d",&data);
    
    head->data=data;

    do
    {
        NewNode=(struct node*)malloc(sizeof(struct node));
        if (NewNode==NULL)
        {
            printf("Unable to allocate memory.");
            break;
        }
        printf("Enter the data of node: ");
        scanf("%d",&data);
        printf("\n1. %d\n",data);
        
        NewNode->data=data;
        temp=head;
        
        if (data<temp->data)
        {
            addvalue(temp,NewNode);
        }
        else
        {
            addvalue(temp,NewNode);
        }
        printf("Do you want to continue: ");
        scanf("%d",&answer);
    }
    while(answer==1);
}

void addvalue(struct node *temp,struct node *NewNode)
{
    if (temp==NULL)
    {
        temp=NewNode;
    }
    else if (NewNode->data<temp->data)
    {
        printf("L\n");
        printf("\n%d\n",temp->data);
        addvalue(temp->left,NewNode);
    }
    else
    {
        printf("R\n");
        printf("\n%d\n",temp->data);
        addvalue(temp->right,NewNode);
    }
}

void searchtree(int S,struct node *temp)
{
    if (temp->data==S)
    {
        printf("%d is found in tree",S);
        return;
    }
    else if(temp->data>S)
    {
        temp=temp->right;
        searchtree(S,temp);
    }
    else if(temp->data<S)
    {
        temp=temp->left;
        searchtree(S,temp);
    }
    else if(temp==NULL)
    {
        printf("%d is not found in tree",S);
    }
    
}

错误原因及修复方案 #

核心错误 #

1. 值传递无法修改原指针：addvalue函数接收的是struct node*类型参数，属于值传递。执行temp=NewNode时仅修改函数内部临时指针，不会改变原树中父节点的left/right指针，导致新节点无法挂载到树上。
2. 节点指针未初始化：根节点和新创建的节点未将left/right初始化为NULL，导致空分支判断出现未定义行为。
3. 搜索函数逻辑顺序错误：searchtree先判断节点值再检查temp==NULL，会触发空指针访问崩溃。

修复后的代码 #

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

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

void createtrees();
void addvalue(struct node **temp, struct node *NewNode);
void searchtree(int S, struct node *temp);

int main()
{
    int S;
    createtrees();
    printf("\nEnter the integer to search for: ");
    scanf("%d",&S);
    searchtree(S, head);
    return 0;
}

void createtrees()
{
    struct node *NewNode;
    int data, answer=1;
    head=(struct node*)malloc(sizeof(struct node));
    
    if (head==NULL)
    {
        printf("Unable to allocate memory.");
        exit(0);
    }
    
    printf("Enter the data of first node: ");
    scanf("%d",&data);
    
    head->data = data;
    head->left = NULL;
    head->right = NULL;

    do
    {
        NewNode=(struct node*)malloc(sizeof(struct node));
        if (NewNode==NULL)
        {
            printf("Unable to allocate memory.");
            break;
        }
        printf("Enter the data of node: ");
        scanf("%d",&data);
        printf("\n%d\n",data);
        
        NewNode->data = data;
        NewNode->left = NULL;
        NewNode->right = NULL;
        
        addvalue(&head, NewNode);
        
        printf("Do you want to continue: ");
        scanf("%d",&answer);
    }
    while(answer==1);
}

void addvalue(struct node **temp, struct node *NewNode)
{
    if (*temp == NULL)
    {
        *temp = NewNode;
    }
    else if (NewNode->data < (*temp)->data)
    {
        printf("L\n");
        printf("当前节点: %d\n", (*temp)->data);
        addvalue(&((*temp)->left), NewNode);
    }
    else
    {
        printf("R\n");
        printf("当前节点: %d\n", (*temp)->data);
        addvalue(&((*temp)->right), NewNode);
    }
}

void searchtree(int S, struct node *temp)
{
    if (temp == NULL)
    {
        printf("%d is not found in tree", S);
        return;
    }
    if (temp->data == S)
    {
        printf("%d is found in tree", S);
        return;
    }
    else if (temp->data > S)
    {
        searchtree(S, temp->left);
    }
    else
    {
        searchtree(S, temp->right);
    }
}

修复说明 #

• 将addvalue参数改为双重指针，直接修改原树中的节点指针，实现新节点的正确挂载。
• 所有节点初始化left/right为NULL，确保空分支判断逻辑正确。
• 调整searchtree逻辑顺序，先检查节点是否为空，避免空指针访问。

内容的提问来源于stack exchange，提问作者TRUE LORD