二叉排序树的建立及遍历的实现.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月2日系主任（或责任教师）签名：2007年7月2日排序二叉树的建立及其遍历的实现武汉理工大学《数据结构》课程设计说明书摘要：我所设计的课题为排序二叉树的建立及其遍历的实现，它的主要功能是将输入的数据组合成排序二叉树，并进行，先序，中序和后序遍历。设计该课题采用了C语言程序设计，简洁而方便，它主要运用了建立函数，调用函数，建立递归函数等等方面来进

3、行设计。关键字：排序二叉树，先序遍历，中序遍历，后序遍历0．引言我所设计的题目为排序二叉树的建立及其遍历的实现。排序二叉树或是一棵空树；或是具有以下性质的二叉树：（1）若它的左子树不空，则作子树上所有的结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3）它的左，右子树也分别为二叉排序树。对排序二叉树的建立需知道其定义及其通过插入结点来建立排序二叉树，遍历及其输出结果。该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历，其关键是运用递归调用，这将极大的方便算法设计。1．需求分析建立排序二叉树，主要是需要建立节点用来存

4、储输入的数据，需要建立函数用来创造排序二叉树，在函数内，需要进行数据比较决定数据放在左子树还是右子树。在遍历二叉树中，需要建立递归函数进行遍历。该题目包含两方面的内容，一为排序二叉树的建立；二为排序二叉树的遍历，包括先序遍历，中序遍历和后序遍历。排序二叉树的建立主要运用了循环语句和递归语句进行，对遍历算法运用了递归语句来进行。2．数据结构设计在写算法之前，应对其进行数据结构设计。本题目主要会用到建立结点，构造指针变量，插入结点函数和建立排序二叉树函数，求深度函数，以及先序遍历函数，中序遍历函数和后序遍历函数，还有一些常用的输入输出语句。对建立的函明确其作用，先理清函数内部的

5、程序以及算法在将其应用到整个程序中，在建立排序二叉树时，主要用到建立节点函数，建立树函数，深度函数，在遍历树是，用到先序遍历函数，中序遍历函数和后序遍历函数。武汉理工大学《数据结构》课程设计说明书结点结构体定义：typedefstructtnode/建立节点/{intdata;structtnodelchild,rchild;}TNODE;3．算法设计在进行算法设计时，应将题目分为两部分，排序二叉树的建立，排序二叉树的遍历。3.1定义结点typedefstructtnode/建立节点/{intdata;structtnodelchild,rchild;}TNODE;TNOD

6、Eq;/构造指针变量/TNODEbt;3.2插入结点函数insert()Voidinsert(TNODEb,TNODEs)/排序二叉树中插入节点/{if((b)==NULL)(b)=s;elseif(s->data==(b)->data)return;elseif(s->data<(b)->data)insert((&(b)->lchild),s);elseif(s->data>(b)->data)insert((&(b)->rchild),s);}3.3创建树函数creat()voidcreat(TNODEb)/建立排序二叉树/武汉理工大学《数据结构》课程设计说明书{in

7、tx;TNODEs;b=NULL;/初始化二叉数/scanf("%d",&x);s=(TNODE)malloc(sizeof(TNODE));q=s;/将根结点指针地址赋值给q/while(x!=-1)/反复读入节点,直至-1结束/{s->data=x;s->lchild=NULL;s->rchild=NULL;insert(&bt,s);scanf("%d",&x);/节点插入排序二叉树中/s=(TNODE)malloc(sizeof(TNODE));n=n+1;}}3.4求排序二叉树的深度intdeep(TNO