建立二叉树并求指定结点路径

1、数据结构课程设计报告井冈山大学电子与信息工程学院数据结构课程设计报告 ( 20112012年度第一学期)课程名称： 数据结构课程设计 题 目： 建立二叉树并求指定结点路径 院 系： 计算机科学系 班 级： 09 软件班 姓 名： 学 号： 90913006 指导教师： 成 绩： 2011 年 12月 8日成 绩 评 定一、 指导教师评语二、 成绩成绩备注 指导教师： 日 期： 年 月 日题目 建立二叉树并求指定结点路径。问题描述 要求能够按先序遍历的次序输入二叉树的各个节点，并能够输出中序遍历的序列，以及指定点的路径 基本要求 分别建立二叉树存储结构的输入函数，输出中序遍历的函数，以及输出指定

2、节点路径的函数1需求与规格说明：1)定义二叉树的存储结构，每个节点设置三个域，即值域、左指针域、右指针域。要建立二叉树t的链式存储结构，即建立二叉链表。根据输入二叉树节点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树，建立如下图所示的二叉树。应该在程序运行窗口的主控菜单后，选择“1”并回车，紧接着在程序运行窗口中提示信息“输二叉树的先序序列节点值：”之后，采用以下字符序列：abcdegf（以代替空格）作为建立二叉树t的输入字符序列并回车，窗口出现：二叉树的链式存储结构建立完成！ 二叉树的图形结构2）二叉树的遍历。本系统采用非递归中序遍历算法进行中序遍历，这意味着遍历右子书时不再

3、需要保存当前的根指针，可直接修改栈顶记录的指针即可。需要在程序运行窗口的主控菜单中选择“2”并回车，程序运行窗口会出现以下中序遍历序列：该二叉树的中序遍历序列是：cbegdfa3)求二叉树的指定节点路径。在程序运行窗口的主控菜单中选择“3”并回车，在程序运行窗口中提示信息“输入要求路径的节点值：”输入“g”并回车，会得到结果为：-a-b-d-e-g如果输入“i”并回车，会得到结果为：没有要求的节点！2设计1）设计思想我们知道，在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求；但 采用后序遍历二叉树是可行的，因为后序遍历是

4、最后访问根结点，按这个顺序将 访问过的结点存储到一个顺序栈中，然后再输出即可。因此，我们可以非递归地 后序遍历二叉树t，当后序遍历访问到结点*p 时，此时栈中存放的所有结点均为 给定结点*p 的祖先，而由这些祖先便构成了一条从根结点到结点*p之间的路径。 （1）存储结构：二叉树的链式存储结构（2）主要算法基本思想。2）设计表示: 为实现上述的设计要求，首先要定义二叉树的链式存储结构，我们采用二叉 链表的方式，相应的类型说明为：typedef char datatype; typedef struct node datatype data; struct node *lchild,*rchild

5、; bintnode,*bintree;（1）函数接口说明:status createbitree(bintree &bt)/*按照先序遍历次序递归建立二叉树*/status inorder(bintree bt)/*二叉树非递归中序遍历算法*/voidn nodepath(binntree bt,bintnode*ch)*/求二叉树根节点到给定节点*p的路径*/ （2）函数调用关系如图所示：main（）createbitreeinordernodepath3）实现注释:二叉树的创建模块：按先序遍历次序递归建立二叉树，通过读入的字符，分配存储空间生成新节点后再逐个构建根节点、左子树和右子树。程

6、序代码可参考文献1p3算法6.4语句注释见附录代码。 二叉树中序遍历模块：采用非递归中序遍历算法，先逐步扫描二叉树的左子树，并压入堆栈，如果栈不为空，左子树为空，则弹出栈顶的一个元素并输出。然后再扫描右子树，然后再重复上面的步骤扫描该分支的左子树，直至整棵二叉树都完成扫描。此时输出的序列便是该二叉树的中序遍历序列。语句注释见代码。二叉树指定结点路径模块：该模块由nodepath、findbt、findx三个函数体构成，main函数通过先调用findx函数来查找结点，findx又通过逐步调用findbt函数遍历查找结点的路径，最后main函数在通过调用nodepath函数得到给定结点的路径。该模

