127 lines
3.0 KiB
C++
127 lines
3.0 KiB
C++
//
|
|
// Created by grtsinry43 on 5/8/25.
|
|
//
|
|
|
|
#include "problem2.h"
|
|
|
|
#include <iostream>
|
|
#include <string>
|
|
using namespace std;
|
|
|
|
struct Student {
|
|
int id; // 学号
|
|
int score; // 成绩
|
|
Student(int id, int score) : id(id), score(score) {}
|
|
};
|
|
|
|
struct TreeNode {
|
|
Student data;
|
|
TreeNode* left;
|
|
TreeNode* right;
|
|
explicit TreeNode(Student data) : data(data), left(nullptr), right(nullptr) {}
|
|
};
|
|
|
|
class BST {
|
|
private:
|
|
TreeNode* root;
|
|
|
|
TreeNode* insert(TreeNode* node, Student data) {
|
|
if (!node) return new TreeNode(data);
|
|
if (data.id < node->data.id)
|
|
node->left = insert(node->left, data);
|
|
else if (data.id > node->data.id)
|
|
node->right = insert(node->right, data);
|
|
return node;
|
|
}
|
|
|
|
TreeNode* findMin(TreeNode* node) {
|
|
while (node && node->left) node = node->left;
|
|
return node;
|
|
}
|
|
|
|
TreeNode* remove(TreeNode* node, int id) {
|
|
if (!node) return nullptr;
|
|
if (id < node->data.id)
|
|
node->left = remove(node->left, id);
|
|
else if (id > node->data.id)
|
|
node->right = remove(node->right, id);
|
|
else {
|
|
if (!node->left) {
|
|
TreeNode* temp = node->right;
|
|
delete node;
|
|
return temp;
|
|
} else if (!node->right) {
|
|
TreeNode* temp = node->left;
|
|
delete node;
|
|
return temp;
|
|
}
|
|
TreeNode* temp = findMin(node->right);
|
|
node->data = temp->data;
|
|
node->right = remove(node->right, temp->data.id);
|
|
}
|
|
return node;
|
|
}
|
|
|
|
TreeNode* search(TreeNode* node, int id) {
|
|
if (!node || node->data.id == id) return node;
|
|
if (id < node->data.id)
|
|
return search(node->left, id);
|
|
return search(node->right, id);
|
|
}
|
|
|
|
void inorder(TreeNode* node) {
|
|
if (!node) return;
|
|
inorder(node->left);
|
|
cout << "ID: " << node->data.id << ", Score: " << node->data.score << endl;
|
|
inorder(node->right);
|
|
}
|
|
|
|
public:
|
|
BST() : root(nullptr) {}
|
|
|
|
void insert(Student data) {
|
|
root = insert(root, data);
|
|
}
|
|
|
|
void remove(int id) {
|
|
root = remove(root, id);
|
|
}
|
|
|
|
void search(int id) {
|
|
TreeNode* result = search(root, id);
|
|
if (result)
|
|
cout << "Found - ID: " << result->data.id << ", Score: " << result->data.score << endl;
|
|
else
|
|
cout << "Student with ID " << id << " not found." << endl;
|
|
}
|
|
|
|
void display() {
|
|
inorder(root);
|
|
}
|
|
};
|
|
|
|
int problem_2() {
|
|
BST bst;
|
|
|
|
// 插入学生成绩
|
|
bst.insert(Student(101, 85));
|
|
bst.insert(Student(102, 90));
|
|
bst.insert(Student(103, 78));
|
|
bst.insert(Student(104, 88));
|
|
|
|
cout << "All students:\n";
|
|
bst.display();
|
|
|
|
// 查找学生成绩
|
|
cout << "\nSearching for student with ID 102:\n";
|
|
bst.search(102);
|
|
|
|
// 删除学生信息
|
|
cout << "\nRemoving student with ID 103:\n";
|
|
bst.remove(103);
|
|
|
|
cout << "\nAll students after removal:\n";
|
|
bst.display();
|
|
|
|
return 0;
|
|
} |