课程设计任务
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
学生姓名： 陈楠 专业班级： 软件zy1202班
指导教师： 夏红霞 工作单位： 计算机科学与技术学院
题 目: 二叉树的建立和中序遍历的演示
课程设计要求:
1、熟练掌握基本的数据结构；
2、熟练掌握各种算法；
3、运用高级语言编写质量高、风格好的应用程序。
课程设计任务:
1、系统应具备的功能：
（1）以二叉链为存储结构,建立二叉树
（2）用递归算法和非递归算法实现二叉树的中序遍历
（3）二叉树中序遍历的演示
2、数据结构设计；
3、主要算法设计；
4、编程及上机实现；
5、撰写课程设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
，包括：
（1）设计题目；
（2）摘要和关键字；
（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等；
（4）结束语；
（5）参考文献。
时间安排： 2010年7月5日－9日 （第19周）
7月5日 查阅资料
7月6日 系统设计，数据结构设计，算法设计
7月7日 -8日 编程并上机调试
7月9日 撰写报告
7月10日 验收程序，提交设计报告书。
指导教师签名：
2010年7月4日
系主任（或责任教师）签名： 2010年7月4日
二叉树的建立和中序遍历的演示
摘要：
该程序用先序递归的方式建立二叉树，然后采用递归和非递归的方法中序遍历二叉树
关键字：
二叉树 中序遍历 递归 非递归
一 需求分析：
优化复杂递归，提高程序效率，快速查找，插入删除，实现简单而相当有效的数据压缩算法 ，编译器设计的核心数据结构 。
二 算法设计：
#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,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->top-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->rchild;
++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 *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=(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 node's details is :%d\n",data);
#endif
#ifdef FLOAT
printf("The tree node's details is :%f\n",data);
#endif
#ifdef CHAR
printf("The tree node's details is :%c\n",data);
#endif
return 1;
}
/*---------------中序遍历二叉树---------------------*/
/*递归中序遍历二叉树*/
void InorderTraverse(BTNode bitree,int (*Visit)(ElemType data))
{
if(bitree)
{
InorderTraverse(bitree->lchild,Visit);
Visit(bitree->data);
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->data);
p=p->rchild;
}
}
}
/*--------------------------------主函数------------------------------------*/
int main(void)
{
BTNode bitree;
InitTree(&bitree);/*初始化根节点*/
printf("-------整型和浮点型以0表示空，字符以空格表示空--------\n");
浙公网安备 33021202002483