注：实验用书为 数据结构 C语言版 第2版，人民邮电出版社出版。
实验题目：学生管理系统的设计与实现
实验环境：Visual C++ 6.0或其他C++环境
一、实验目的
1、掌握二叉树的定义；
2、掌握二叉树的基本操作，如二叉树的建立、遍历、结点个数统计、树的深度计算等。
二、实验内容
（一）用递归的方法实现以下算法：
1、以二叉链表表示二叉树，建立一棵二叉树（算法5.3）；
2、输出二叉树的中序遍历结果（算法5.1）；
3、输出二叉树的前序遍历结果（见样例）；
4、输出二叉树的后序遍历结果（见样例）；
5、计算二叉树的深度（算法5.5）；
6、统计二叉树的结点个数（算法5.6）；
7、统计二叉树的叶结点个数；
8、统计二叉树的度为1的结点个数；
9、输出二叉树中从每个叶子结点到根结点的路径。
10、交换二叉树每个结点的左孩子和右孩子；
11、设计二叉树的双序遍历(DblOrderTraverse)算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。
三、测试效果如图：

四、代码如下：

#include <iostream>
using namespace std;

typedef struct Node
{//定义二叉树结构
    char data;
    struct Node *lchild,*rchild;
}*BiTree,BiTNode;

