数据结构课程设计报告-二叉树根节点到指定节点的路径

1、数据结构课程设计报告-二叉树根节点到指定节点的路径 数据结构课程设计报告 二叉树根节点到指定节点的路径 递归调用思想 班 级： 软件092 姓名：_ 指导教师：成绩：信息工程学院 2011年6月17日-2 -摘要（题目）：二 叉树根节点到指定节点的路径1.引言 二叉树是n个结点的有穷个集合，它或者是空集（n=0 ）,或者同时满足以下 两个条件；（1）有且仅有一个称为根的结点；（2）其余 结点分为两个互不相交的集合 T1 , T2 ,并且T1 , T2 ,都是 二叉树，分别 称为根的左子树和右子树 。二叉树形结构在 客观世界中大量存在，如行政组织机构和人类社会的家谱关 系 等都可用二叉树结构形象

2、地表示。在计算机应用领域， 二叉树也被广泛地应用。例如在编译程序中，可用二 叉树 来表示源程序的语法结构；在数据库系统中，可用二叉树来 表示组织信息；在计算机图形学中，可用二叉树来表示图像关系等。因此对二叉树的研究具有重要意义。2.需求分析利用一个简单的菜单，通过菜单项进行选择，实现和完成如 下功能：用先序输入，建立二叉树存储结构、求指定结点的路径。 对于建立二叉树存储结构，考虑到栈和队列的存 储结构比较繁琐，从而定义一指针数组来一一存储该二叉树先序遍历过的结点，并对该结点进行判断是否为指定的目 标结点，并进行输生等操作。3.概要设计 对二叉树采用链式存储结构，其结构定义如下：typedef

3、structnode DataType data; struct node*lchild,*rchild; BinTNode,*BinTree;每个结点中设置三个域,即值域data ,左指针域*lchild 和右指针域*rchild 。 本 程序分为6大模块：全局变量定义、创建结构体、创建二叉 链表存储表示、查找目标结点、求结 点路径、主函数。(1) 全局变量定义(2)创建结构体(3)创建二叉链表存储表示：定义二叉树的链式存储结构，输入数据生成二叉树。(4)查找目标结点：采用二叉链表作为存储结构，利用递归方法，对各个结点进行判断改结点是否在二叉树中。-3 -(5)求结点路径：采用二叉链表作为存

4、储结构，利用先序遍历二 叉树方法以及指针数组的存储结构方法，对结点路径的遍历查找及输由。(6)主函数 程序流程图 重要函数有 主函数int main () 输入函数 scanf () 输由函数 printf () 二叉树的先序建立函数CreateBiTree () 结点查找函数FindBT ()求结点路径函数NodePath () 4.详细设计 (1)定义二叉树 用链式存储结构存储二叉树。其中，了 lchild和rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。定义二叉树结点值的类型为字符型且结点个 数不超过100个，具体实现方法如下：二叉树的根节点到指定节点的路径

5、主程序代码 输入函数输由函数 建立函数查找函数求路径函数-4 - typedef struct node DataType data; struct node*lchild,*rchild; BinTNode,*BinTree; (2)建立二叉树创 建二叉链表存储的二叉树。按二叉树带空指针的先序次序输 入结点值，结点类型为字符型。按先序 次序输入，其中“ 表示空结点。算法是按照先序遍历思想设计的。构造二叉链 表表示的二叉树，符号 表示空树。具体实现方法如下： Status CreateBiTree(BinTree &bt) char ch; printf(ch=); scanf(%c,&ch)

6、; getchar(); if (ch=) bt=NULL; else bt=(BinTNode *)malloc(sizeof(BinTNode); bt-data=ch; /生成根结点 CreateBiTree(bt-lchild); /构造左子树CreateBiTree(bt-rchild); / 构造右子树 return OK; (3)查找函数-5 -函数功能是用递归方法对二叉树进行先序遍 历查找，调用此函数可以返回二叉树中指定目标结点。算 法思想：若找到目标结点，则返回该目标结点；否则访问二叉 树的根结点；先序遍历根的左子树；先序遍历根的右子树。具体实现方法如下：void FindB

7、T(BinTree bt,DataType x) if(bt!=NULL) & !found) if(bt-data=x) p=bt;found=1; else FindBT(bt-lchild,x); /遍历查找左子树 FindBT(bt-rchild,x); /遍历查找右子树 BinTNode *Findx(BinTree bt,DataType x) /按给定值查找结点int found=0; / 用found来作为是否查找到的标志 BinTree p=NULL; / 置空指针 FindBT(bt,x); return(p); 7)求指定结点路径：该函数功能是根据已创建的二叉树和输入的目

