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

如对您有帮助，请购买打赏，谢谢您！安徽工程大学数据结构课程设计说明书学生姓名: 刘超 学号： 09学 院: 计算机与信息学院专 业: 信息与计算科学题 目: 二叉树的创建和遍历指导教师 潘海玉2014年8月25日如对您有帮助，请购买打赏，谢谢您！目录需求分析概要设计详细设计调试分析课程总结附录------------------------------------------------------------------------------------------------------------------------------------------

11391012如对您有帮助，请购买打赏，谢谢您！需求分析问题描述：根据运行时输入的先序序列， 创建一棵二叉树，分别对其进行先序、中序、后序、层序遍历，并显示遍历结果。voidCreateBTree(BTree&T)//按先序次序输入，构造二叉树voidPreOrder(BTreeT)//递归先序遍历voidInOrder(BTreeT)//递归中序遍历voidPostOrder(BTreeT)//递归后序遍历voidLevelOrder(BTreeT)//层序遍历voidNRPreOrder(BTreebt)//非递归先序遍历voidNRInOrder(BTreebt)//非递归中序遍历voidNRPostOrder(BTreebt)//非递归后序遍历voidmain()//二叉树的建立与遍历实现概要设计此次课程设计遍历算法的框架图遍历算法递归遍历

层序遍历

非递归遍历先序遍历 中序遍历 后序遍历 先序遍历 中序遍历 后序遍历此次课程设计所用的三组二叉树AA如对您有帮助，请购买打赏，谢谢您！B C B CD E FD E FG H AB FC G本设计所使用的存储结D构： E HtypedefcharElemType;//定义二叉树结点值的类型为字符型typedefstructbnode{//二叉链表结构定义ElemTypedata;structbnode*lchild,*rchild;}Bnode,*BTree;typedefstruct{BTreeptr;inttag;}stacknode;详细设计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);}}调试分析一组测试树运行时界面课程总结这个程序的代码较为简单， 可以实现了二叉树的三种递归遍历算法和三种非递归遍历算法还有层序遍历算法， 想要改进的话可以在选择功能上下手， 建立的时候提示更人性化， 对输入的数据进行有效性验证，也可以改进为对遍历算法进行选择等等。如对您有帮助，请购买打赏，谢谢您！二叉树这个数据结构几乎在每一本的数据结构的书都作为重点内容讲述，足见其在算法和程序设计界的重要地位。但是，到目前为止，自己还没有真正体验到它的威力， 可能是学习的还不够深刻。像二叉树遍历的算法， 用递归的算法只是简单的几行代码，然后就可以实现输出遍历次序。对于非递归的思想，要用到栈这个数据结构，但是对于二叉树遍历问题来说非递归要较递归复杂。程序一开始总是出现语法错误，改了很多次也上网查了相关资料，才最后改为现在可以成功运行的程序。在这个过程中，我体会到开发工程师的感觉了，就是要用挑剔的眼光想问题并且不断地改进自己的程序。通过这次课程设计逐渐提高了自己的程序设计和调试能力，通过上机实习，严整自己设计算法的正确性，学会了有效利用基本调试方法，查找出代码中的错误并且修改。我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。附录#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");prin