学号：012091034001
课程设计
题目按层次输入建立二叉树
学院计算机科学与技术学院
专业计算机科学与技术专业
班级计算机0909
姓名樊旭
指导教师张霞
2011 年07 月03 日
目录
●课程设计任务
书 (2)
●按层次建立二叉树的实
现 (3)
一、问题描述 (3)
二、设计 (3)
1、存储结构设计 (3)
2、主要算法设计 (3)
3、测试用例设计 (5)
三、调试报告 (5)
四、经验和体会 (6)
五、源程序清单和运行结果 (6)
●成绩评定
表 (10)
课程设计任务书
学生姓名：旭专业班级： 0909 班
指导教师：张霞工作单位：计算机科学系
题目: 按层次输入建立二叉树
初始条件：
按层次输入扩展的完全二叉树中的结点，建立一棵二叉树。
（1）用二叉链表作存储结构；
（2）对建立的二叉树给出后序遍历的结果；
（3）测试用例自己设计；
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：
1、问题描述
简述题目要解决的问题是什么。
2、设计
存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；
3、调试报告
调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。
4、经验和体会（包括对算法改进的设想）
5、附源程序清单和运行结果。
源程序要加注释。
如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，
6、设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。
时间安排：
1、第19周完成。
2、7月1 日14：00到计算中心检查程序、交课程设计报告、源程序（CD 盘）。
指导教师签名：年月日
系主任（或责任教师）签名：年月日
按层次输入建立二叉树的实现
一、问题描述
按层次输入扩展的完全二叉树中的结点，建立一棵二叉树。
（1）用二叉链表作存储结构；
（2）对建立的二叉树给出后序遍历的结果；
（3）测试用例自己设计；
二、设计
1、存储结构设计
由问题采用二叉链表存储结构为：
typedef struct btnode
{
char cdata;
struct btnode *lchild,*rchild;
}BTNode;
BTNode *Create_BiTree()
2、主要算法设计
（1）函数BTNode *Create_BiTree()实现对二叉树的建立，同时使用辅助数组建立二叉树。
定义顶点编号整型i以‘0’作为结束条件，以及顶点信息字符型ch以‘#’作为结束条件。
辅助数组p【MAXSIZE】各项则指向依次输入的数据。
BTNode *Create_BiTree()
{
int i,j;
char ch;
BTNode *s,*t,*p[MAXSIZE];
printf("输入顶点编号及信息，输入0和#结束:i,ch");
scanf("%d,%c",&i,&ch);
while(i==0||ch=='#') break;
while(i!=0 &&ch!='#')
{s=(BTNode *)malloc(sizeof(BTNode));
s->cdata=ch;
s->lchild=s->rchild=NULL;
p[i]=s;
if(i==1) t=s;
else
{j=i/2;
if(i%2==0) p[j]->lchild=s;
else p[j]->rchild=s;
}
printf("输入顶点编号及信息，输入0和#结束:i,ch");
scanf("%d,%c",&i,&ch);
}
return t;
（2）函数void Postorder(BTNode *bt)实现二叉树的后序遍历。
使用递归左右子树完成输出。
void Postorder(BTNode *bt)
{/*后序递归遍历*/
if(bt)
{
Postorder(bt->lchild);
Postorder(bt->rchild);
printf("%c",bt->cdata);
}
}/* Postorder*/
3、测试用例设计
假设有完全一棵二叉树，按层次遍历为：g c f a b d e，现按此程序建立二叉树按后序输出结果应为：a b c d e f g则正确。
三、调试报告
1、刚开始设想建立二叉树时，在生成新节点时申请一个
辅助变量，下一次再申请一个，但是这样的设计浪费
存储空间并且不易于操作，更正为辅助数组即解决这
一问题。
2、判断输入节点i是上一节点j（j=i/2）的左右孩子时，
如果i%2==0那么说明节点i是j的左孩子，则
p[j]->lchild=s，否则p[j]->rchild=s即可。
3、习惯性用#include<iostream.h>,但由于该头文件中不
包括malloc函数和printf及scanf函数，所以不能运
行。
将其更正为#include<stdlib.h>和#include <stdio.h>
后正确。
四、经验和体会
我这次的课程设计相对简单，只需建立一棵二叉树并后序输出就可以了，因此总体上并无多大难度，但是在这种小实验上调试过程就有了较多错误，虽然很多错误都是由于粗心造成的，但是这也十分提醒我在以后的实验和工作中得多注意小细节，不要粗心大意，不然到头来费时费力。
此外，在生成节点时选择正确和效率的算法和技巧也十分重要，在程序的时间和空间上找一个折衷的思想对其效率有很大提高，因此也要引起注意。
相信通过这次较正式的形式对程序
的分析，会对我以后的学习起到促进和补充的作用。
五、源程序清单和运行结果
#include<stdlib.h>
#include <stdio.h>
#define MAXSIZE 20
typedef struct btnode
{
char cdata;
struct btnode *lchild,*rchild;
}BTNode;
BTNode *Create_BiTree()//二叉树的建立
{//用辅助数组建立二叉树
int i,j;
char ch;
BTNode *s,*t,*p[MAXSIZE];
printf("输入顶点编号及信息，输入0和#结束:i,ch");
scanf("%d,%c",&i,&ch);
while(i==0||ch=='#') break;
while(i!=0 &&ch!='#')//建立二叉树的存储结构
{s=(BTNode *)malloc(sizeof(BTNode));
s->cdata=ch;
s->lchild=s->rchild=NULL;
p[i]=s;
if(i==1) t=s;//判断输入结点是根结点、左孩子还是右孩子
else
{j=i/2;
if(i%2==0) p[j]->lchild=s;
else p[j]->rchild=s;
}
printf("输入顶点编号及信息，输入0和#结束:i,ch");
scanf("%d,%c",&i,&ch);
}
return t;
}// Create_BiTree1
void Postorder(BTNode *bt)
{/*后序递归遍历*/
if(bt)
{
Postorder(bt->lchild);
Postorder(bt->rchild);
printf("%c",bt->cdata);
}
}// Postorder
void main()
{
BTNode *t;
t=Create_BiTree();
printf("后序遍历结果:\n"); Postorder(t); }
运行结果截图：
运行结果正确无误。
本科生课程设计成绩评定表班级：计算机009班姓名：旭学号：012091034001
序号评分项目满分实得分
1 学习态度认真、遵守纪律10
2 设计分析合理性10
3 设计方案正确性、可行性、创造性20
4 设计结果正确性40
5 设计报告的规范性10
6 设计验收10
总得分/等级
评语：
注：最终成绩以五级分制记。
优（90-100分）、良（80-89分）、中（70-79分）、
及格（60-69分）、60分以下为不及格
指导教师签名：
201 年月日。