武汉理工大学《数据结构》课程设计说明书
题 目: 二叉树的建立和后序遍历的演示 初始条件：
理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算
法；
实践：计算机技术系实验室提供计算机及软件开发环境。
要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写
等具体要求）
1、系统应具备的功能：
（1）选择树的存储结构,建立二叉树
（2）用递归算法和非递归算法实现二叉树的后序遍历 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现；
5、撰写课程设计报告，包括： （1）设计题目；
（2）摘要和关键字（中文和英文）；
（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现
及测试、不足之处、设计体会等； （4）结束语； （5）参考文献。
时间安排： 2007年7月2日－7日 （第18周）
7月2日 查阅资料
7月3日 系统设计，数据结构设计，算法设计 7月4日-5日 编程并上机调试 7月6日 撰写报告
7月7日 验收程序，提交设计报告书。
指导教师签名： 2007年7月6日 系主任（或责任教师）签名： 2007年 月 日
二叉树的建立和后序遍历演示
周其凤 计算机0502班
武汉理工大学《数据结构》课程设计说明书
摘要：该程序的主要部分有：建立一个二叉树以及二叉树的后序遍历算法的演示。
关键字：二叉树 ，左右子树，根结点，后序遍历
0. 引言
设计不同的结点结构可构成不同形式的链式存储结构。由二叉树的定义
得知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据域和左、右指针域。利用这种结点结构所得的二叉树的存储结构称之为二叉链表。
遍历二叉树即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。
后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。
1. 需求分析：
1.1 先序次序输入建立二叉树；
1.2后序遍历二叉树的递归算法； 1.3 后序遍历二叉树的非递归算法。
2．数据结构设计：
//-------二叉树的链表存储表示------- 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()失败，则操作失败。
Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e));\\ //采用二叉链表存储结构，Visit是对结点操作的应用函数。 //层次遍历二叉树T，对每个结点调用函数Visit一次且仅一次。 //一旦Visit()失败，则操作失败。
3．算法设计：
3.1 先序建立二叉树
这个函数主要是生成二叉树。
void CreateBiTree(BiTree *T) {
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树 //构造二叉链表表示的二叉树T. char ch; ch=tree[ti++]; if(ch==NULL) return; if(ch==' ') *T=NULL;
武汉理工大学《数据结构》课程设计说明书
else {
*T=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=ch;
//生成根结点
//构造左子树 //构造右子树
CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } }
3.2 二叉树的后序遍历演示算法：
3.2.1二叉树的后序遍历递归算法:
void PostOrder(BiTree T) {
if(T) {
PostOrder(T->lchild); PostOrder(T->rchild); printf(\ } }
3.2.2采用”标记栈法“的后序遍历非递归算法（while-while形式）
void PostOrder_zb(BiTree t) {
int tag[100],top=0; /*tag为标记栈*/
BiTree stack[100]; while(t||top) {
while(t) { stack[++top]=t;
tag[top]=0; /*标记栈置为0：第一次访问*/ t=t->lchild; }
if(top) {
if(tag[top]==1) {printf(\如果这个结点访问了两次，输出之*/
