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

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

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

3、de 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 - typedefstruct node DataType data; struct node*lchild,*rchild; BinTNode,*BinTree;（ 2）建立二叉树创建二叉链表存储的二叉树。按二叉树带空指针的先序次序输入结点值，结点类型为字符型。按先序次序输入，其中 “”表示空结点。算法是按照先序遍历思想设计的。构造二叉链表表示的二叉树，“”符号表示空树。具体实现方法如下：Status CreateBiTree(BinTree &bt) char ch; printf(&qu

6、ot;ch=");scanf("%c",&ch); getchar(); if (ch='') bt=NULL; else bt=(BinTNode *)malloc(sizeof(BinTNode); bt->data=ch;/ 生成根结点CreateBiTree(bt->lchild); /构造左子树CreateBiTree(bt->rchild); /构造右子树 return OK; （ 3）查找函数- 5 -函数功能是用递归方法对二叉树进行先序遍历查找，调用此函数可以返回二叉树中指定目标结点。算 法思想：若找到目标

7、结点，则返回该目标结点；否则访问二叉树的根结点；先序遍历根的左子树；先序遍历根的右子树。具体实现方法如下： 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); /遍历查找右子树 BinTNode *Findx(BinTree bt,DataType x) /按给定值查找结点 int found=0; /用 found来作为是否

8、查找到的标志BinTree p=NULL; /置空指针 FindBT(bt,x); return(p); 7）求指定结点路径：该函数功能是根据已创建的二叉树和输入的目标结点，调用此函数可以查找并输出目标结点的路径。算法思想：根据先序遍历二叉树的递归定义，采用一个指针数组来保存返回的结点。先扫描根结点的左子树上的结点并写入指针数组。判断该结点是否与指定目标结点相等，若不相等，然后扫描该结点的右结点并写-6-入指针数组，再扫描该右结点的所有左结点写入指针数组。当一个结点的左孩子树均访问完后再访问该结点，并与给定的结点比较。若相等，则循环输出指针数组中的所有元素，而这个顺序值就是要求的路径。若不相等

9、，则继续上述过程。具体实现方法如下：void NodePath(BinTree bt,BinTNode*ch) / 求二叉树根结点到给定结点 *p 的路径 typedefenum 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(top>0) s=stack

10、top; if(tagtop=1) - 7 - if(s=ch)/ 找到 ch, 则显示从根结点到 ch 的路径for(i=1;i<=top;i+) printf("->%c",stacki->data); find=TRUE; else top-; s=stacktop; /endif if(top>0&& !find) if(tagtop!=1) s=s->rchild; / 扫描右子树 tagtop=1; else s=NULL; /endif /endlif while(!find&& top!=0);

11、（8）主函数：- 8 -该函数为程序的主函数功能是循环输出菜单，功能界面；从界面获取功能菜单中对应的字符，通过switch() 语句实现对函数的调用，进而实现功能。具体代码如下：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(&qu

12、ot;t *ttttttt *n");printf("t*n"); while(xz) /*输出菜单 ,功能 */printf("n n"); printf("=n"); - 9 - printf(" 1.建立二叉树的存储结构n"); printf(" 2.求二叉树指定结点的路径n");printf(" 0.Exit System!n"); printf("=n"); printf("请选择:(0-2)n");scanf(&q

13、uot;%d",&xz); getchar(); 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 pr

14、intf("没有要求的节点 !n");printf("n"); break; / switch / while 源程序：#include #include #define num 100 #define OK 1 typedefint Status; typedef char DataType; typedef structnode DataType data; struct node*lchild,*rchild; BinTNode,*BinTree; int found; BinTNode*p; Status CreateBiTree(BinTree

15、 &bt) - 11 - char ch;printf("ch="); scanf("%c",&ch); getchar(); if (ch='')bt=NULL; else bt=(BinTNode *)malloc(sizeof(BinTNode);bt->data=ch; /生成根结点CreateBiTree(bt->lchild); /构造左子树 CreateBiTree(bt->rchild); /构造右子树 returnOK; void NodePath(BinTree bt,BinTNode

16、 *ch) /求二叉树根结点到给定结点*p 的路径 typedef enumFALSE,TRUEboolean; BinTNode *stacknum; /定义栈int tagnum; int i,top; boolean find; BinTNode *s;find=FALSE; top=0; s=bt; - 12 - do while(s!=NULL) /扫描左子树 top+; stacktop=s; tagtop=0;s=s->lchild; if(top>0) s=stacktop; if(tagtop=1) if(s=ch) /找到 ch, 则显示从根结点到ch 的路径f

17、or(i=1;i<=top;i+) printf("->%c",stacki->data); find=TRUE; else top-; s=stacktop; /endif if(top>0&& !find) - 13 - if(tagtop!=1) s=s->rchild; /扫描右子树 tagtop=1; elses=NULL; /endif /endlif while(!find && top!=0); void FindBT(BinTree bt,DataType x) if(bt!=NULL) &am

18、p;& !found) if(bt->data=x) p=bt;found=1; else FindBT(bt->lchild,x); /遍历查找左子树FindBT(bt->rchild,x); /遍历查找右子树BinTNode *Findx(BinTree bt,DataType x) /-14-按给定值查找结点int found=0; /用found来作为是否查找到的标志BinTree p=NULL; / 置空指针 FindBT(bt,x); return(p); int main() bool isStop; BinTree bt; char ch1; int

19、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(&qu

20、ot; 1.建立二叉树的存储结构 n"); printf(" 2.求二叉树指定结点的路径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)NodePath(bt,p); else printf(&