二叉树遍历算法的应用与实现数据结构课程设计说明书格式.doc

PAGE PAGE 1 中北大学 数 据 结 构 课 程 设 计 说 明 书 ? ? ? 学生姓名: ?宁亚楠 学 号： 1021011601? 学 院: 软件学院 专 业: 软件开发与测试? 题 目: 二叉树遍历算法的应用与实现 指导教师 何志英 ? ? ? ?20 设计任务概述（包括系统总体框图及功能描述） 此次课程设计遍历算法的框架图 遍历算法 遍历算法 递归遍历 非递归遍历 先序遍历 中序遍历 后序遍历 先序遍历 中序遍历 后序遍历 此次课程设计所用二叉树 A A B D C F E 本设计所采用的数据结构（如：链表、栈、树、图等） 链表，栈，二叉树。 功能模块详细设计 本程序的功能是建立二叉树，对二叉树进行递归先序遍历、中序遍历和后序遍历，用栈实现非递归的先序、中序遍历和后序遍历。 本程序要求用户以字符输入，最后以回车键建入数据。 本程序的结果将依次打印出递归先序遍历、中序遍历和后序遍历，用栈实现非递归的先序和中序遍历和后序遍历。 3.1 详细设计思想 函数功能及声明如下，源代码见附表： int CreateBiTree(BiTree *T)； //建立一棵二叉树 int preOrder(BiTree T)； //先序递归遍历二叉树 int inOrder(BiTree T)； //中序递归遍历二叉树 int oldOrder(BiTree T)； //后序递归遍历二叉树 void dlr(BiTNode *t)； //前序非递归遍历二叉树 void ldr(BiTNode *t)； //中序非递归遍历二叉树 void lrd(BiTNode *t)； //后序非递归遍历二叉树 void main()； //选择功能及输出界面 3.2 核心代码 #includestdio.h #includestdlib.h #define maxsize 100 int leafcount=0; //二叉树的二叉链表存储表示 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //栈的定义 typedef struct stack { int top; BiTree stacklist[maxsize]; }stack,*sqlist; //构造一棵二叉树 int CreateBiTree(BiTree *T) { char ch; printf(输入节点:\n); scanf(%c,ch); ch=getchar(); while(!((ch=zch=a||ch==0)||(ch=Zch=A||ch==0))) { //printf(字符非法,请重新输入\n); ch=getchar(); } printf(\n); if(ch==0) { *T=NULL; } else{ if(!(*T=(BiTree)malloc(sizeof(BiTNode)))) return 0; (*T)-data=ch; CreateBiTree(((*T)-lchild)); CreateBiTree(((*T)-rchild)); } return 1; } //先序递归遍历二叉树 int preOrder(BiTree T) { if(T){ printf(%c ,T-data); if (!T-lchild!T-rchild) leafcount+=1; preOrder(T-lchild); preOrder(T-rchild); } return 1; } //中序递归遍历二叉树 int inOrder(BiTree T) { if(T){ inOrder(T-lchild); printf(%c ,T-data); inOrder(T-rchild); } return 1; } //后序递归遍历二叉树