7、块需定义全局变量p和found以方便查找，否则容易出错，出错情况见调试报告。语句注释见代码。3调试报告：编程的最初阶段，在case3语句中，缺少p=null;和found=0两个语句，得到的结果不管查找的结点是否存在，其结果均显示为g结点的路径，后经设置断点、调试，发现p指针在更换查找结点时，指向的地址始终与第一个查找的结点（即g）的地址相同，导致结果出错，所以应在ch1=getchar()；获取新结点之后令p指针为空。 在编程的后期，暂未考虑到found为全局变量，因此即使加上p=null;这条语句，得到的结果为第一次查找g结点正确、第二次查找i结点也正确，此后继续查找不管是否存在的结点，其

8、结果均与第二次的结果一致，显然此为错误的结果。经过调试判断后，得出found为全局变量，第一次查找存在的结点时，found被赋值为1，所以导致接下来的查找过程中在findbt函数中：if（bt!=null）&!found)，因为found已被赋值为1，所以，直接跳出查找退出findbt函数，也就是没进行查找，现实的结果均为没有找到！实际上根本就没进行查找！所以应补充语句found=0；以恢复初值。到此，程序正确！4程序清单和结果：#include #include #define num 100#define ok 1typedef int status;typedef char dataty

9、pe;typedef struct node datatype data; struct node *lchild,*rchild;bintnode,*bintree;int found;bintnode *p;status createbitree(bintree &bt) char ch; printf(ch=); scanf(%c,&ch); getchar(); if (ch=) bt=null; else bt=(bintnode *)malloc(sizeof(bintnode); bt-data=ch; /生成根结点 createbitree(bt-lchild); /构造左子树

10、 createbitree(bt-rchild); /构造右子树 return ok;status inorder(bintree bt)/二叉树非递归中序遍历算法 bintnode *p,*s100; /定义数组栈 int i=0; /初始化栈 p=bt; do while(p!=null) /扫描根结点及其所有的左结点并将其地址入栈 si+=p; p=p-lchild; if (i0) /判断栈是否为空 p=s-i; /出栈 printf(%ct,p-data); /访问结点 p=p-rchild; /扫描右子树 while(i0|p!=null); return ok;void node

11、path(bintree bt,bintnode *ch)/求二叉树根结点到给定结点*p的路径 typedef enum 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) if(s=ch) /找到ch,则显示从根结

12、点到ch的路径 for(i=1;i%c,stacki-data); find=true; 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);void findbt(bintree bt,datatype x) if(bt!=null) & !found) if(bt-data=x) p=bt;found=1; else findbt(bt-lchild,x); /遍历

13、查找左子树 findbt(bt-rchild,x); /遍历查找右子树 bintnode *findx(bintree bt,datatype x)/按给定值查找结点 int found=0; /用found来作为是否查找到的标志 bintree p=null; /置空指针 findbt(bt,x); return(p);void main() bool isstop; bintree bt; char ch1; int xz=1; while(xz) printf(建立二叉树并求指定结点路径n); printf(=n); printf(1.建立二叉树的存储结构 n); printf(n);

14、printf(2.求解二叉树的中序遍历 n); printf(n); printf(3.求二叉树指定结点的路径 n); printf(n); printf(0. 退 出 系 统 n); printf(=n); printf(请选择:(0-3) n); scanf(%d,&xz); getchar(); switch(xz) /输入:abdecf case 1:printf(输入二叉树的先序序列结点值:n); createbitree(bt); printf(二叉树的链式存储结构建立完成! n); printf(n); break; case 2:printf(该二叉树的中序遍历序列是:n); inorder(bt); printf(n); break; /查找指定结点路径 case 3:printf(路径的节点值是：n); ch1=getchar(); findx(bt,ch1); if(p!=null) nodepath(bt,p); else printf(没有要求的节点!n); printf(n); break; / switch / while结果截屏：图1.建立二叉树图3.