2按上表序列,构造一棵二叉排序树,每个结点中保存学生的姓名、学号和成绩信息。①按中序遍历输出此二叉树;②按广度优先遍历算法输出此二叉树;③以姓名为关键字,查找某人的成绩单信息;以Tai Yi为例输出查询结果;④如果想输出所有成绩低于或等于75的所有信息,用伪代码告诉我怎么做
时间: 2024-03-10 21:45:02 浏览: 15
对于这道题目,我们可以按照以下步骤来解决:
1. 按照表中的序列,构建二叉排序树,每个节点中保存学生的姓名、学号和成绩信息。
2. 按中序遍历输出此二叉树,得到排序后的学生信息。
3. 按广度优先遍历算法输出此二叉树,得到按层次遍历的学生信息。
4. 以姓名为关键字,查找某人的成绩单信息,以Tai Yi为例输出查询结果。
5. 如果想输出所有成绩低于或等于75的所有信息,可以使用中序遍历算法遍历二叉排序树,对于每个节点,判断其成绩是否低于或等于75,如果是,则输出其学生信息。
以下是伪代码实现:
```
// 定义二叉排序树节点结构体
struct TreeNode {
string name; // 学生姓名
int id; // 学生学号
int score; // 学生成绩
TreeNode* left; // 左子节点
TreeNode* right;// 右子节点
};
// 向二叉排序树中插入节点
void insert(TreeNode* &root, string name, int id, int score) {
if (root == nullptr) {
root = new TreeNode{name, id, score, nullptr, nullptr};
return;
}
if (name < root->name) {
insert(root->left, name, id, score);
} else {
insert(root->right, name, id, score);
}
}
// 中序遍历二叉排序树
void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->name << " " << root->id << " " << root->score << endl;
inorderTraversal(root->right);
}
// 广度优先遍历二叉排序树
void levelTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
cout << cur->name << " " << cur->id << " " << cur->score << endl;
if (cur->left != nullptr) {
q.push(cur->left);
}
if (cur->right != nullptr) {
q.push(cur->right);
}
}
}
// 查找学生姓名为name的成绩单信息
TreeNode* find(TreeNode* root, string name) {
if (root == nullptr) {
return nullptr;
}
if (name == root->name) {
return root;
} else if (name < root->name) {
return find(root->left, name);
} else {
return find(root->right, name);
}
}
// 输出所有成绩低于或等于75的学生信息
void printLowScore(TreeNode* root) {
if (root == nullptr) {
return;
}
printLowScore(root->left);
if (root->score <= 75) {
cout << root->name << " " << root->id << " " << root->score << endl;
}
printLowScore(root->right);
}
// 测试代码
int main() {
TreeNode* root = nullptr;
insert(root, "Zhang San", 1001, 85);
insert(root, "Li Si", 1002, 92);
insert(root, "Wang Wu", 1003, 78);
insert(root, "Zhao Liu", 1004, 65);
insert(root, "Tai Yi", 1005, 90); // 以Tai Yi为例进行查找
cout << "中序遍历结果:" << endl;
inorderTraversal(root);
cout << "广度优先遍历结果:" << endl;
levelTraversal(root);
cout << "查找Tai Yi的成绩单信息:" << endl;
TreeNode* t = find(root, "Tai Yi");
cout << t->name << " " << t->id << " " << t->score << endl;
cout << "所有成绩低于或等于75的学生信息:" << endl;
printLowScore(root);
return 0;
}
```