数据结构课程设计(先中后序遍历)

.PAGE....XX工程大学数据结构课程设计说明书学生姓名:

刘超学号：3120702109

学院:计算机与信息学院专业:信息与计算科学题目:二叉树的创建和遍历指导教师潘海玉20XX8月25日.....目录需求分析1概要设计1详细设计3调试分析9课程总结10附录12..需求分析问题描述：根据运行时输入的先序序列,创建一棵二叉树,分别对其进行先序、中序、后序、层序遍历,并显示遍历结果。voidCreateBTree<BTree&T>//按先序次序输入,构造二叉树voidPreOrder<BTreeT>//递归先序遍历voidInOrder<BTreeT>//递归中序遍历voidPostOrder<BTreeT>//递归后序遍历voidLevelOrder<BTreeT>//层序遍历voidNRPreOrder<BTreebt>//非递归先序遍历voidNRInOrder<BTreebt>//非递归中序遍历voidNRPostOrder<BTreebt>//非递归后序遍历voidmain<>//二叉树的建立与遍历实现2.概要设计此次课程设计遍历算法的框架图层序遍历遍历算法递归遍历层序遍历遍历算法递归遍历非递归遍历先序遍历中序遍历后序遍历先序遍历中序遍历后序遍历此次课程设计所用的三组二叉树AAAACBCBCBCBDFEEFDDFEEFDGHAGHABFBFGGCCDEHDEH本设计所使用的存储结构：typedefcharElemType;//定义二叉树结点值的类型为字符型typedefstructbnode{//二叉链表结构定义 ElemTypedata; structbnode*lchild,*rchild;}Bnode,*BTree;typedefstruct{ BTreeptr; inttag;}stacknode;3.详细设计voidCreateBTree<BTree&T>{//按先序次序输入,构造二叉链表表示的二叉树T,#表示空树 charch; ch=getchar<>; if<ch=='#'>T=NULL;//读入#时,将相应节点指针置空 else{ if<!<T=<Bnode*>malloc<sizeof<Bnode>>>>printf<"创建失败!">;//生成结点空间 T->data=ch; CreateBTree<T->lchild>;//构造二叉树的左子树 CreateBTree<T->rchild>;//构造二叉树的右子树 }}voidPreOrder<BTreeT>{//递归先序遍历 if<T>{ printf<"%c",T->data>; PreOrder<T->lchild>; PreOrder<T->rchild>; }}voidInOrder<BTreeT>{//递归中序遍历 if<T>{ InOrder<T->lchild>; printf<"%c",T->data>; InOrder<T->rchild>; }}voidPostOrder<BTreeT>{//递归后序遍历 if<T>{ PostOrder<T->lchild>; PostOrder<T->rchild>; printf<"%c",T->data>; }}voidLevelOrder<BTreeT>{//层序遍历 BTreeQ[MAX]; intfront=0,rear=0; BTreep; if<T>{//根结点入队 Q[rear]=T; rear=<rear+1>%MAX; } while<front!=rear>{ p=Q[front];//队头元素出队 front=<front+1>%MAX; printf<"%c",p->data>; if<p->lchild>{//左孩子不为空,入队 Q[rear]=p->lchild; rear=<rear+1>%MAX; } if<p->rchild>{//右孩子不为空,入队 Q[rear]=p->rchild; rear=<rear+1>%MAX; } }}voidNRPreOrder<BTreebt>{//非递归先序遍历 BTreestack[MAX],p; inttop; if<bt!=NULL>{ top=0; p=bt; while<p!=NULL||top>0>{ while<p!=NULL>{ printf<"%c",p->data>; stack[top]=p;//预留p指针在数组中 top++; p=p->lchild; } if<top>0>{ top--; p=stack[top]; p=p->rchild;///*左子树为空,进右子树*/ } } }}voidNRInOrder<BTreebt>{//非递归中序遍历 BTreestack[MAX],p; inttop; if<bt!=NULL>{ top=0; p=bt; while<p!=NULL||top>0>{ while<p!=NULL>{ stack[top]=p;//预留p指针在数组中 top++; p=p->lchild; } if<top>0>{ top--; p=stack[top]; printf<"%c",p->data>; p=p->rchild;/*左子树为空,进右子树*/ } } }}voidNRPostOrder<BTreebt>{//非递归后序遍历stacknodes[MAX],x;BTreep=bt; inttop; if<bt!=NULL>{ top=0; p=bt; do{ while<p!=NULL>{//遍历左子树 s[top].ptr=p; s[top].tag=1;//标记为左子树 top++; p=p->lchild; } while<top>0&&s[top-1].tag==2>{ x=s[--top]; p=x.ptr; printf<"%c",p->data>;//tag为R,表示右子树访问完毕,故访问根结点 } if<top>0>{ s[top-1].tag=2;//遍历右子树 p=s[top-1].ptr->rchild; } }while<top>0>; }}4.调试分析一组测试树运行时界面5.课程总结这个程序的代码较为简单,可以实现了二叉树的三种递归遍历算法和三种非递归遍历算法还有层序遍历算法,想要改进的话可以在选择功能上下手,建立的时候提示更人性化,对输入的数据进行有效性验证,也可以改进为对遍历算法进行选择等等。二叉树这个数据结构几乎在每一本的数据结构的书都作为重点内容讲述,足见其在算法和程序设计界的重要地位。但是,到目前为止,自己还没有真正体验到它的威力,可能是学习的还不够深刻。像二叉树遍历的算法,用递归的算法只是简单的几行代码,然后就可以实现输出遍历次序。对于非递归的思想,要用到栈这个数据结构,但是对于二叉树遍历问题来说非递归要较递归复杂。程序一开始总是出现语法错误,改了很多次也上网查了相关资料,才最后改为现在可以成功运行的程序。在这个过程中,我体会到开发工程师的感觉了,就是要用挑剔的眼光想问题并且不断地改进自己的程序。通过这次课程设计逐渐提高了自己的程序设计和调试能力,通过上机实习,严整自己设计算法的正确性,学会了有效利用基本调试方法,查找出代码中的错误并且修改。我会继续我的兴趣编写程序的,相信在越来越多的尝试之后,自己会不断进步和提高。6.附录#include<stdlib.h>#include<stdio.h>#include<iostream.h>#defineMAX10//结点个数不超过10个typedefcharElemType;//定义二叉树结点值的类型为字符型typedefstructbnode{//二叉链表结构定义 ElemTypedata; structbnode*lchild,*rchild;}Bnode,*BTree;voidCreateBTree<BTree&T>{//按先序次序输入,构造二叉链表表示的二叉树T,#表示空树 charch; ch=getchar<>; if<ch=='#'>T=NULL;//读入#时,将相应节点指针置空 else{ if<!<T=<Bnode*>malloc<sizeof<Bnode>>>>printf<"创建失败!">;//生成结点空间 T->data=ch; CreateBTree<T->lchild>;//构造二叉树的左子树 CreateBTree<T->rchild>;//构造二叉树的右子树 }}voidPreOrder<BTreeT>{//递归先序遍历 if<T>{ printf<"%c",T->data>; PreOrder<T->lchild>; PreOrder<T->rchild>; }}voidInOrder<BTreeT>{//递归中序遍历 if<T>{ InOrder<T->lchild>; printf<"%c",T->data>; InOrder<T->rchild>; }}voidPostOrder<BTreeT>{//递归后序遍历 if<T>{ PostOrder<T->lchild>; PostOrder<T->rchild>; printf<"%c",T->data>; }}voidLevelOrder<BTreeT>{//层序遍历 BTreeQ[MAX]; intfront=0,rear=0; BTreep; if<T>{//根结点入队 Q[rear]=T; rear=<rear+1>%MAX; } while<front!=rear>{ p=Q[front];//队头元素出队 front=<front+1>%MAX; printf<"%c",p->data>; if<p->lchild>{//左孩子不为空,入队 Q[rear]=p->lchild; rear=<rear+1>%MAX; } if<p->rchild>{//右孩子不为空,入队 Q[rear]=p->rchild; rear=<rear+1>%MAX; } }}voidNRPreOrder<BTreebt>{//非递归先序遍历 BTreestack[MAX],p; inttop; if<bt!=NULL>{ top=0; p=bt; while<p!=NULL||top>0>{ while<p!=NULL>{ printf<"%c",p->data>; stack[top]=p;//预留p指针在数组中 top++; p=p->lchild; } if<top>0>{ top--; p=stack[top]; p=p->rchild;///*左子树为空,进右子树*/ } } }}voidNRInOrder<BTreebt>{//非递归中序遍历 BTreestack[MAX],p; inttop; if<bt!=NULL>{ top=0; p=bt; while<p!=NULL||top>0>{ while<p!=NULL>{ stack[top]=p;//预留p指针在数组中 top++; p=p->lchild; } if<top>0>{ top--; p=stack[top]; printf<"%c",p->data>; p=p->rchild;/*左子树为空,进右子树*/ } } }}typedefstruct{BTreeptr;inttag;}stacknode;voidNRPostOrder<BTreebt>{//非递归后序遍历stacknodes[MAX],x;BTreep=bt; inttop; if<bt!=NULL>{ top=0; p=bt; do{ while<p!=NULL>{//遍历左子树 s[top].ptr=p; s[top].tag=1;//标记为左子树 top++; p=p->lchild; } while<top>0&&s[top-1].tag==2>{ x=s[--top]; p=x.ptr; printf<"%c",p->data>;//tag为R,表示右子树访问完毕,故访问根结点 } if<top>0>{ s[top-1].tag=2;//遍历右子树 p=s[top-1].ptr->rchild; } }while<top>0>; }}voidmain<>{//主函数 BTreeT; T=NULL; intselect; while<1>{ printf<"\n\n\n请选择要执行的操作:\n">; printf<"1.创建二叉树\n">; printf<"2.二叉树的递归遍历算法〔前、中、后\n">; printf<"3.二叉树的层次遍历算法\n">; printf<"4.二叉树的非递归遍历算法〔前、中、后\n">; printf<"0.退出\n">; printf<"输入：">; cin>>select; switch<sel