课程设计任务书
学生姓名： 专业班级：
指导教师： 工作单位：
题 目: 二叉树的建立和后序遍历的演示
初始条件：
理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法；
实践：计算机技术系实验室提供计算机及软件开发环境。
要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1、系统应具备的功能：
（1）选择树的存储结构,建立二叉树
（2）用递归算法和非递归算法实现二叉树的后序遍历
（3）二叉树后序遍历的演示
2、数据结构设计；
3、主要算法设计；
4、编程及上机实现；
5、撰写课程设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
，包括：
（1）设计题目；
（2）摘要和关键字（中文和英文）；
（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等；
（4）结束语；
（5）参考文献。
时间安排： 2010年元月10日----14日（第19周）
元月10日- 查阅
资料
新概念英语资料下载李居明饿命改运学pdf成本会计期末资料社会工作导论资料工程结算所需资料清单
元月11日- 系统设计，数据结构设计，算法设计
元月12日---13日 编程并上机调试
元月14日- 撰写报告
元月15日- 验收程序，提交设计报告书。
指导教师签名： 2010年1月10日
系主任（或责任教师）签名： 2010年1月10日
二叉树的建立和后序遍历的演示
摘要：
程序选择树的存储结构为链表存储，建立二叉树。 用两种算法来实现二叉树的后序遍历，即递归算法和非递归算法。程序用于实现数据的存储和不同方式的输出。
关键字：二叉树 后序遍历 递归算法 非递归算法
Abstract：
This program choose linked list to be the storage structure of
the tree.In this way,we establish a binary tree.When achieving postorder traversal of the binary tree,I use tow
kinds of algorithm,they are recursive algorithm and nonrecursive algorithm.This program is used to achieve the storage of data.It can also output data in two different ways.
Key words: binary tree postorder traversal recursive algorithm nonrecursive algorithm.
1.引言
二叉树是一种树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于二的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树的优越性在于可以快速查找数据。二叉树可以在log（n）的时间复杂度内查找一个数据，而用普通的数组或线性列表只能在n的时间复杂度内查找一个数据。这样，数据的查找方面就提供了非常大的便利。后序遍历二叉树则为二叉树数据查找的方式之一。其操作定义为：若二叉树为空，则空操作，否则1.后序遍历左子树2.后序遍历右子树3.访问根节点
二叉树使得数据的存储以及压缩变得方便。在计算机领域应用非常广泛，是非常基础也非常重要的知识点。许多算法需要建立在二叉树的基础上实现，鉴于此，我选择了这个课题，希望可以让自己有所锻炼。
2．需求分析
首先需要建立二叉树。为了方便数据的输入，以先序次序建立一个二叉树，二叉树的存储结构为链表存储。然后以递归和非递归两种方式来后序遍历建立的二叉树，基本操作为：从根节点开始，沿左子树一直走到没有左孩子的节点为止。并将所经[节点]的地址第一次进栈，当找到没有左孩子的节点时，此节点的左子树已访问完毕。从栈顶退出该节点，判断该节点是否为第一次进栈，如是，再将所经[节点]的地址第二次进栈，并沿该节点的右子树一直走到没有右孩子的节点为止，如否，则访问该节点。此时，该节点的左、右子树都已完全遍历，且令指针p = NULL。如此重复到栈空为止。
3.数据结构与算法分析
3.1数据结构设计
//-------二叉树的链表存储表示---------
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*Bitree;
//-------------基本操作的函数原型说明（部分）---------
Status CreateBiTree(BiTree &T);
//按先序次序输入二叉树终结点的值（一个字符），空格表示空树//构造二叉链表表示的二叉树T.
Status PreOrderTraverse(bitree T,Status(*Visit)(TElemType e));\
//构造二叉链表存储结构，Visit是对结点操作的应用函数。
//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
//一旦Visit（）失败，则操作失败。
Status inorderTraverse(BiTree T,Status(*Visit)(TElemType e));\
//采用二叉链表存储结构，Visit是对结点操作的应用函数。
//中序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
//一旦Visit()失败，则操作失败。
Status PostorderTraverse(BiTree T,Status(*Visit)(TElemType e));\
//采用二叉链表存储结构，Visit是对结点操作的应用函数。
后序遍历二叉树T，对每个结点调用函数Visit一次且仅一次
//一旦Visit()失败，则操作失败。
3.2算法设计
3.2.1先序建立二叉树
这个函数主要是生成二叉树
#include
#include
struct tree
{
char data;
struct tree *lchild;//结点的坐孩子
struct tree *rchild;、、结点的右孩子
};
typedef struct tree * treptr;
treptr build(treptr t)//先序顺序建立二叉树
{
char c;
c=getchar();
if(c=='#')
{
t=NULL;//如果输入的是“#”，则此结点为空
}
else
{
t=(treptr)malloc(sizeof(struct tree));
t->data=c;
t->lchild=build(t->lchild);
t->rchild=build(t->rchild);
}
return t;
}
}
3.2.2二叉树的后续遍历演示算法
3,2,2.1二叉树的后续遍历递归算法：
void postdorder(treptr root)//这是递归实现
{
if (root!=NULL)
{
postdorder(root->lchild);//先遍历左子树
postdorder(root->rchild);//再遍历右子树
printf("%c",root->data);//访问根节点
}
}
struct stack
{
treptr *top,*base;//栈顶指针和栈尾指针
};
typedef struct stack *stackptr;
void init (stackptr s)//初始化栈
{
s->base=(treptr*)malloc(sizeof(treptr)*100);
s->top=s->base;
}
void push(stackptr s,treptr t)//入栈
{
*(s->top++)=t;
}
treptr pop(stackptr s)//弹出栈顶元素
{
treptr t;
t=*(--(s->top));
return t;
}
treptr gettop(stackptr s)//取栈顶元素
{
treptr *l=s->top-1;
return *(l);
}
3,2.2.2采用“标记栈法”的后序遍历非递归算法（while-while形式）
void postorder(treptr t)//这是非递归后序实现
{
stackptr s=(stackptr)malloc(sizeof(struct stack));
treptr temp=t;
treptr p;
treptr lastvist=NULL;
init(s);
p=t;
while(p||s->top!=s->base)
{
while(p)
{
push(s,p);
p=p->lchild;
}
temp=gettop(s);
if(temp->rchild==NULL||temp->rchild==lastvist)
{
putchar(temp->data);
lastvist=pop(s);
}
else
p=temp->rchild;
}
}
4.源代码
#include
#include
struct tree
{
char data;
struct tree *lchild;
struct tree *rchild;
};
typedef struct tree * treptr;
treptr build(treptr t)
{
char c;
c=getchar();
if(c=='#')
{
t=NULL;
}
else
{
t=(treptr)malloc(sizeof(struct tree));
t->data=c;
t->lchild=build(t->lchild);
t->rchild=build(t->rchild);
}
return t;
}
void postdorder(treptr root)
{
if (root!=NULL)
{
postdorder(root->lchild);
postdorder(root->rchild);
printf("%c",root->data);
}
}
struct stack
{
treptr *top,*base;
};
typedef struct stack *stackptr;
void init (stackptr s)
{
s->base=(treptr*)malloc(sizeof(treptr)*100);
s->top=s->base;
}
void push(stackptr s,treptr t)
{
*(s->top++)=t;
}
treptr pop(stackptr s)
{
treptr t;
t=*(--(s->top));
return t;
}
treptr gettop(stackptr s)
{
treptr *l=s->top-1;
return *(l);
}
void postorder(treptr t)
{
stackptr s=(stackptr)malloc(sizeof(struct stack));
treptr temp=t;
treptr p;
treptr lastvist=NULL;
init(s);
p=t;
while(p||s->top!=s->base)
{
while(p)
{
push(s,p);
p=p->lchild;
}
temp=gettop(s);
if(temp->rchild==NULL||temp->rchild==lastvist)
{
putchar(temp->data);
lastvist=pop(s);
}
else
p=temp->rchild;
}
}
void main()
{
treptr t=NULL;
t=build(t);
postdorder(t);
printf("非递归后序遍历\n");
postorder(t);
printf("\n");
return 0;
}
5.运行结果
先序顺序输入二叉树：
得到二叉树的两种方式（递归和非递归）运行出来的二叉树的后序遍历结果
输入第二棵二叉树结点值
得到运行结果（二叉树的递归和非递归两种方式产生的后序遍历）
6.有关技术讨论
这个程序的核心就是二叉树的两种后序遍历的方式，即递归和非递归。二叉树的建立过程中是以先序遍历输入各个结点值的。如果输入的数据不符合二叉树的结构，那么运行将出错。二叉树很好的节省了数据存储的空间。二叉树的后序遍历则实现了非常方便的查找各个数据。我们知道程序调用自身的编编程技巧称为递归（ recursion）。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。以上的截图中显示的是输入以下二叉树后程序用递归和非递归两种算法对二叉树进行后序遍历的结果。
我们可以看到二叉树的结构导致了其数据的查找非常方便。为每个结点分配左孩子和右孩子，若左孩子和右孩子为空则输入”#”，这样在输出数据的时候只需用指针分别指向某个结点的左孩子和右孩子即可。
7.设计体会
通过这次课程设计，我对算法的谁有了更深入的了解，并且进一步熟悉了c语言和语法。
对二叉树的建立和遍历在成舍得设计上比较复杂，这次课程设计的过程中我多次与同学交流怎样使二叉树的算法更加见状更加简单。这对我自己有很大的提升。二叉树的应用是非常广泛的，利用二叉树的遍历和查找可实现方便快速查找。学好二叉树的应用是很重要的。这是我第一次自己完整的做一个程序，从算法开始。有很多还需要改进的地方。比如程序在调试的过程中花费了相当多的时间，细节上不够细心导致很多小错误的产生。但是也的确很好的锻炼了我自己的编程能力。
结束语
本程序成功的实现了二叉树的建立以及用递归和非递归两种方式对而擦书进行后序遍历。再输入了二叉树的各个结点后能用两种方式输出其后序遍历。但是在算法的简洁性上还非常需要改进，对二叉树的应用需要更加熟悉。
参考文献
1.谭浩强主编 《C语言程序设计》 清华大学出版社2008年7月
2. 严蔚敏，吴伟民，米宁编著 《数据结构》 清华大学出版社2007年3月
3.屈婉玲，耿素云，张立昂 编著 《离散数学》 高等教育出版社2008 3月
本科生课程设计成绩评定表
班级： 姓名： 学号：
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
10
2
设计分析合理性
10
3
设计
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
正确性、可行性、创造性
20
4
设计结果正确性
40
5
设计报告的规范性
10
6
设计验收
10
总得分/等级
评语：
注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、
及格（60-69分）、60分以下为不及格
指导教师签名：
2011 年 元 月17日
浙公网安备 33021202002483