8、标结点，调用此函数可以查找并输由目标结点的路 径。算法思想：根据先序遍历二叉树的递归定义，采用一 个指针数组来保存返回的结点。先扫描根结点的左子树上的结点并写入指针数组。判断该结点是否与指定目标结点相 等，若不相等，然后扫描该结点的右结点并写-6-入指针数组，再扫描该右结点的所有左结点写入指针数组。当一个 结点的左孩子树均访问完后再访问该结点，并与给定的结点比较。若相等，则循环输由指针数组中的所有元素，而这 个顺序值就是要求的路径。若不相等，则继续上述过程。具体实现方法如下：void NodePath(BinTree bt,BinTNode*ch) /求二叉树根结点到给定结点*p的路径type

9、defenum FALSE,TRUEboolean; BinTNode *stacknum; / 定 义指针数组 int tagnum; int i,top; boolean find; BinTNode*s; find=FALSE; top=0; s=bt; do while(s!=NULL) / 扫描 左子树 top+; stacktop=s; tagtop=0; s=s-lchild;if(top0) s=stacktop; if(tagtop=1) - 7 - if(s=ch) 找到ch,则显示从根结点到 ch的路径 for(i=1;i%c,stacki-data);find=TRUE

10、; else top-; s=stacktop; /endif if(top0& !find) if(tagtop!=1) s=s-rchild; /扫描右子树tagtop=1; else s=NULL; /endif /endlif while(!find& top!=0); (8)主函数：-8 -该函数为程序的主函数功能是循环输由菜单，功能界面；从界面获取功能菜单中对 应的字符，通过 switch()语句实现对函数的调用，进而实现 功能。具体代码如下： int main() bool isStop; BinTree bt; char ch1; int xz=1; printf(t *n);

11、 printf(t *ttttttt *n); printf(t*tt欢迎来到这里 tt *n); printf(t * t t建立二叉树并求指定结点路径 t t *n); printf(t *ttttttt *n);printf(t*n); while(xz) /*输由菜单，功能*/printf(n n); printf(=n); - 9 - printf( 1.建立二叉树的存储结构n); printf( 2.求二叉树指定结点的路径n);printf( O.Exit System!n); printf(=n); printf( 请选择:(0-2)n);scanf(%d”,&xz); getc

12、har(); switch(xz) case 1:printf( 输 入二叉树的先序序列结点值:n); CreateBiTree(bt); printf(二叉树的链式存储结构建立完成！ n); printf(n); break;case 2:printf(路径的节点值是：n); ch1=getchar();p=NULL; found=0; Findx(bt,ch1); if(p!=NULL) - 10 - NodePath(bt,p); else printf(没有要求的节点!n);printf(n); break; / switch / while 源程序：#include #include

13、 #define num 100 #define OK 1 typedef int Status; typedef char DataType; typedef struct node DataType data; struct node*lchild,*rchild; BinTNode,*BinTree; int found; BinTNode*p; Status CreateBiTree(BinTree &bt) - 11 - char ch;printf(ch=); scanf(%c”,&ch); getchar(); if (ch=)bt=NULL; else bt=(BinTNode

14、 *)malloc(sizeof(BinTNode); bt-data=ch; /生成根结点 CreateBiTree(bt-lchild); / 构造左子树 CreateBiTree(bt-rchild); /构造右子树 returnOK; void NodePath(BinTree bt,BinTNode *ch) / 求二叉 树根结点到给定结点 *p的路径typedef enum FALSE,TRUEboolean; BinTNode *stacknum; / 定义栈 int tagnum; int i,top; boolean find; BinTNode *s;find=FALSE;

15、 top=0; s=bt; - 12 - do while(s!=NULL) / 扫描左子树 top+; stacktop=s; tagtop=0;s=s-lchild; if(top0) s=stacktop; if(tagtop=1) if(s=ch) / 找到ch,则显示从根结点到 ch的路径 for(i=1;i%c,stacki-data);find=TRUE; else top-; s=stacktop; /endif if(top0& !find) - 13 - if(tagtop!=1) s=s-rchild; /扫描右子树 tagtop=1; elses=NULL; /endi

16、f /endlif while(!find & top!=0); void FindBT(BinTree bt,DataType x) if(bt!=NULL) & !found) if(bt-data=x) p=bt;found=1; else FindBT(bt-lchild,x); /遍历查找左子树FindBT(bt-rchild,x); / 遍历查找右子树 - 14 - BinTNode *Findx(BinTree bt,DataType x) /按给定值查找结点int found=0; / 用found来作为是否查找到的标志 BinTree p=NULL; / 置空指针 FindB

