本文共 5271 字，大约阅读时间需要 17 分钟。

   
   
   
/************************************************* 五、查找、排序、文件 1、【二叉排序树与文件操作】 功能要求： （1）从键盘输入一组学生记录建立二叉排序树； （2）二叉排序树存盘； （3）由文件恢复内存的二叉排序树； （4）中序遍历二叉排序树； （5）求二叉排序树深度； （6）求二叉排序树的所有节点数和叶子节点数； （7）向二叉排序树插入一条学生记录； （8）从二叉排序树中删除一条学生记录； （9）从二叉排序树中查询一条学生记录； （10）以广义表的形式输出二叉排序树 等功能。 //定义学生记录类型 struct student { char num[6]; // 学号 int grade; // 成绩 }; // 定义二叉排序树节点值的类型为学生记录类型 typedef struct student ElemType; // 定义二叉排序树的节点类型 typedef struct BSTNode { ElemType data; struct BSTNode *left; struct BSTNode *rchild; } BSTNode; BSTNode *Node; struct student s[100]; int BSTInsert(Node &t, struct student key) { if (t) { if (key.grade == t->data.grade) return 0; else if (key.grade < t->data.grade) return BSTInsert(t->lchild, key); else return BSTInsert(t->rchild, key); } else { t = new Node(); t->lchild = t->rchild = NULL; t->data = key; return 1; } return 0; } void CreateBST(Node &t, struct student key[], int n) { t = NULL; for (int i = 0; i < n; i++) BSTInsert(t, key[i]); } void preorder(Node bt) { if (bt) { printf("学号: %s 成绩: %d\n", bt->data.num, bt->data.grade); preorder(bt->lchild); preorder(bt->rchild); } } void inorder(Node bt) { if (bt) { inorder(bt->lchild); printf("学号: %s 成绩: %d\n", bt->data.num, bt->data.grade); inorder(bt->rchild); } } void disorder(Node bt) { if (bt) { disorder(bt->lchild); disorder(bt->rchild); printf("学号: %s 成绩: %d\n", bt->data.num, bt->data.grade); } } int getheight(Node bt) { if (!bt) return 0; int l, r; l = getheight(bt->lchild); r = getheight(bt->rchild); return (l > r ? l : r) + 1; } int CountLeaf(Node bt) { if (!bt) return 0; if (!bt->lchild && !bt->rchild) return 1; return CountLeaf(bt->lchild) + CountLeaf(bt->rchild); } int CountNode(Node bt) { if (!bt) return 0; return 1 + CountNode(bt->lchild) + CountNode(bt->rchild); } int flag; void Search(Node bt, int number) { if (!bt) { // puts("没有此人。"); return; } else { if (bt->data.num == number) { printf("输入的学号 %d 对应的成绩为 %d\n", number, bt->data.grade); flag = 1; return; } Search(bt->lchild, number); Search(bt->rchild, number); } }void Delete(Node &p) { if (!p->lchild && !p->rchild) { p = NULL; return 1; } else if (!p->lchild) { // 左空，重接右子树 q = p; p = p->rchild; delete p; } else if (!p->rchild) { q = p; p = p->lchild; delete p; } else { q = p; s = p->lchild; while (s->rchild) { q = s; s = s->rchild; } p->data = s->data; delete s; } return 1; }int BSTDelete(Node &t, struct student key) { if (!t) return 0; else { if (key.num == t->data.num) Delete(t); else if (key.grade < t->data.grade) BSTDelete(t->lchild, key); else BSTDelete(t->rchild, key); return 0; } }void get_pos(Node bt) { Queue
    
      Q; Node p = bt; if (p) { p->pos = 1; Q.push(p); while (!Q.empty()) { p = Q.front(); Q.pop(); if (p->lchild) { p->lchild->pos = 2 * p->pos; Q.push(p->lchild); } if (p->rchild) { p->rchild->pos = p->pos; Q.push(p->rchild); } } }void get_saved(Node t) { if (!t) return; else { s[t->pos].grade = t->data.grade; s[t->pos].num = t->data.num; get_saved(t->lchild); get_saved(t->rchild); }void check(Node t) { if (!t) return; else { check(t->lchild); printf("操作的学号: %s 操作的成绩: %d\n", t->data.num, t->data.grade); check(t->rchild); }FILE *fp; void File_W(Node t) { get_pos(t); check(t); for (int i = 0; i < 100; i++) { s[i].grade = s[i].num = 0; } get_saved(t); if ((fp = fopen("file.rtf", "ab+")) == NULL) { printf("不能打开文件。\n"); getchar(); } fwrite(s, sizeof(struct student), 100, fp); rewind(fp); }void file_r(Node t) { fread(ss, sizeof(struct student), 100, fp); check(t); for (int i = 0; i < 100; i++) printf("%d %d\n", ss[i].num, ss[i].grade); }void display(Node t) { if (t) { printf("("); display(t->lchild); display(t->rchild); printf("学号: %s, 成绩: %d", t->data.num, t->data.grade); printf(")"); } }void error() { puts("请输入正确的选项."); }int main() { cout << "******************二叉排序树与文件操作***********************\n"; Node t = NULL; while (1) { cout << "1. 创建排序二叉树"; cout << "2. 先序遍历排序二叉树"; cout << "3. 中序遍历排序二叉树"; cout << "4. 后序遍历排序二叉树"; cout << "5. 查找排序二叉树的深度"; cout << "6. 查找排序二叉树的节点个数";cout << "7. 查找排序二叉树的叶子个数";cout << "8. 向排序二叉树中插入一条记录";cout << "9. 向排序二叉树中删除一条记录";cout << "10. 查找二叉排序树的一条记录";cout << "11. 保存排序二叉树";cout << "12. 恢复排序二叉树";cout << "13. 广义表形式输出二叉排序树";cout << "0. 退出";cout << "请输入您要进行的操作：";int n; cin >> n;if (n == 0) break; if (n == 1) { cout << "请输入要排序的学生数 n "; cin >> n;cout << "请输入n个学生的学号和成绩"; struct student stu[n]; for (int i = 0; i < n; i++) { cin >> stu[i].num >> stu[i].grade; } CreateBST(t, stu, n); continue; }if (n == 2) { preorder(t); continue; } if (n == 3) { inorder(t); continue; } if (n == 4) { disorder(t); continue; } if (n == 5) { printf("树的深度为: %d\n", getheight(t)); continue; } if (n == 8) { cout << "所有节点个数为: " << CountNode(t) << endl; cout << "叶子个数为: " << CountLeaf(t) << endl; puts("请输入要插入学生的学号和成绩："); struct student tmp; cin >> tmp.num >> tmp.grade; BSTInsert(t, tmp); cout << "插入成功！" << endl; continue; }if (n == 9) { puts("请输入要删除记录的学号和成绩:"); struct student tmp; cin >> tmp.num >> tmp.grade; BSTDelete(t, tmp); cout << " 删除成功！" << endl; continue; }if (n == 10) { flag = 0; int number; cout << "请输入要查找的学号: "; cin >> number; Search(t, number); if (!flag) cout << "没有此人，请输入正确的学号。" << endl; continue; }if (n == 11) { File_W(t); file_r(t); display(t); continue; } if (n == 12) { t = File_R(t); continue; } if (n == 13) { error(); continue; }return 0;}