数据结构课程设计
《数据结构》课程设计说明书
二叉平衡数算法实现
班级：计科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 << "创建成功!"< 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; //定义一个顺序栈指针st InitStack(st); //初始化栈st Push(st, b); //根节点进栈 while (!StackEmpty(st)) //栈不为空时循环 { Pop(st, p); //退栈节点p并访问它 printf("%c ", p->data); //访问节点p if (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; //定义一个顺序栈指针st InitStack(st); //初始化栈st if (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); //出栈节点p printf("%c ", p->data); //访问节点p p = p->rchild; //转向处理其右子树 } } printf("\n"); } DestroyStack(st); //销毁栈 } void PostOrder1(BTNode* b) //后序非递归遍历算法 { BTNode* p, * r; bool flag; SqStack* st; //定义一个顺序栈指针st InitStack(st); //初始化栈st p = 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); //取出当前的栈顶节点p if (p->rchild == r) //若节点p的右孩子为空或者为刚刚访问过的节点 { printf("%c ", p->data); //访问节点p Pop(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)。时间复杂度应该为O(nlogn)，每个节点都要遍历到，需要n次，而且需要将二叉树划分logn次，所以递归版的遍历的空间复杂度为O(nlogn)； 层序遍历：层序遍历是通过队列来进行每个节点的存储打印的，所以时间复杂度和空间复杂度都为O(n)，n为结点数。 5. 测试 图5-1 初始化菜单 图5-2输出二叉树 图5-3输出树的高度 图5-4 输出叶子结点 图5-5 输出后序递归遍历 图5-6查找结点所在层 图5-7 输出后续非递归遍历 图5-8 层次遍历输出结构 经过多次测试与更改，但是无法打破原有的界面格式，使得界面输出不够美观，程序的递归与非递归先序、中序、后序遍历、层次遍历、计算结点个数，计算结点所在层数等功能基本能够流畅地实现，达到了应有的要求；不过在输出二叉树的时候，不知道为什么后面会多出一个括号，经过多次的更改与实验也没有将其更改成功，通过查看相关书籍以及网上搜索算法原理，终于明白了错误所在，并完成了排错。 6．课程设计心得 6.1 改进方案 对自己的设计进行评价，指出合理和不足之处，提出改进方案； 1）菜单设置方面：运用了if（）语句，这样看着没有条理，不适合用在二叉树的遍历上，因为遍历结果显而易见并不十分复杂，没有必要使程序复杂化，故采用的是程序运行输出模式。 2）二叉树的创建：采用二叉链表存储的方式，利用扩展先序遍历实现二叉树的创建，这样做相对简单，但是对有些情况下不太实用，所以应该增加一项根据后序中序实现创建的算法，是程序更加完善。 3）整体布局：由于存在某两个函数的制约关系，要求必须先执行A在执行B，一旦执行顺序错误就会导致输出结果错误。这样降低了程序的冗错性，不利于用户操作，可以通过添加函数间强制装换关系，强制执行，或者是在后者运行的函数中添加必要语句，使其脱离制约函数的制约。 6.2 设计心得 其实在本程序的设计过程当中，没有很吸引人的关键技术，因为本人的C语言或C++语言都不是学的很好，所以当初设计的时候就只是想把功能都实现就好了，尽可能的把所要求的功能都编进程序，这样就觉得很满足了。所以都是设计的比较简单易懂的语言，这样自己能够更明白一些，所以就没有时间去细细地去设计自己的程序。本程序要说有什么值得说的，那就只有人性化这点了，在设计成学的时候，因为自己怕弄混了，所以添加了很详尽的提示，这样在编程的过程中或调试的时候都能够比较快的运行。还有就是尽可能的应用了do-while语句和switch-case语句，这两个语句在之前不是很常用，所以在这个程序中试 炼了一下，虽然在编写的过程中总是出错，但还是成功的用好了，也是程序有条理一些。我也知道这些东西别人可能比我弄得还要好，但是我在我所学的知识中成功的应用了这些，我觉得就是好事，就是进步。唯一的亮点可能就是进入系统是的密码设计了，就这一点小小的设计就花了我好几个小时去调试，因为总能在后面程序的加入及运行时发现一些新的小问题。 一周多的课程设计，终于成功的验收了，虽然有些疲惫，但还是有很多的收获的，像计算机组成原理的课设一样，我又一次巩固了所学到的知识，之前的学习只是停留在理论基础上，现在自己动手操作试验后，才是真正的理解及体会。C也学了近一年，有很多知识都是似懂非懂，通过平时上机操作，自己也了解了一些，但让我有了更深的理解和更好的认识，则是在这次的课设上，之前的困惑也通过这次的课设解决了一些，虽然还是不能够全面的理解，但是有进步就很高兴。 在课程设计之前，因为有了综合实验的经验与教训，明白了写代码这一步是非常重要的，因为当你把代码输进去之后，并编译让其运行，发现通过不了，再来检查出问题，是很费费力的事情，因此分析和规划代码是很重要的，最重要的是要把逻辑结构写好，这样就不会出现大问题，写代码就要先找出核心的内容，用多种方法来实现核心部分，这样可以尽可能的避免发现逻辑或编译不支持的错误。 通过本次论文设计，我初步学会了论文设计的基本方法，学会了怎样去借鉴别人的方法和经验，知道了如何整合资料和处理这些资料的能力，这为以后做毕设的论文打下了基础，使我感觉比较好的是有一种成功的喜悦，虽然在编译的时候会经常因为一些小的错误而心烦意乱，但是也不失为一件好事，失败的越多积累的经验越丰富，对人的考验也比较多，那么在最后编译成功时的喜悦就越浓烈，也是自己的能力有了进一步的提高。由于知识和经验的不足，这个程序编写的不是很尽如人意，但是融合了自己的心血，就觉得是最好的，所以在以后还是需要较多的努力的，还是会在以后的学习过程中不断地提高和改进的。 7．参考文献 [1]《算法导论》(英文名：Introduction to Algorithm) 主编：Thomas H.Cormen、 Charles E.Leiserson等译者:潘金贵、顾铁成出版社:机械工业出版社(第三版) [2]《数据结构与算法》主编：王曙燕 2013年9月第1版人民邮电出版社 [3]《C语言程序设计教程》主编：王曙燕 2014年9月第1版人民邮电出版社 [4]谭浩强.C程序设计(第三版)[M].北京:清华大学出版社，2005. 8．附录 #include #include #include #include #include #include "work.h" using namespace std; #define MaxSize 100 using namespace std; typedef char ElemType; typedef struct b { ElemType data; struct b* lchild, * rchild;//二叉树结构声明 }BTNode; typedef struct { BTNode* data[100]; //存放栈中的数据元素 int top; //存放栈顶指针，即栈顶元素在data数组中的下标 } SqStack; typedef struct { BTNode* data[MaxSize];//存放队中元素 int front, rear;//队头队尾指针 }SqQueue; int width[10] = { 0 }; //存放各层宽度的数组 BTNode* LchildNode(BTNode* p) /*返回*p结点的左孩子结点指针*/ { return p->lchild; } BTNode* RchildNode(BTNode* p) /*返回*p结点的右孩子结点指针*/ { return p->rchild; } 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) { case1:St[top]->lchild = p; break; case2: St[top]->rchild = p; break; } } } j++; ch = str[j]; //继续扫描str } } int FindNode(BTNode* b, ElemType x) { int p; if (b == NULL) { return NULL; } else if (b->data == x) { return x; } else { p = FindNode(b->lchild, x); if (p != NULL) { return p; } else return FindNode(b->rchild, x); } } ///队列的有关操作 void InitQueue(SqQueue*& q) { q=(SqQueue*)malloc(sizeof(SqQueue)); q->front = q->rear = 0; } //判断队列是否为空 bool QueueEmpty(SqQueue* q) { return (q->front == q->rear); } //进队列 bool enQueue(SqQueue* q, BTNode* e) { if ((q->rear + 1) % MaxSize == q->front)//队满溢出 return false; q->rear = (q->rear + 1) % MaxSize; q->data[q->rear] = e; return true; } //出队列 bool deQueue(SqQueue*& q, BTNode*& e) { if (q->front == q->rear)//判断是否队空return false; q->front = (q->front + 1) % MaxSize; e = q->data[q->front]; return false; } void DestoryBTree(BTNode*& b) { if (b != NULL) { DestoryBTree(b->lchild); DestoryBTree(b->rchild); free(b); } } void DispBTree(BTNode* b) { //输出单链表 if (b != NULL) { cout << (char)b->data << " "; if (b->lchild != NULL || b->rchild != NULL) { cout << "("; DispBTree(b->lchild); if (b->rchild != NULL) cout << ","; DispBTree(b->rchild); cout << ")"; } } } int BTHeight(BTNode* b) { //树的高度 int lchildh, rchildh; if (b == NULL) return(0); lchildh = BTHeight(b->lchild); rchildh = BTHeight(b->rchild); return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1); } void 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; } } void DispLeaf(BTNode* b) { //递归输出叶子节点 if (b != NULL) { if (b->lchild == NULL & b->rchild == NULL) cout << (char)b->data; DispLeaf(b->lchild); DispLeaf(b->rchild); } } int listleaf(BTNode* b) { //输出叶子结点个数 int num1; if (b == NULL) return 0; else if (b->lchild == NULL && b->rchild == NULL) return 1; num1 = listleaf(b->rchild) + listleaf(b->lchild); return num1; } int listnode(BTNode* b) { int num; if (b == NULL) return(0); else { num = listnode(b->lchild) + listnode(b->rchild) + 1; } return num; } int maxnode(BTNode* b) { if (NULL == b) return 0; int maxLeft = maxnode(b->lchild); int maxRight = maxnode(b->rchild); int max = maxLeft > maxRight ? maxLeft : maxRight; return max > b->data ? max : b->data; } int listfloor(BTNode* b, char x) { int num2, m, n; if (b == NULL) num2 = 0; else if (b->data == x) num2 = 1; else { m = listfloor(b->lchild, x); n = listfloor(b->rchild, x); if (m == 0 && n == 0) num2 = 0; else num2 = ((m > n) ? m : n) + 1; } return num2; } int Level(BTNode* b, ElemType x, int h) { int l; if (b == NULL) return(0); else if ((char)b->data == (char)x) return(h); else { l = Level(b->lchild, x, h + 1);//左子树中查找 if (l != 0) return(l);//在左子树中找到，返回l else return(Level(b->rchild, x, h + 1));//在左子树中未找到再在右子树中查找 } } //栈的所有操作如下 void InitStack(SqStack*& s) //初始化栈 { s=(SqStack*)malloc(sizeof(SqStack));//分配一个是顺序栈空间，首地址存放在s中 s->top = -1; //栈顶指针置为-1 } void DestroyStack(SqStack*& s) //销毁栈 { free(s); } bool StackEmpty(SqStack* s) //判断栈是否为空 { return(s->top == -1); } bool Push(SqStack*& s, BTNode* e) //进栈{ if (s->top == MaxSize - 1) //栈满的情况，即栈上溢出 return false; s->top++; //栈顶指针增1 s->data[s->top] = e; //元素e放在栈顶指针处 return true; } bool Pop(SqStack*& s, BTNode*& e) //出栈{ if (s->top == -1) //栈为空的情况，即栈下溢出 return false; e = s->data[s->top]; //取栈顶指针元素的元素 s->top--; //栈顶指针减1 return true; } bool GetTop(SqStack* s, BTNode*& e) //取栈顶元素 { if (s->top == -1) //栈为空的情况，即栈下溢出 return false; e = s->data[s->top]; //取栈顶元素 return true; } void PreOrder1(BTNode* b) //先序非递归遍历算法 { BTNode* p; SqStack* st; //定义一个顺序栈指针st InitStack(st); //初始化栈st Push(st, b); //根节点进栈 while (!StackEmpty(st)) //栈不为空时循环 { Pop(st, p); //退栈节点p并访问它 printf("%c ", p->data); //访问节点p if (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; //定义一个顺序栈指针st InitStack(st); //初始化栈st if (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); //出栈节点p printf("%c ", p->data); //访问节点p p = p->rchild; //转向处理其右子树 } } printf("\n"); } DestroyStack(st); //销毁栈 } void PostOrder1(BTNode* b) //后序非递归遍历算法 { BTNode* p, * r; bool flag; SqStack* st; //定义一个顺序栈指针st InitStack(st); //初始化栈st p = 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); //取出当前的栈顶节点p if (p->rchild == r) //若节点p的右孩子为空或者为刚刚访问过的节点 {//访问节点p printf("%c ", p->data); Pop(st, p); r = p; //r指向刚访问过的节点 } else { p = p->rchild; //转向处理其右子树 flag = false; //表示当前不是处理栈顶节点 } } } while (!StackEmpty(st)); //栈不空循环 printf("\n"); DestroyStack(st); //销毁栈 } void LevelOrder(BTNode* b) { BTNode* p; SqQueue* qu; InitQueue(qu);//初始化队列 enQueue(qu, b);//根结点指针进入队列 while (!QueueEmpty(qu)) //队不为空时循环 { deQueue(qu, p);//出队结点p cout << (char)p->data << " "; if (p->lchild != NULL)//有 { enQueue(qu, p->lchild); } if (p->rchild != NULL)//有右孩子进队 { enQueue(qu, p->rchild); } } } 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 << "创建成功!"< 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; if (i == 0) { cout << "程序已经退出" << endl; cout << endl; break; } else if (i == 1) { cout << "二叉树输出为" << endl; DispBTree(b); cout << endl; } else if (i == 2) { int h; h = BTHeight(b); cout << "二叉树高度为" << endl; cout << h << endl; cout << endl; } else if (i == 3) { int y; ElemType x; cout << "请输入你要查找的结点" << endl; cin >> x; y = FindNode(b, x); if (y == x) cout << "该结点存在" << endl; else cout << "该结点不存在" << endl; cout << endl; } else if (i == 4) { cout << "叶子结点显示如下：" << endl; DispLeaf(b); cout << endl; } else if (i == 5) { int c; c = listleaf(b); cout << "叶子结点个数为：" << c << endl; cout << endl; } else if (i == 6) { cout << "前序递归遍历输出为" << endl; PreOrder(b); cout << endl; } else if (i == 7) { cout << "中序递归遍历输出为" << endl; InOrder(b); cout << endl; } else if (i == 8) { cout << "后序递归遍历输出为" << endl; PostOrder(b); cout << endl; } else if (i == 9) { int c; cout << "查询结点个数"; c = listnode(b); cout << "个数为" << c << endl; cout << endl; } else if (i == 10) {