为什么我的二叉搜索树的创建功能不起作用？

Question

创建函数应该询问用户他们想要输入多少个节点，然后一个一个地插入那么多元素。

我正在使用前序遍历函数检查二叉搜索树的创建

代码在输入部分运行良好，它要求用户输入数据，但是当它应该以预序遍历方式显示树时，它什么都不做并退出。

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

struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
};

void insert(struct Node* root, int x)
{
    if(root -> left == NULL && x < root -> data)
    {
        struct Node* new_node = (struct Node* )malloc(sizeof(struct Node));
        new_node -> data = x;
        new_node -> left = NULL;
        new_node -> right = NULL;
        root -> left = new_node;
    }
    else if(root -> right == NULL && x > root -> data)
    {
        struct Node* new_node = (struct Node* )malloc(sizeof(struct Node));
        new_node -> data = x;
        new_node -> left = NULL;
        new_node -> right = NULL;
        root -> right = new_node;
    }
    else
    {
        if(x < root -> data)
        {
            insert(root -> left, x);
        }
        else if(x > root -> data)
        {
            insert(root -> right, x);
        }
    }
}

void create(struct Node* root)
{
    root = (struct Node*)malloc(sizeof(struct Node));
    printf("\nHow many nodes do you want to create: ");
    int tree_size;
    scanf("%d", &tree_size);
    printf("\nEnter data for root node: ");
    int ent_data;
    scanf("%d", &ent_data);
    root -> data = ent_data;
    root -> left = NULL;
    root -> right = NULL;
    for(int i=1; i<tree_size; i++)
    {
        printf("\nEnter data for node: ");
        scanf("%d", &ent_data);
        insert(root, ent_data);
    }
}

void preOrderTraversal(struct Node *root)
{
    if(root != NULL)
    {
        printf("%d, ", root -> data);
        preOrderTraversal(root -> left);
        preOrderTraversal(root -> right);    
    }
}


int main()
{
    struct Node* root = NULL;
    create(root);
    
    preOrderTraversal(root);
    return 0;
}

Answer 1

问题是 create 不会修改主变量 root。 C 参数按值传递，因此您应该执行以下操作之一：

将root的地址传递给create函数，或者
根本不要将 root 作为参数传递，但让 create return 作为根指针。

第二个选项是首选，因为root不作为输入 create的值，而是作为输出.

与您的问题无关，但尽量避免代码重复。您的代码中有三个地方可以调用 malloc 并初始化一个节点。而是为此创建一个函数并在这三个地方调用它。

这里是修改后的代码：

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

struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to call whenever you need a node instance
struct Node * create_node(int x)
{
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node -> data = x;
    new_node -> left = NULL;
    new_node -> right = NULL;
    return new_node;
}

void insert(struct Node* root, int x)
{
    if(root -> left == NULL && x < root -> data)
    {
        root -> left = create_node(x); // Use function
    }
    else if(root -> right == NULL && x > root -> data)
    {
        root -> right = create_node(x); // Use function
    }
    else
    {
        if(x < root -> data)
        {
            insert(root -> left, x);
        }
        else if(x > root -> data)
        {
            insert(root -> right, x);
        }
    }
}

struct Node* create() // No parameter, but return type
{
    printf("\nHow many nodes do you want to create: ");
    int tree_size;
    scanf("%d", &tree_size);
    printf("\nEnter data for root node: ");
    int ent_data;
    scanf("%d", &ent_data);
    struct Node* root = create_node(ent_data); // Use function
    for(int i=1; i<tree_size; i++)
    {
        printf("\nEnter data for node: ");
        scanf("%d", &ent_data);
        insert(root, ent_data);
    }
    return root; // Return the root
}

void preOrderTraversal(struct Node *root)
{
    if(root != NULL)
    {
        printf("%d, ", root -> data);
        preOrderTraversal(root -> left);
        preOrderTraversal(root -> right);    
    }
}


int main()
{
    struct Node* root = create(); // No argument, but return value
    preOrderTraversal(root);
    return 0;
}

为什么我的二叉搜索树的创建功能不起作用？

Why is my create function of binary search tree not working?

data-structures

tree

binary

binary-search-tree

creation