某班级学生的姓名、学号、成绩列表如下： Name Number Score Lei Zhenzi 101401 82 Jiang Ziya 100032 90 Ne Zha 101674 70 Shen Gongbao 101982 87 Jiu Weihu 107431 75 Tian Zun 100001 98 Tai Yi 101009 81 Yang Jian 101321 63 Huang Feihu 101567 72 Zhou Wang 108160 55 Li Jing 102456 84 Tu Xingsun 102245 65 内容： 1选择合适的数据结构，按上表序列，构造一棵完全二叉树，每个结点中保存学生的姓名、学号和成绩信息。①按后序(递归)遍历输出此二叉树；②按先序(非递归)算法出此二叉树；③按广度优先遍历算法输出此二叉树； 2按上表序列，构造一棵二叉排序树，每个结点中保存学生的姓名、学号和成绩信息。①按中序遍历输出此二叉树；②按广度优先遍历算法输出此二叉树；③以姓名为关键字，查找某人的成绩单信息；以Tai Yi为例输出查询结果；④如果想输出所有成绩低于或等于75的所有信息；该如何做？ 要求： 1）编写程序，实现上述实验内容。

1. 构造完全二叉树

为了构造完全二叉树，我们需要按照层次遍历的方式依次插入每个节点。同时，对于每个节点，我们需要保存学生的姓名、学号和成绩信息。为了方便，我们可以将这些信息保存在一个结构体中。下面是代码示例：

#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;

struct Student {
    string name;
    int number;
    int score;
};

struct TreeNode {
    Student data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(Student s) : data(s), left(nullptr), right(nullptr) {}
};

void postOrder(TreeNode* root) {
    if (!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->data.name << " " << root->data.number << " " << root->data.score << endl;
}

void preOrder(TreeNode* root) {
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node) {
            cout << node->data.name << " " << node->data.number << " " << node->data.score << endl;
            s.push(node->right);
            s.push(node->left);
        }
    }
}

void levelOrder(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node) {
            cout << node->data.name << " " << node->data.number << " " << node->data.score << endl;
            q.push(node->left);
            q.push(node->right);
        }
    }
}

int main() {
    Student students[] = {
        {"Lei Zhenzi", 101401, 82},
        {"Jiang Ziya", 100032, 90},
        {"Ne Zha", 101674, 70},
        {"Shen Gongbao", 101982, 87},
        {"Jiu Weihu", 107431, 75},
        {"Tian Zun", 100001, 98},
        {"Tai Yi", 101009, 81},
        {"Yang Jian", 101321, 63},
        {"Huang Feihu", 101567, 72},
        {"Zhou Wang", 108160, 55},
        {"Li Jing", 102456, 84},
        {"Tu Xingsun", 102245, 65},
    };
    int n = sizeof(students) / sizeof(Student);

    TreeNode* root = new TreeNode(students[0]);
    queue<TreeNode*> q;
    q.push(root);
    for (int i = 1; i < n; i += 2) {
        TreeNode* parent = q.front();
        q.pop();
        parent->left = new TreeNode(students[i]);
        q.push(parent->left);
        if (i + 1 < n) {
            parent->right = new TreeNode(students[i + 1]);
            q.push(parent->right);
        }
    }

    cout << "Post-order traversal: " << endl;
    postOrder(root);

    cout << "Pre-order traversal: " << endl;
    preOrder(root);

    cout << "Level-order traversal: " << endl;
    levelOrder(root);

    return 0;
}

2. 构造二叉排序树

为了构造二叉排序树，我们需要依次插入每个节点。对于每个节点，我们需要保存学生的姓名、学号和成绩信息。为了方便，我们可以将这些信息保存在一个结构体中。同时，由于二叉排序树的左子树节点的值都小于父节点的值，右子树节点的值都大于父节点的值，因此在插入节点时需要按照一定的规则来进行比较。下面是代码示例：

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct Student {
    string name;
    int number;
    int score;
};

struct TreeNode {
    Student data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(Student s) : data(s), left(nullptr), right(nullptr) {}
};

void inOrder(TreeNode* root) {
    if (!root) return;
    inOrder(root->left);
    cout << root->data.name << " " << root->data.number << " " << root->data.score << endl;
    inOrder(root->right);
}

TreeNode* insert(TreeNode* root, Student s) {
    if (!root) return new TreeNode(s);
    if (s.number < root->data.number) {
        root->left = insert(root->left, s);
    } else {
        root->right = insert(root->right, s);
    }
    return root;
}

TreeNode* search(TreeNode* root, string name) {
    if (!root) return nullptr;
    if (name == root->data.name) {
        return root;
    } else if (name < root->data.name) {
        return search(root->left, name);
    } else {
        return search(root->right, name);
    }
}

void print(TreeNode* root) {
    if (!root) return;
    if (root->data.score <= 75) {
        cout << root->data.name << " " << root->data.number << " " << root->data.score << endl;
    }
    print(root->left);
    print(root->right);
}

int main() {
    Student students[] = {
        {"Lei Zhenzi", 101401, 82},
        {"Jiang Ziya", 100032, 90},
        {"Ne Zha", 101674, 70},
        {"Shen Gongbao", 101982, 87},
        {"Jiu Weihu", 107431, 75},
        {"Tian Zun", 100001, 98},
        {"Tai Yi", 101009, 81},
        {"Yang Jian", 101321, 63},
        {"Huang Feihu", 101567, 72},
        {"Zhou Wang", 108160, 55},
        {"Li Jing", 102456, 84},
        {"Tu Xingsun", 102245, 65},
    };
    int n = sizeof(students) / sizeof(Student);

    TreeNode* root = nullptr;
    for (int i = 0; i < n; i++) {
        root = insert(root, students[i]);
    }

    cout << "In-order traversal: " << endl;
    inOrder(root);

    cout << "Level-order traversal: " << endl;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node) {
            cout << node->data.name << " " << node->data.number << " " << node->data.score << endl;
            q.push(node->left);
            q.push(node->right);
        }
    }

    cout << "Search for Tai Yi: " << endl;
    TreeNode* node = search(root, "Tai Yi");
    if (node) {
        cout << node->data.name << " " << node->data.number << " " << node->data.score << endl;
    } else {
        cout << "Not found." << endl;
    }

    cout << "Students with score <= 75: " << endl;
    print(root);

    return 0;
}

注意：在实际应用中，由于每个节点的数据可能比较复杂，因此在插入、查找和删除节点时需要使用更加高效的数据结构，例如 AVL 树、红黑树等。