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

Question

create函数应该询问用户要输入多少个节点，然后逐个插入这么多元素。

我正在使用预购遍历功能来检查二进制搜索树的创建

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

#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不会修改main的变量root。C参数是按值传递的，因此您应该执行以下操作之一：

• 将root的地址传递给create函数，或者
• 根本不要将root作为参数传递，而是让create返回根指针

第二个选项是首选选项，因为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;
}