《二叉树的建立和遍历等操作报告》由会员分享，可在线阅读，更多相关《二叉树的建立和遍历等操作报告（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告1 *大学电子与信息工程学院数据结构课程设计报告( 2011 2012年度第一学期 )课程名称：数据结构课程设计题目：建立二叉树并求指定结点路径院系：电信学院计算机科学系班级：09 软件 班姓名：学号：指导教师：成绩：2011 年 12 月 10 日数据结构课程设计报告2 成 绩 评 定一、 指导教师评语二、 成绩成绩备注指导教师：日期：年月日数据结构课程设计报告3 题目建立二叉树并求指定结点路径、深度、叶子个数和左右子树交换。 问题描述 要求能够按先序遍历次序输入二叉树中结点的值来构造二叉树T； 然后用递归和非递归算法实现二叉树 T 的中序遍历； 接着编写算法实现求二叉树
2、T中指定结点的路径， 即从键盘输入二叉树 T 的任一结点，可以输出从根结点到该结点所经历的结点；最后编写二叉树的三个应用算法 （求二叉树的深度、 求二叉树的叶子结点个数、 将二叉树左右子树交换） 。 基本要求 分别建立二叉树存储结构的输入输出函数、输出中序遍历函数、指定节点路径函数、求深度函数、求叶子个数函数和将二叉树左右子树交换函数一、需求与规格说明1、定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树 T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树，建立如下图所示的二叉树。应该在程序运行窗
3、口的主控菜单后，先选择“1”并回车，紧接着在程序运行窗口中提示信息“输入二叉树的先序序列结点值: ”之后，采用以下字符序列：abcdegf（以替代空格，但是程序中直接输入空格就是，详细见代码注释）作为建立二叉树T 的输入字符序列并回车，窗口出现：二叉树的链式存储结构建立完成! 图 1 二叉树的图形结构2、二叉树的遍历。本系统采用非递归中序遍历算法进行中序遍历，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。需要在程序运行窗口的主控菜单中选择“2” 并回车，程序运行窗口会出现以下中序遍历序列：该二叉树数据结构课程设计报告4 的中序遍历序列是 : cbegdfa 3
4、、求二叉树的指定结点路径。在程序运行窗口的主控菜单中选择“3” 并回车，在程序运行窗口中提示信息“输入要求路径的结点值 : ”输入“ g” 并回车，会得到结果为：abdeg 如果输入“ i” 并回车，会得到结果为：没有要求的结点！4、求二叉树的深度。在程序运行窗口的主控菜单中选择“4” 并回车，在会得到结果为：该二叉树的深度为： 5 5、求二叉树的叶子结点个数。在程序运行窗口的主控菜单中选择“5” 并回车，在会得到结果为： 该二叉树的叶子结点数为：3 6、将二叉树左右子树交换（此处我用交换后的中序遍历来检验是否成功）。在程序运行窗口的主控菜单中选择“6” 并回车 . 得到结果为： 该二叉树的左
5、右节点已交换成功，其中序遍历序列是： afdgebc 7、退出程序。在程序运行窗口的主控菜单中选择“0” 并回车。退出程序。二、设计1、设计思想在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求（求路径）；但采用后序遍历二叉树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺序栈中，然后再输出即可。因此，我们可以非递归地后序遍历二叉树T，当后序遍历访问到结点 *p 时，此时栈中存放的所有结点均为给定结点*p 的祖先，而由这些祖先便构成了一条从根结点到结点 *p 之间的路径。而求二叉树的深度和叶子结
6、点数可以直接判断结点孩子的数目来完成，将二叉树的左右子树交换也可以利用递归的方法，交换左右孩子来实现。2、设计表示为实现上述的设计思想，首先要定义二叉树的链式存储结构，我们采用二叉链表的方式，相应的类型说明为：typedef char DataType; typedef struct node DataType data; struct node *lchild,*rchild; BinTNode,*BinTree; 数据结构课程设计报告5 函数接口说明 : Status CreateBiTree(BinTree typedef char DataType; typedef struct no
7、de DataType data; struct node *lchild,*rchild; BinTNode,*BinTree; int found; BinTNode *p; Status CreateBiTree(BinTree printf(“ch=“); scanf(“%c“, getchar(); if (ch= ) bt=NULL; / 程序中直接输入空格，不用以代替空格。数据结构课程设计报告7 else bt=(BinTNode *)malloc(sizeof(BinTNode); bt-data=ch; /生成根结点CreateBiTree(bt-lchild); /构造左子
8、树CreateBiTree(bt-rchild); /构造右子树 return OK; Status Inorder(BinTree bt) /二叉树非递中序遍历算法 BinTNode *stacknum; /定义栈数组int top=0; /初始化栈stacktop=bt; do while(NULL!=stacktop) / 扫描根结点及其所有的左结点并入栈 top=top+1; stacktop=stacktop-1-lchild; top=top-1; /退栈if(top=0) /判断栈是否为空 printf(“%c“,stacktop-data); /访问结点stacktop=sta
9、cktop-rchild; /扫描右子树 while(top=0); return OK; BinTree NodePath(BinTree bt, BinTNode *ch) /3.求二叉树指定结点的路径 typedef enumFALSE,TRUEboolean; BinTNode *stacknum;/ 定义栈int i,top,tagnum; boolean find; BinTNode *s; find=FALSE;/ 初始化数据结构课程设计报告8 top=0; s=bt; do while(s!=NULL) top+; stacktop=s; tagtop=0; s=s-lchil
10、d; if(top0) s=stacktop; if(tagtop=1) if(s=ch) for(i=1;i%c“,stacki-data); find=TRUE; else top-; s=stacktop; /endif if(top0/扫描右子树tagtop=1; else s=NULL; /end if /endif while(!find return s; void FindBT(BinTree bt,DataType x) if(bt!=NULL) found=1; else FindBT(bt-lchild,x); FindBT(bt-rchild,x); BinTNode
11、*Findx(BinTree bt,DataType x) int found=0; BinTree p=NULL; FindBT(bt,x); return(p); int Depth(BinTree bt) /4.求二叉树的深度 int h,lh,rh; if (bt=NULL) h=0; else lh=Depth(bt-lchild); rh=Depth(bt-rchild); if (lh=rh) h=lh+1; else h=rh+1; return h; /Depth int Leaf(BinTree bt) /5.求二叉树的叶子结点个数 if (bt=NULL) return
12、0; else if (bt-lchild=NULL else return Leaf(bt-lchild)+Leaf(bt-rchild); /Leaf 数据结构课程设计报告10 BinTNode *huhuan(BinTNode *p) /将 p 指针指向的二叉树的左右子树进行互换。BinTNode *stacknum;/ 指针类型的堆栈int k=0; stackk=NULL; if(p!=NULL)/ 交换 p 结点的左右孩子 k+; stackk=p-lchild; p-lchild=p-rchild; p-rchild=stackk; p-lchild=huhuan(p-lchil
13、d); p-rchild=huhuan(p-rchild); return (p); void main() BinTree bt; /BinTNode *root; char ch1; int xz=1,sd=0,yz=0; while(xz) printf(“ 建立二叉树并求指定结点路径n“); printf(“=n“); printf(“ 1.建立二叉树的存储结构n“); printf(“ 2.求解二叉树的中序遍历n“); printf(“ 3.求二叉树指定结点的路径n“); printf(“ 4.求二叉树的深度n“); printf(“ 5.求二叉树的叶子结点个数n“); printf
14、(“ 6.将二叉树左右子树交换n“); printf(“ 0.退出系统n“); printf(“=n“); printf(“ 请选择： (0-6) n“); 数据结构课程设计报告11 scanf(“%d“, getchar(); switch(xz) / 输入:ABCDEGF 输出: CBEGDFA case 1:printf(“输入二叉树的先序序列结点值:n“); CreateBiTree(bt); printf( “二叉树的链式存储结构建立完成!n“); break; case 2:printf(“该二叉树的中序遍历序列是:n“); Inorder(bt); printf( “n“); b
15、reak; case 3:printf( “请输入要求路径的结点值：n“ ); ch1=getchar(); p=NULL; found=0; Findx(bt,ch1); if(p!=NULL) NodePath(bt,p); else printf( “ 没有要求的节点！n“ ); printf( “n“ ); break; case 4:sd=Depth(bt); printf( “该二叉树的深度为： %d n “,sd ); printf(“n“); break; case 5:yz=Leaf(bt); printf( “该二叉树的叶子节点数为：n%d n“,yz ); printf( “n“ ); break; 数据结构课程设计报告12 case 6: bt=huhuan(bt); printf( “该二叉树的左右结点已交换成功，其中序遍历序列是:n“ ); Inorder(bt); printf( “n“ ); break; / switch / while 六、运行结果截图数据结构课程设计报告13 数据结构课程设计报告14 参考文献：1 严蔚敏
