二叉树的建立和后序遍历的演示.doc

《二叉树的建立和后序遍历的演示.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、题目:二叉树的建立和后序遍历的演示初始条件：理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法；实践：计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）选择树的存储结构,建立二叉树（2）用递归算法和非递归算法实现二叉树的后序遍历2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字（中文和英文）；（3）正文，包括引言、需求分析、数据结构

2、设计、算法设计、程序实现及测试、不足之处、设计体会等；（4）结束语；（5）参考文献。时间安排：2007年7月2日－7日（第18周）7月2日查阅资料7月3日系统设计，数据结构设计，算法设计7月4日-5日编程并上机调试7月6日撰写报告7月7日验收程序，提交设计报告书。指导教师签名：2007年7月6日系主任（或责任教师）签名：2007年月日二叉树的建立和后序遍历演示周其凤计算机0502班摘要：该程序的主要部分有：建立一个二叉树以及二叉树的后序遍历算法的演示。关键字：二叉树，左右子树，根结点，后序遍历0.引言设计不同的

3、结点结构可构成不同形式的链式存储结构。由二叉树的定义得知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据域和左、右指针域。利用这种结点结构所得的二叉树的存储结构称之为二叉链表。遍历二叉树即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。1.需求分析：1.1先序次序输入建立二叉树；1.2后序遍历二叉树的

4、递归算法；1.3后序遍历二叉树的非递归算法。2．数据结构设计：//-------二叉树的链表存储表示-------typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;//-------基本操作的函数原型说明（部分）---------StatusCreateBiTree(BiTree&T);//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树//构造二叉链表表示的二叉树T.StatusP

5、reOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链表存储结构，Visit是对结点操作的应用函数。//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。//一旦Visit()失败，则操作失败。StatusinOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链表存储结构，Visit是对结点操作的应用函数。//中序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。//

6、一旦Visit()失败，则操作失败。StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链表存储结构，Visit是对结点操作的应用函数。//后序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。//一旦Visit()失败，则操作失败。StatusLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链表存储结构，Visit是对结点操作的应用函数。//层次遍

7、历二叉树T，对每个结点调用函数Visit一次且仅一次。//一旦Visit()失败，则操作失败。3．算法设计：3.1先序建立二叉树这个函数主要是生成二叉树。voidCreateBiTree(BiTree*T){//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树//构造二叉链表表示的二叉树T.charch;ch=tree[ti++];if(ch==NULL)return;if(ch=='')*T=NULL;else{*T=(BiTree)malloc(sizeof(BiTNode));(*T)->da

8、ta=ch;//生成根结点CreateBiTree(&(*T)->lchild);//构造左子树CreateBiTree(&(*T)->rchild);//构造右子树}}3.2二叉树的后序遍历演示算法：3.2.1二叉树的后序遍历递归算法:voidPostOrder(BiTreeT){if(T){PostOrder(T->lchild);PostOrder(T->rchild);prin