数据结构课程设计二叉树的创建和遍历

《数据结构课程设计二叉树的创建和遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、安徽工程大学数据结构课程设计说明书   学生姓名: 刘超学号：3120702109 学院:计算机与信息学院专业:信息与计算科学题目:二叉树的创建和遍历指导教师潘海玉    2014年8月25日目录1.需求分析-----------------------12.概要设计-----------------------13.详细设计-----------------------34.调试分析-----------------------95.课程总结-----------------------106.附录-----------------------121.

2、需求分析问题描述：根据运行时输入的先序序列，创建一棵二叉树，分别对其进行先序、中序、后序、层序遍历，并显示遍历结果。voidCreateBTree(BTree&T)//按先序次序输入，构造二叉树voidPreOrder(BTreeT)//递归先序遍历voidInOrder(BTreeT)//递归中序遍历voidPostOrder(BTreeT)//递归后序遍历voidLevelOrder(BTreeT)//层序遍历voidNRPreOrder(BTreebt)//非递归先序遍历voidNRInOrder(BTreebt)//非递归中序遍历voidNRPo

3、stOrder(BTreebt)//非递归后序遍历voidmain()//二叉树的建立与遍历实现2.概要设计此次课程设计遍历算法的框架图层序遍历遍历算法递归遍历非递归遍历先序遍历中序遍历后序遍历先序遍历中序遍历后序遍历第20页此次课程设计所用的三组二叉树AACBCBDFEEFDGHABFGCDEH本设计所使用的存储结构：typedefcharElemType;//定义二叉树结点值的类型为字符型typedefstructbnode{//二叉链表结构定义ElemTypedata;structbnode*lchild,*rchild;}Bnode,*BTree

4、;typedefstruct{BTreeptr;inttag;第20页}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);//构造二叉树的左子树CreateBT

5、ree(T->rchild);//构造二叉树的右子树}}voidPreOrder(BTreeT){//递归先序遍历if(T){printf("%c",T->data);PreOrder(T->lchild);PreOrder(T->rchild);第20页}}voidInOrder(BTreeT){//递归中序遍历if(T){InOrder(T->lchild);printf("%c",T->data);InOrder(T->rchild);}}voidPostOrder(BTreeT){//递归后序遍历if(T){PostOrder(T->lchild

6、);PostOrder(T->rchild);printf("%c",T->data);}}voidLevelOrder(BTreeT){//层序遍历BTreeQ[MAX];intfront=0,rear=0;第20页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;

7、rear=(rear+1)%MAX;}if(p->rchild){//右孩子不为空，入队Q[rear]=p->rchild;rear=(rear+1)%MAX;}}}voidNRPreOrder(BTreebt){//非递归先序遍历BTreestack[MAX],p;第20页inttop;if(bt!=NULL){top=0;p=bt;while(p!=NULL

8、

9、top>0){while(p!=NULL){printf("%c",p->data);stack[top]=p;//预留p指针在数组中top++;p=p->lchild;}if(top>0){

10、top--;p=stack[top];p=p->rchild;///*左子树为空