《数据结构》课程设计说明书二叉平衡数算法实现班级：计科1703 组别：十七指导老师：彭代文完成时间：2018.6.20 组长：学号：组员 1：学号：组员 2：学号：成绩：目录1.课题设计任务 (1)2.任务分析 (1)3. 概要设计 (2)3.1 功能模块的划分 (2)3.1.1 主功能模块 (2)3.1.2 创建树模块 (2)3.1.3 遍历树模块 (2)3.2功能函数调用图 (2)4.详细设计 (3)4.1 数据存储结构： (3)4.2各模块流程图及算法： (4)4.2.1 主函数 (4)4.2.2 输入二叉树 (5)4.2.3非递归遍历 (5)4.2.4递归遍历 (7)4.3 算法的效率分析： (8)5. 测试 (9)6．课程设计心得 (10)6.1 改进方案 (10)6.2 设计心得 (10)7．参考文献 (11)8．附录 (12)1.课题设计任务现实世界层次化的数据模型中，数据与数据之间的关系纷繁复杂。

其中很多关系无法使用简单的线性结构表示清楚，比如祖先与后代的关系、整体与部分的关系等。

于是人们借鉴自然界中树的形象创造了一种强大的非线性结构——树。

树形结构的具体形式有很多种，其中最常用的就是二叉树。

针对这样的问题, 我选择了二叉树的操作作为我的课程设计主题, 编写程序, 实现对二叉树的遍历. 在本次课程设计中, 二叉树的建立使用了递归算法；在前序、中序和后续遍历的算法中则同时使用了递归与非递归的算法, 即在这些遍历算法的实现中使用了栈结构与队列结构, 提供了6种不同的遍历方式, 供使用者选择. 同时, 该程序具有输出层序遍历的功能, 层序遍历模块使用了非递归算法. 该程序基本实现了对二叉树的遍历, 对于递归与非递归算法, 我们应从实际应用中体验这些算法的优越性。

编程实现二叉树的建立，先序、中序、后序（递归和非递归方法）、层序遍历，二叉树的高度、统计叶子节点的数目、统计结点总数、输出结点的最大值、输出结点所在的层数、打印输出二叉树的单链表形式。

2.任务分析数据存储：采用二叉链表存储功能设计：首先，创建二叉树；其次打印二叉树：若二叉树为空，则空操作；否则依次打印右子树、打印根结点、打印左子树；最后，要实现二叉树的一些基本运算，包括先序遍历、中序遍历、后序遍历、计算结点数、叶子节点数、计算结点所在层等操作。

具体分别是先序遍历二叉树：利用二叉链表作为存储结构的先序遍历，先访问根结点，在依次访问左右子树；中序遍历二叉树：利用二叉链表作为存储结构的中序遍历，先访问左子树，再访问根结点，最后访问右子树；后序遍历二叉树：利用二叉链表作为存储结构的后序遍历，先访问左子树，再访问右子树，最后访问根结点；计算二叉树叶子数：若二叉树为空，返回0；若只有根结点，返回1；否则，返回左子树+右子树；计算二叉树结点数：若二叉树为空，返回0；若只有根结点，返回1；否则，返回左子树+右子树+1。

运用手动键盘输入，将二叉树序列按先序的顺序，从键盘输入到字符数组中，实现二叉树的创建。

运用递归的方式，计算出二叉树的节点的个数以及二叉树的深度，并且在屏幕输出显示等等操作比较基础。

遍历二叉树分为四种方式，先序遍历、中序遍历、后序遍历、层次遍历。

其中先序遍历、中序遍历和后序遍历都用递归与非递归的方法实现，采用链表存储的方式，并在屏幕输出结果。

层次遍历运用循环队列的方法实现，需要重新定义队头和队尾，以及队列的最大长度，并且在屏幕上实现输出显示。

第一次成功创建二叉树之后，如果想要重新创建，必须将已经创建的二叉树实现删除，并且释放内存空间，实现第二次重新创建。

用链式存储结构实现对二叉排序树的的创建，各种遍历，树高、节点数量等基本操作，在整个程序中可以将程序分为四大代码块，首先菜单代码块；其次是基础代码块，分别包括栈操作代码块和队列操作代码块；再其次是主体代码块即各种树操作的函数代码块，最后是输出操作代码块。

