C语言 如何在二叉搜索树中插入新节点?

Question

我正在尝试插入BST N次，我必须要求用户在insert函数中输入数据。这是我的代码。我尝试使用预购方法打印树，但它只打印最后一个输入。我必须使用ID作为键，并使用预购打印所有数据工资和ID。

#include <stdio.h>
#include <stdlib.h>
struct Node{
int EmployeeID;
float Salary;
struct Node* left;
struct Node* right;
};
struct Node* insert(struct Node* root,int ID, float Salary){

printf("Enter Employee ID: ");
scanf("%d", &ID);
printf("Enter Employee Salary: ");
scanf("%f", &Salary);
if(root == NULL){
root = (struct Node*)malloc(sizeof(struct Node));
root->EmployeeID = ID;
root->Salary = Salary;
root->left=root->right= NULL;
}
else if(ID < root->EmployeeID)
root->left = insert(root->left, ID, Salary);
else
root->right = insert(root->right, ID, Salary);
return root;
};
void PrePrint(struct Node* root){
if(root == NULL)
return;
printf("%d   %.2f", root->EmployeeID, root->Salary);
PrePrint(root->left);
PrePrint(root->right);
return;
}
int main()
{
int N, i;
struct Node* root;
int ID;
int Sal;
root = NULL;
printf("How many Employee you would like to enter? n");
scanf("%d", &N);
for(i=0; i<N; i++){
root = insert(root, ID, Sal);
printf("n");
}
PrePrint(root);
}

Answer 1

删除插入函数中root = NULL;的第一个语句。

就插入功能而言，您可以将其修改为：

struct Node* insert(struct Node* root, int ID, float Salary){
printf("Enter Employee ID: ");
scanf("%d", &ID);
printf("Enter Employee Salary: ");
scanf("%f", &Salary);
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->EmployeeID = ID;
newNode->Salary = Salary;
newNode->left = NULL;
newNode->right = NULL;
struct Node* cp_of_root = root;
if(root==NULL)
return newNode;
struct Node* parent = NULL;
while(root!=NULL){
parent = root;
if (newNode->val > root->val)
root = root->right;
else
root = root->left;
}
if(newNode->val > parent->val)
parent->right = newNode;
else
parent->left = newNode;
return cp_of_root;
}

我希望这段代码能消除你的疑问。

Answer 2

要将 scanf 保留在插入函数中，您需要创建一个标志以了解这是您第一次初始化变量(id 和薪水(还是您已经有值并且不想再次扫描。

#include <stdio.h>
#include <stdlib.h>
struct Node{
int EmployeeID;
float Salary;
struct Node* left;
struct Node* right;
};
struct Node* insert(struct Node* root,int ID, float Salary){
if(ID==-1 && Salary==-1)
{
printf("Enter Employee ID: ");
scanf("%d", &ID);
printf("Enter Employee Salary: ");
scanf("%f", &Salary);
}
if(root == NULL){
root = (struct Node*)malloc(sizeof(struct Node));
root->EmployeeID = ID;
root->Salary = Salary;
root->left=NULL;
root->right= NULL;
}
else if(ID < root->EmployeeID)
root->left = insert(root->left, ID, Salary);
else
root->right = insert(root->right, ID, Salary);
return root;
};
void PrePrint(struct Node* root){
if(root == NULL)
return;
printf("%d   %.2fn", root->EmployeeID, root->Salary);
PrePrint(root->left);
PrePrint(root->right);
return;
}
int main()
{
int N, i;
struct Node* root;
int ID;
float Salary;
root = NULL;
printf("How many Employee you would like to enter? n");
scanf("%d", &N);
for(i=0; i<N; i++){
root = insert(root, ID=-1, Salary=-1);
printf("n");
}
PrePrint(root);
}