17、T(bt,x); return(p); int main() bool isStop; BinTree bt; char ch1; int xz=1;printf(t*n，)； printf(t *ttttttt *n); printf(t*tt 欢迎来到这里 tt *n); printf(t * t t建立二叉树并求指定结点路径 t t *n); printf(t *ttttttt *n);printf(t*n); - 15 - while(xz) /*输生菜单，功能* printf(n n); printf(=n); printf( 1.建立二叉树的存储结构n); printf( 2.求二

18、叉树指定结点的路径n); printf(0.Exit System!n); printf(=n); printf( 请选择:(0-2)n);scanf(%d,&xz); getchar(); switch(xz) case 1:printf( 输 入二叉树的先序序列结点值 :n); CreateBiTree(bt); printf( 二叉树的链式存储结构建立完成！ n); printf(n); break;-16 - case 2:printf( 路径的节点值是：n); ch1=getchar();p=NULL; found=0; Findx(bt,ch1); if(p!=NULL) Node

19、Path(bt,p); else printf(没有要求的节点!n);printf(n); break; switch while 5. 测试结果 -17 -18 - 6.调试分析 本设计是先序输入的，当然也可以中序和 后序输入，为了减小时间和空间复杂度，所以只设计了先序 输入。对于先序，中序，后序等访问，需要的话，也可以 按要求加入。本设计的缺点是，输错了的话，要重新输入。7.设计体会 虽然都说 程序=数据结构+算法”，但我们在学 习运用数据结构编程之前，并没能深刻体会到这一点，直到 这次课设实践。我们感受最深的一点是：以 前用C编程， 只是注重如何编写函数能够完成所需要的功能，似乎没有明

20、确的战术，只是凭单纯的意识和简单的语句来堆砌由一段程 序。还体会到深刻理解数据结构的重要性。只有真正理解 这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。以前对递归算法一直很害怕，总是看不明白究竟这 递归是怎么进行的。在这次实验中终于克服了这一障碍，一 次次单步执行书中递归函数的例子，并一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！同时 还根据自己的理解写生了类似的递归函数实现了新的功能， 真是受 益良多啊！在这次实验中，对参数的调用也进行了 很多种尝试，已差不多经能够选择合适的参数形式来实现函 数之间的数据传输交

21、互了。这次实验中也由现过一些比较严重的错误。在主函数调用CreateBiTree (&bt)的参数&bt误 写成元素bt,在调试程序时给我们团队带来一定的封面山东建筑大学2009级工程造价专业毕业设计任务书题 目：山东省职业技术学院办公楼工程项目商务标书设计期限：自2011年7月至2011年10月班 级： 0720913141学生姓名：学 号：指导教师（签字）：任成友庄春华山东建筑大学毕业设计任务书班级学生姓名指导教师张琳设计题目山东省职业技术学院办公楼工程项目商务标书计始数 设原参1、工程概况山东省职业技术学院办公楼项目概况：(1)建设单位：建达房地产升发有限公司2)本工程为办公楼，具体位置

22、详见规划总平面图3)本工程总建筑面积5195.74平方米4)本工程五层，一层层图4.2m,二-四层图3.9m,五层层图4.2m, 建度 29.74m,室内外展 0.60m。5)本工程结构形式：框架结构，抗震设防烈度：6度6)本工程建筑等级：三级；耐火等级：为二级。7)本工程设计使用年限：3类(合理使用50年)8)屋间防水等级：二级2、工程特点本工程为重点工程，业主要求尽量采用施工新技术并要求必须按合 同工期完工。施工现场狭小，应考虑合理利用现场空间。3、资金筹措条件(D工程合同价c=a程报价；(2)开工前业主拨付工程备料款 A=20% C;(3)工程进度款，每月末按形象进度延迟一个月拨付；(4

23、)不足部分通过银行贷款补足，贷款利率 =12%(单利)；(5) /、考虑保修金的留设。(6)现场条件：已实现三通一平.(7)工程量清单(8)施工图(另附)设计 工作 内容1、撰写招标文件，编制工程量清单以施工图纸为依据，根据国家标准建设工程工程量清单计价规 范、及山东省现行消耗量定额进行编制。鼓励学生在完成手工预算的 全部工作的基础上，另用工程造价编制软件对手算的结果进行校审复 核。工程量清单编制的内容后；(1)均回；(2)总说明；(3)分部分项，程量清单；(4)措施项目清单；(5)其他项目清单；2、编制投标文件投标文件只编写商务标部分(1)商务部分主要包括卜列内容：1)投标函：2)建安工程唱

24、标单；3）法定代表人资格证明书；4）法定代表人授权书；5）投标保证金。6）报价单（2）商务标编制：计算工程量；确定综合单价；进行投标报价；编制 报价汇总表，和各类投标报价单价表。投标报价说明；投标报价汇总表；主要材料清单报价表；分部分项 工程量清单报价表；措施项目报价表；其他项目报价表；规费与税金工 程量清单项目报价表。1、毕业设计程序的要求（1）设计准备阶段毕业设计题目选定后，应由指导教师向学生下达毕业设计指导书。 学生根据毕业设计指导书的选题和指导教师的安排，应该做好如下的准 备，包括：认真阅读毕业设计任务书的内容，熟悉施工图纸，调查了解 与设计内容相关的资料；收集相关的工具书。包括设计规范、施工规范、 预算定额、工程估价