二叉树中序遍历

1、课程设计任务书学生姓名： 陈楠 专业班级： 软件zy1202班 指导教师： 夏红霞 工作单位： 计算机科学与技术学院 题 目: 二叉树的建立和中序遍历的演示课程设计要求:1、熟练掌握基本的数据结构；2、熟练掌握各种算法；3、运用高级语言编写质量高、风格好的应用程序。课程设计任务: 1、系统应具备的功能：（1）以二叉链为存储结构,建立二叉树（2）用递归算法和非递归算法实现二叉树的中序遍历（3）二叉树中序遍历的演示2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字；（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及

2、测试、不足之处、设计体会等；（4）结束语；（5）参考文献。时间安排： 2010年7月5日9日 （第19周）7月5日 查阅资料7月6日 系统设计，数据结构设计，算法设计7月7日 -8日 编程并上机调试7月9日 撰写报告7月10日 验收程序，提交设计报告书。 指导教师签名： 2010年7月4日 系主任（或责任教师）签名： 2010年7月4日 二叉树的建立和中序遍历的演示摘要： 该程序用先序递归的方式建立二叉树，然后采用递归和非递归的方法中序遍历二叉树关键字： 二叉树 中序遍历 递归 非递归一 需求分析： 优化复杂递归，提高程序效率，快速查找，插入删除，实现简单而相当有效的数据压缩算法 ，编译器设计

3、的核心数据结构 。二 算法设计：#include#include#define MAX_STACK 20 /*初始化栈的最大长度*/#define INCREMENT 10 /*每次栈的增量*/typedef int ElemType;#define INT/*-定义数据结构-*/*-定义树的节点-*/typedef struct BiNode ElemType data; struct BiNode *lchild,*rchild; BiNode,*BTNode;/*-定义栈-*/typedef struct Stack int stacksize;/*栈的总长度*/ BTNode base

4、,top;Stack,*BiStack;/*-栈的一些基本操作-*/*-初始化栈*/void InitStack(BiStack stack) stack-base=(BTNode)malloc(sizeof(BiNode)*MAX_STACK); if(!stack-base) printf(1.Memory allocation failed!n); exit(0); stack-top=stack-base; stack-stacksize=MAX_STACK; /*-插入数据元素*/void Push(BiStack stack,BTNode TreeNode) if(stack-to

5、p-stack-base)=stack-stacksize)/*当栈满时重新增加内存*/ stack-stacksize+=INCREMENT; stack-base=(BTNode)realloc(stack-base,sizeof(BiNode)*stack-stacksize); if(!stack-base) printf(2.Memory allocation failed!n); exit(0); stack-top-data=TreeNode-data; stack-top-lchild=TreeNode-lchild; stack-top-rchild=TreeNode-rch

6、ild; +stack-top;/*-删除数据元素*/void Pop(BiStack stack,BTNode *TreeNode) if(stack-top=stack-base) printf(The Stack is Empty!n); return ; *TreeNode=stack-top; -stack-top;/*-判断栈是否为空*/int IsEmpty(Stack stack)/*当栈是空时，返回1，否则返回0*/ if(stack.top=stack.base) return 1; else return 0;/*-创建二叉树-*/void InitTree(BTNode

7、 *bitree) /*初始化二叉树根节点*/ *bitree=NULL; void CreateTree(BTNode *bitree) /*创建二叉树*/*采用先序递归遍历的方式建立二叉树*/ ElemType data; #ifdef INT scanf(%d,&data); if(data=0) #endif #ifdef FLOAT scanf(%f,&data); if(data=0.0) #endif #ifdef CHAR scanf(%c,&data); if(data= )/*当为空格时认为无左或右孩子*/ #endif *bitree=NULL; else *bitree

8、=(BTNode)malloc(sizeof(BiNode); if(!*bitree) printf(4.Memory allocation failed!n); exit(1); (*bitree)-data=data; CreateTree(&(*bitree)-lchild); CreateTree(&(*bitree)-rchild); /*-访问树的节点-*/int print(ElemType data)/*输出树的每个节点的详细信息*/ #ifdef INT printf(%d ,data); /printf(The tree nodes details is :%dn,dat

9、a); #endif #ifdef FLOAT printf(The tree nodes details is :%fn,data); #endif #ifdef CHAR printf(The tree nodes details is :%cn,data); #endif return 1;/*-中序遍历二叉树-*/*递归中序遍历二叉树*/void InorderTraverse(BTNode bitree,int (*Visit)(ElemType data) if(bitree) InorderTraverse(bitree-lchild,Visit); Visit(bitree-d

10、ata); InorderTraverse(bitree-rchild,Visit); /*非递归中序遍历二叉树*/void InorderTraverse1(BTNode bitree,int (*Visit)(ElemType data) BTNode p; Stack stack; InitStack(&stack);/*初始化栈*/ while(p|!IsEmpty(stack) if(p) /*若当前子树非空，则将其根保存并访问左子树*/ Push(&stack,p); p=p-lchild;/*一直找到树的最左边*/ else Pop(&stack,&p); Visit(p-dat

11、a); p=p-rchild; /*-主函数-*/int main(void) BTNode bitree; InitTree(&bitree);/*初始化根节点*/ printf(-整型和浮点型以0表示空，字符以空格表示空-n); printf(Input the tree node data:n); CreateTree(&bitree);/*创建二叉树*/ printf(中序遍历（递归） :n); InorderTraverse(bitree,print);/*递归中序遍历二叉树*/ printf(n); printf(中序遍历（非递归） :n); InorderTraverse(bit

12、ree,print);/*非递归中序遍历二叉树*/ printf(n); return 1;三 程序运行结果：四 不足之处： 虽然程序能正确的运行和输出结果了，但由于时间紧迫，程序设计的时候考虑的不太全面，导致程序设计时较为冗长和繁杂，代码不够优化。而且，手动输入数据比较麻烦，可以改为更为简单的读取文本或数据库的方法来取代手动输入。五 设计体会：经过这些时日的设计，调试与运行，很好的锻炼了我的编程能力，主要是经过对实际问题的编程训练，大大拓宽了我的思路，不再拘泥于书上的一些算法，可以自己总结比较一些其他的算法，对自己编程思想的锻炼起了很大的作用。亦提升了自己对计算机的兴趣，对将来的更深远的学习无疑是有利的。六 结束语： 充分利用前序遍历的特点，就可以生成二叉树。如果把前序换成层序，算法不用改动，若换成后序，只需将