void CreateBiTree(BiTree &T)
{//先序创建二叉树
    char ch;
    cin>>ch;
    if(ch=='#') T=NULL;
    else{
        T=new BiTNode;
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
void InOrderTraverse(BiTree T)
{//中序遍历
    if(T)
    {
        InOrderTraverse(T->lchild);
        cout<<T->data;
        InOrderTraverse(T->rchild);
    }
}
void PreOrderTraverse(BiTree T)
{//先序遍历
    if(T)
    {
        cout<<T->data;
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}
void PostOrderTraverse(BiTree T)
{//后序遍历
    if(T)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout<<T->data;
    }
}
void Copy(BiTree T,BiTree &NewT)
{//二叉树的复制
    if(T==NULL){
        NewT=NULL;
        return;
    }else
    {
        NewT=new BiTNode;
        NewT->data=T->data;
        Copy(T->lchild,NewT->lchild);
        Copy(T->rchild,NewT->rchild);
    }
}
int Depth(BiTree T)
{//树的深度
    if(T==NULL)
        return 0;
    else
    {
        int m=Depth(T->lchild);
        int n=Depth(T->rchild);
        if(m>n) return (m+1);
        else return (n+1);
    }
}
int NodeCount(BiTree T)
{//统计二叉树中结点的个数
    if(T==NULL) return 0;
    else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int LeafCount(BiTree T)
{//统计二叉树中叶子结点的个数
    if(!T) return 0;
    if(!T->lchild &&!T->rchild){//如果二叉树左子树和右子树皆为空,说明该二叉树根节点为叶子节点,加1.
        return 1;
    }else{
        return LeafCount(T->lchild)+LeafCount(T->rchild);
    }
}
int Node_1_Count(BiTree T)
{//统计二叉树的度为1的结点个数
    if(!T) return 0;
    if((!T->lchild)&&(T->rchild)||(T->lchild)&&(!T->rchild))
        return 1 + Node_1_Count(T->lchild) + Node_1_Count(T->rchild);
    else
        return Node_1_Count(T->lchild) + Node_1_Count(T->rchild);
}
void PrintAllPath(BiTree T, char path[], int pathlen)
{//二叉树中从每个叶子结点到根结点的路径
  int i;
  if(T != NULL) {
    path[pathlen] = T->data; //将当前结点放入路径中
    if(T->lchild == NULL && T->rchild == NULL) {//叶子结点
        for(i = pathlen; i >= 0; i--)
            cout << path[i] << " " ;
      cout << endl;
    }else{
      PrintAllPath(T->lchild, path, pathlen + 1);
      PrintAllPath(T->rchild, path, pathlen + 1);
    }
  }
}
void ExChangeTree(BiTree &T)
{//构造函数，使用递归算法进行左右结点转换
    BiTree temp;
    if(T!=NULL){//判断T是否为空，非空进行转换，否则不转换
        temp=T->lchild;
        T->lchild=T->rchild;//直接交换节点地址
        T->rchild=temp;
        ExChangeTree(T->lchild);
        ExChangeTree(T->rchild);
    }
}
void DblOrderTraverse(BiTree T)
{//二叉树的双序遍历
    if(T)
    {
        cout<<T->data;
        DblOrderTraverse(T->lchild);
        cout<<T->data;//访问两遍
        DblOrderTraverse(T->rchild);
    }
}
int main()
{
    BiTree T;
    //测试例子AB#CD##E##F#GH###
    cout<<"先序遍历输入(以#结束):";
    CreateBiTree(T);
    cout<<"中序遍历输出:";
    InOrderTraverse(T);
    cout<<endl<<"先序遍历输出:";
    PreOrderTraverse(T);
    cout<<endl<<"后序遍历输出:";
    PostOrderTraverse(T);
    cout<<endl<<"树的深度:"<<Depth(T);
    cout<<endl<<"结点的个数:"<<NodeCount(T);
    cout<<endl<<"叶结点的个数:"<<LeafCount(T);
    cout<<endl<<"度为1的结点个数:"<<Node_1_Count(T);
    cout<<endl<<"二叉树中从每个叶子结点到根结点的所有路径："<<endl;
    char path[256];
    int pathlen=0;
    PrintAllPath(T,path,pathlen);//
    //交换二叉树每个结点的左孩子和右孩子
    BiTree tem=T;//直接复制一颗树，在不改变原树的前提下，对临时树进行交换。
    ExChangeTree(tem);
    cout<<"先序遍历输出交换后的结果:";
    PreOrderTraverse(tem);
    cout<<endl<<"双序遍历输出:";
    DblOrderTraverse(T);
    return 0;
}

五、流程图：

前言

  数据库是按照一定的数据结构来组织、存储和管理数据的仓库。其实我们在前面的时候介绍过十篇关于数据库调优的文章。我们从本文开始，为大家介绍数据库的基本知识，主要以MySQL为主。本文主要介绍数据库的基础知识，包括数据库的组成以及发展，另外介绍数据库的基本操作，包括数据库、表的增删改。首先给大家介绍数据库的基本知识。

一、数据库的基本知识

  目前为止，随着企业规模不断扩大，面临着以下的问题：

• 1、存储大量数据
• 2、大量数据的检索和访问
• 3、保证数据信息的一致和完整
• 4、数据共享和安全

  数据库一般分为关系型数据库和非关系数据库。其中，关系型数据库主要包括我们常用的MySQL、SqlServer、Orcale等；非关系型数据库主要包括NoSQL、Redis等。我们的数据库的结构如下图所示：

  接下来，给大家介绍表中的一些基本的概念：

  1、我们的表是由固定列和任意形成的表结构的数据集
  2、表中的列称为字段，表中的行称为记录
  3、以字段为基本的存储单位和计算单位
  4、每一个字段必须有字段名，且同一张表中的字段名不能重复
  5、每个字段的==数据类型必须一致==

  其实，我们在日常的生活应用中，除了办公的时候会用到Excel或者WPS之外，其他我们企业面对庞大的数据用到的都是以二维表结构存储数据的存储格式。在我们的主流的关系型数据库中，各个数据库的特点是不一样的，他们的特点分别如下：

  1、Orcale：运行稳定、可移植性高、功能齐全、性能超群，一般适用于大型企业
  2、DB2：速度快、可靠性好，适用于海量数据、恢复性极强，一般适用于大中型企业
  3、MySQL：开源、体积小、速度快，适用于中小型企业
  4、SQLServer：全面高效、界面友好易操作，但是不跨平台，适用于中小型企业

  MySQL最早是由瑞典MySQL AB公司开发，仅供内部使用。2000年基于GPL协议开放源码，2008年MySQL AB公司被Sun公司收购，2009年Sun公司又被Oracle公司收购。有了Orcale公司的技术支持。Mysql在2010年以后发布了多个版本，在各个方面加强了企业级的特性。
  接下来，给大家介绍数据库、数据库管理系统以及SQL之间的关系：

• 1、数据库是长期存储在计算机内、有组织、统一管理的相关数据的集合
• 2、数据库管理系统是用于管理数据库的软件，它对数据进行统一管理和控制，以保证数据库的安全性和完整性。
• 3、SQL是一种结构化查询语言，它是国际标准化组织采纳的标准数据库语言

  接下来，给大家介绍SQL语言分类，一般来说，SQL语言主要分为数据定义语言DDL、数据操作定义DML、数据查询语言DQL、数据控制语言DCL。接下来给大家分别介绍这几种语言：

• 1、数据定义语言DDL：用于创建、修改、删除数据库中的各种对象(数据库、表、视图、索引等)，常用于CREATE、ALTER、DROP。
• 2、数据操作定义DML：用于操作数据库表中的记录，常用于命令有INSERT、UPDATE、DELETE。
• 3、数据查询语言DQL：用于查询数据库表中的记录，基本结构：SELECT <字段名> FROM <表或视图表> WHERE <查询条件>
• 4、数据控制语言DCL：用于定义数据库访问权限和安全级别，常用命令：GRANT、REVOKE

  我们在书写SQL语句的时候有一定的要求，具体如下：

  1、SQL语句可以单行或多行书写，用分号结尾
  2、SQL关键字要用空格分隔，也可以用缩进来增强语句的可读性
  3、SQL对大小写不敏感
  4、用**#或–单行注释，用/**/多行注释，注释语句不可执行

二、数据定义语言DDL

  我们通过MySQL Workbench来写MySQL语句。首先是查看数据库

show databases;

  具体执行结果如下：

  创建数据库：create databases 数据库名称，数据库名称不能与SQL关键字相同，不能重复。具体数据库命令如下：

create database test;

  具体执行结果如下：

  选择使用数据库：use 数据库名称;具体命令如下：

use test;

  具体执行结果如下：

  我们要删除数据库，可以使用drop database 数据库名称,不过这条命令我们慎用，一旦删了，很难恢复的。具体命令实现如下：

drop database test;

  以上就是数据库层面的基本操作，接下来，我们介绍数据库基本结构，具体如下：

• 1、数据库：组织、存储和管理相关数据的集合，同一个数据库管理系统中数据库名必须唯一
• 2、表：由固定列数和任意行数构成的二维表结构的数据集，同一个数据库中表命名必须唯一
• 3、字段：一列即为一字段，同一表中字段名必须唯一
• 4、记录：一行即为一条记录。以 字段为基本存储和计算单位，每个字段的数据类型必须一致 。
  

  接下来介绍数据表的增删改查，首先介绍创建数据表：create table 表名;，不过在建表之前要先选择进入数据库：use 数据库名称，建表的时候可以不指定约束条件，但是 必须指定表名、字段名及每个字段的数据类型，表名不能与SQL关键字相同，同一个数据库下的表名不能重复，具体命令如下：

create table department(
deptno int, 
dname varchar(10), 
num int
);

  具体执行结果如下：

  查看当前数据库中所有表用show tables,具体命令如下：

show tables;

  具体执行结果如下：

  查看表名结构用desc 表名，具体命令如下：

desc emp;

  具体执行结果如下：

  我们删除表格要用drop table 表名，但是这条命令要慎用。

drop table employee;

  具体执行结果如下：

  接下来介绍MySQL常用数据类型。具体介绍如下：

• int：大整数型，有符号大小-2147483648~2147483647， 无符号大小0~4294967295，默认长度最多为11个数字，如int(11)
• float：单精度浮点型，默认float(10,2)，表示最多10个数字，其中有2位小数
• decimal：十进制小数型，适合金额、价格等对精度要求较高的数据存储。默认decimal(10,0)，表示最多10位数字，其中0位小数。
• char：固定长度字符串型，长度为1-255。如果长度小于指定长度，右边填充空格。如果不指定长度，默认为1。如char(10)，‘abc ’ • varchar：可变长度字符串型，长度为1-255。必须指定长度，如varchar(10)，‘abc’ • text：长文本字符串型，最大长度65535，不能指定长度
• date：日期型，‘yyyy-MM-dd’
• time：时间型，‘hh:mm:ss’ • datetime：日期时间型，‘yyyy-MM-dd hh:mm:ss’ • Timestamp：时间戳，在1970-01-01 00:00:00和2037-12-31 23:59:59之间，如1973-12-30 15:30，时间戳为:19731230153000

  具体如下：



  不过需要注意的是：字符串类型和日期时间类型都需要用引号括起来 。接下来，为大家介绍主键约束：

• 每个表中只能有一个主键
• 主键值须非空不重复
• 可设置单字段主键，也可设置多字段联合主键。联合主键中多个字段的取值完全相同时，才违反主键约束

  接下来，添加主键约束。列级添加主键约束：create table <表名> (<字段名1> <字段类型1>primary key,……,<字段n><字段类型n>)；表级添加主键约束：create table <表名> (<字段名1> <字段类型1>……,<字段n><字段类型n>,[constraint 主键约束名], primary key(字段名1[,字段名2,...字段名n]))

  另外，给大家介绍唯一约束：指定字段的取值不能重复，可以为空，但只能出现一个空值； 添加唯一约束：列级添加唯一约束：create table <表名> (<字段名1> <字段类型1> unique,……<字段名n> <字段类型n>);表级添加唯一约束：create table <表名> (<字段名1> <字段类型1,……<字段名n> <字段类型n>,[constraint 唯一约束名] unique (字段名1[,字段名2…字段名n]));
  其次是自动增长列。指定字段的取值自动生成，默认从1开始，每增加一条记录，该字段的取值会加1。只适用于整数型，配合主键一起使用。创建自动增长约束：create table <表名> (<字段名1> <字段类型1> primary key auto_increment,……<字段名n> <字段类型n>);
  非空约束：字段的值不能为空，创建非空约束：create table <表名> (<字段名1> <字段类型1> not null,……<字段名n> <字段类型n>);在默认约束的情况下：如果新插入一条记录时没有为该字段赋值，系统会自动为这个字段赋值为默认约束设定的值，另外，创建默认约束：create table <表名> (<字段名1> <字段类型1> default value,……<字段名n> <字段类型n>)。
  最后就是外键约束。在一张表中执行数据插入、更新、删除等操作时，DBMS都会跟另一张表进行对照，避免不规范的操作，以确保数据存储的完整性。

• 某一表中某字段的值依赖于另一张表中某字段的值
• 主键所在的表为主表，外键所在的表为从表
• 每一个外键值必须与另一个表中的主键值相对应
• 创建外键约束：create table <表名> (<字段名1> <字段类型1>,……<字段名n> <字段类型n>,[constraint 外键约束名]
foreign key(字段名) references <主表>(主键字段));

  具体用代码实现如下：

create table dept(
deptno int primary key,
dname varchar(10),
loc varchar(15)
);

create table employee(
empid int primary key auto_increment,
empname varchar(10) unique,
job varchar(10)  not null default '未知',
mgr int,
hiredate date,
sal float default 0,
comm float,
deptno int,
foreign key(deptno) references dept(deptno)
);

create table employee1(
empname varchar(10) ,
job varchar(10)  not null default '未知',
mgr int,
hiredate date,
sal float default 0,
comm float,
deptno int,
primary key (empname, deptno),
foreign key(deptno) references dept(deptno)
);

  具体执行结果如下：

  接下来修改数据表，具体如下：

• 修改表名：alter table 原表名 rename 新表名;
• 修改字段名：alter table 表名 change 原字段名 新字段名 数据类型;
• 修改字段类型：alter table 表名 modify 字段名 新数据类型;
• 添加字段：alter table 表名 add 新字段名 数据类型;
• 修改字段的排列位置：
  alter table 表名 modify 字段名 数据类型 first;
  alter table 表名 modify 要排序的字段名 数据类型 after 参照字段;
• 删除字段：alter table 表名 drop 字段名;

  具体用代码实现如下：

-- 修改表名
alter table employee rename emp;
-- 修改字段名
alter table emp change empid empno int;
-- 修改字段类型
alter table emp modify sal decimal default 0;
-- 添加字段
alter table emp add city varchar(20);
-- 修改字段的排列位置：
alter table emp modify city varchar(20) first;
alter table emp modify city varchar(20) after job;
-- 删除字段
alter table emp drop city;
desc emp;

  具体执行效果如下：

  以上就是数据定义的全部内容，接下来给大家介绍数据操作语义DML。

三、数据操作语义DML

  前面给大家介绍了数据定义语言，接下来，给大家介绍数据操作语言DML。首先介绍的就是在表中插入数据：

• 指定字段名插入：insert into 表名(字段名1[,字段名2,...]) values(字段值 1[,字段值 2,...]);
• 不指定字段名插入：insert into 表名 values(字段值 1[,字段值 2,...]);需要为表中每一个字段指定值，且值的顺序须和数据表中字段顺序相同
• 批量导入数据：（路径中不能有中文，并且要将‘\’改为‘\’或‘/’） load data infile ‘文件路径.csv’into table 表名 fields terminated by ‘,' ignore 1 lines;

  具体sql语句如下：

-- 插入数据：字段名与字段值的数据类型、个数、顺序必须一一对应
insert into dept(deptno,dname,loc) values (10,'accounting','new york'),
										  (20,'research','dallas');
select * from dept; 
select * from emp; 
insert into dept values (30,'sales','chicago'),
						(40,'operations','boston');

  执行查看dept表结果如下：

  我们批量导入employee表(验证码为：acfl)，我们在下载好表后将其放在不能带有中文的文件夹下，我是放在了E:\database，具体位置如下：

  我们打开该文档，里面的数据如下：

  我们在导入数据的时候，应该要现有部门，因为员工表里有部门的信息，因此，我们现要有部门，才能存储每个部门的员工信息，所以先添加dept的部门信息，再导入emp的员工信息。我们前面在介绍DDL语言的时候已经创建了dept表，现在不重复创建。具体代码如下：

load data infile "E:/database/employee.csv"
into table emp 
fields terminated by ',' 
ignore 1 lines;

  我们可以查看导入的数据以及导入数据的总行数

select * from emp; -- 检查导入数据内容
select count(*) from emp; -- 检查导入数据总行数

  执行的结果如图所示：
  不过需要我们注意的是，如果读者的MySQL版本是8.0 以上，可能在导入的时候会报没有批量导入的权限，具体的错误为：error code：1290 the mysql server is running with the --secure-file-pfiv option so it cannot execute this statement,也就是我们刚才说的没有权限的问题。由于在8.0以上，MySQL加强了数据库的安全性，不允许个人批量导入导出数据。我们首先可以通过以下命令查看我们权限：

show variables like "%secure%"

  执行结果如下：

  如果是刚开始学习MySQL的小伙伴，在执行这条sql语句之前你先得进入mysql库，进入mysql库的命令为：

mysql -uroot -p   --输入密码即可

  执行结果如下：

  我们找到自己安装的MySQL位置，如果你当时没有该目录就在C盘，我是安装到了E盘，在MySQL文件夹下找到 my.ini 文件，我的位置是在这里：
  找到这个文件然后打开，在最后空白处写一句sql命令将其权限打开，具体命令如下：

secure_file_priv =""

  然后保存即可，具体如下：

  然后重启MySQL服务器即可正常导入，如果刚接触mysql的小伙伴们，mysql服务在这里：

  接下来，给大家介绍表中更新数据的操作，我们只需update 表名 set 字段名1=字段值1[, 字段名2=字段值2[,…]][ where 更新条件];，不过在更新数据之前需要设置数据库安全权限，否则会报错，显示我们没有权限；不过这个不用重启mysql服务器。具体的sql语句如下：

set sql_safe_updates=0; -- 设置数据库安全权限
update emp set sal=sal+1000 where empname='smith';
update emp set sal=sal+1000;

  执行结果如下：

  最后介绍删除数据，不过删除就无法恢复了，建议慎用。具体如下：

• delete from 表名[ where 删除条件];
• truncate 表名;（与delete from 表名一样，都是删除表中全部数据，保留表结构）

  具体用sql语句如下：

delete from emp where deptno=20;
truncate emp;

  执行的结果如下：

  既然delete与truncate都对数据表有删除的功能，那么二者之间的区别如下：

• delete可以添加where子句删除表中部分数据，truncate只能删除表中全部数据
• delete删除表中数据保留表结构，truncate直接把表删除(drop table)然后再创建一张新表(create table)，执行速度比delete快。

总结

  本文开始，给大家介绍MySQL的基础知识。本文给大家介绍了数据的基础，包括几种大型数据库的区别与联系以及学习数据库的必要性，以及还介绍了数据库与数据库管理系统以及数据管理员之间的关系。另外，给大家介绍了数据定义语言，包括数据库的增删改查以及进入数据库的命令。最后给大家介绍了数据操作语言，包括对表中的数据进行增删改查。最后还对delete和truncate进行了对比。因此，mysql是很重要的一个技能，几乎计算机中的每个岗位都需要一个mysq技能，因此，需要我们特别的掌握。生命不息，奋斗不止，我们每天努力，好好学习，不断提高自己的能力，相信自己一定会学有所获。加油！！！