Visual Studio 2019编写，可以实现对二叉树的多种方式的创建、采用递归和非递归等两种方式先序、中序、后序进行遍历下面是具体介绍。

3. 概要设计3.1 功能模块的划分3.1.1 主功能模块通过合理的界面设计，根据提示信息，使用者可以方便快捷地运行本程序来完成创建、遍历二叉树、查找结点等操作。

界面美观，人性化，程序智能，安全性高。

3.1.2 创建树模块当进入程序运行界面后，根据提示输入需要建立的二叉树，建立完二叉树后自动进入下一个功能模块。

3.1.3 遍历树模块实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历、层序非递归遍历等方式的遍历操作，并输出各遍历序列。

3.2功能函数调用图图4-1 调用关系图其他功能均为单个函数实现，不做流程描述4.详细设计4.1 数据存储结构：BTNode* LchildNode(BTNode* p) //返回*p结点的左孩子结点指针BTNode* RchildNode(BTNode* p) //返回*p结点的右孩子结点指针void CreateBTree(BTNode*& b, char* str //创建树int FindNode(BTNode* b, ElemType x) //查找结点是否存在void InitQueue(SqQueue*& q) //创建队列bool QueueEmpty(SqQueue* q) //判断队列是否为空bool enQueue(SqQueue* q, BTNode* e) //进队列bool deQueue(SqQueue*& q, BTNode*& e) //出队列void DestoryBTree(BTNode*& b) //销毁释放二叉树void DispBTree(BTNode* b) //输出二叉树int BTHeight(BTNode* b) //计算二叉树高度void PreOrder(BTNode* b) //先序递归遍历算法void InOrder(BTNode* b) //中序递归遍历算法void PostOrder(BTNode* b) //后序递归遍历算法void DispLeaf(BTNode* b) //输出叶子结点int listleaf(BTNode* b) //输出叶子结点个数int listnode(BTNode* b) //输出结点个数int maxnode(BTNode* b) //输出结点的最大值int listfloor(BTNode* b, char x) //输出结点在第几层void InitStack(SqStack*& s) //初始化栈void DestroyStack(SqStack*& s) //销毁栈bool StackEmpty(SqStack* s) //判断栈是否为空bool Push(SqStack*& s, BTNode* e) //进栈bool Pop(SqStack*& s, BTNode*& e) //出栈bool GetTop(SqStack* s, BTNode*& e) //取栈顶元素void PreOrder1(BTNode* b) //先序非递归遍历算法void InOrder1(BTNode* b) //中序非递归遍历算法void PostOrder1(BTNode* b) //后序非递归遍历算法void LevelOrder(BTNode* b) //层次遍历算法4.2各模块流程图及算法：4.2.1 主函数int main(){system("cls");system("color 00a");BTNode* b;int i, n;char x;cout << "本程序为二叉树的操作" << endl;char str[20];cout << "请输入你的二叉树" << endl;cin.getline(str, 20);CreateBTree(b, str);cout << "创建成功!"<<endl;cout << "是否继续操作继续操作请输入1，否则输入0" << endl;cin >> i;while (i != 0){cout << "-------------------------------------------" << endl;cout << "--- 输入【0】结束程序 ---" << endl;cout << "--- 输入【1】输出二叉树 ---" << endl;cout << "--- 输入【2】计算二叉树高度 ---" << endl;cout << "--- 输入【3】查找节点是否存在 ---" << endl;cout << "--- 输入【4】输出所有叶子结点 ---" << endl;cout << "--- 输入【5】计算叶子节点个数 ---" << endl;cout << "--- 输入【6】前序遍历输出二叉树 ---" << endl;cout << "--- 输入【7】中序遍历输出二叉树 ---" << endl;cout << "--- 输入【8】后序遍历输出二叉树 ---" << endl;cout << "--- 输入【9】计算结点个数 ---" << endl;cout << "--- 输入【10】输出该树中结点最大值 ---" << endl;cout << "--- 输入【11】输出树中结点值为x的层 ---" << endl;cout << "--- 输入【12】先序非递归算法 ---" << endl;cout << "--- 输入【13】中序非递归算法 ---" << endl;cout << "--- 输入【14】后序非递归算法 ---" << endl;cout << "--- 输入【15】层次遍历（队列）算法 ---" << endl;cout << "-------------------------------------------" << endl;cout << " >> 请输入你的操作<< " << endl;cin >> i;//以下为功能选择相应的函数，比较繁杂，在此不做展示}}4.2.2 输入二叉树void CreateBTree(BTNode*& b, char* str){//创建二叉链int MaxSize1 = 50;BTNode* St[MaxSize], * p = NULL;int top = -1, k=0, j = 0; char ch = str[j];b = NULL;while (ch != '\0') { //str未扫描完时循环switch (ch) {case '(': top++; St[top] = p; k = 1; break; //可能有左孩子结点，进栈case ')': top--; break;case ',': k = 2; break; //后面为右孩子default:p = (BTNode*)malloc(sizeof(BTNode));p->data = ch;p->lchild = p->rchild = NULL;if (b == NULL)b = p;else {switch (k) {case 1: St[top]->lchild = p; break;case 2: St[top]->rchild = p; break;}}}j++;ch = str[j]; //继续扫描str}}4.2.3非递归遍历void PreOrder1(BTNode* b) //先序非递归遍历算法{BTNode* p;SqStack* st; //定义一个顺序栈指针stInitStack(st); //初始化栈stPush(st, b); //根节点进栈while (!StackEmpty(st)) //栈不为空时循环{Pop(st, p); //退栈节点p并访问它printf("%c ", p->data); //访问节点pif (p->rchild != NULL) //有右孩子时将其进栈Push(st, p->rchild);if (p->lchild != NULL) //有左孩子时将其进栈Push(st, p->lchild);}printf("\n");DestroyStack(st); //销毁栈}//中序非递归遍历void InOrder1(BTNode* b) //中序非递归遍历算法{BTNode* p;SqStack* st; //定义一个顺序栈指针stInitStack(st); //初始化栈stif (b != NULL){p = b;while (!StackEmpty(st) || p != NULL){while (p != NULL) //扫描节点p的所有左下节点并进栈{Push(st, p); //节点p进栈p = p->lchild; //移动到左孩子}if (!StackEmpty(st)) //若栈不空{Pop(st, p); //出栈节点pprintf("%c ", p->data); //访问节点pp = p->rchild; //转向处理其右子树}}printf("\n");}DestroyStack(st); //销毁栈}void PostOrder1(BTNode* b) //后序非递归遍历算法{BTNode* p, * r;bool flag;SqStack* st; //定义一个顺序栈指针stInitStack(st); //初始化栈stp = b;do{while (p != NULL) //扫描节点p的所有左下节点并进栈{Push(st, p); //节点p进栈p = p->lchild; //移动到左孩子}r = NULL; //r指向刚刚访问的节点，初始时为空flag = true; //flag为真表示正在处理栈顶节点while (!StackEmpty(st) && flag){GetTop(st, p); //取出当前的栈顶节点pif (p->rchild == r) //若节点p的右孩子为空或者为刚刚访问过的节点{printf("%c ", p->data); //访问节点pPop(st, p);r = p; //r指向刚访问过的节点}else{p = p->rchild; //转向处理其右子树flag = false; //表示当前不是处理栈顶节点}}} while (!StackEmpty(st)); //栈不空循环printf("\n");DestroyStack(st); //销毁栈}4.2.4递归遍历oid PreOrder(BTNode* b){//先序遍历if (b != NULL){cout << (char)b->data;PreOrder(b->lchild);PreOrder(b->rchild);}}void InOrder(BTNode* b){//中序遍历if (b != NULL){InOrder(b->lchild);cout << (char)b->data;InOrder(b->rchild);}}void PostOrder(BTNode* b){//后序遍历if (b != NULL){PostOrder(b->lchild);PostOrder(b->rchild);cout << (char)b->data;}}4.3 算法的效率分析：主函数：函数中并不包含for循环、递归等复杂的算法，时间复杂度为O（1）；输入二叉树：函数需要扫描输入的二叉树，所以该算法的时间复杂度为O（n）；非递归类遍历：由于不管是先序遍历还是中序遍历以及后序遍历，我们都需要利用一个辅助栈来进行每个节点的存储打印，所以每个节点都要进栈和出栈，不过是根据那种遍历方式改变的是每个节点的进栈顺序，所以时间复杂度为O(n)，同样空间复杂度也为O(n)，n为结点数；递归类遍历：空间复杂度与系统堆栈有关，系统栈需要记住每个节点的值，所以空间复杂度为O(n)。