C语言综合实验设计报告数据结构：二叉树的遍历

1、c语言综合实验设计报告 题目：数据结构：二叉树的遍历 学院:化学工程学院 专业:制药工程 班级:050607 学号： 姓名： 设计日期:2007年1月11日 指导老师： 一 选题背景数据结构是由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。由关系不同可将数据结构分为四类：线性结构、树形结构、图状结构和集合结构。数据的存储结构是数据逻辑结构在计算机中的映象，由关系的两种映象方法可得到两类存储结构：一类是顺序存储结构，它以数据元素相对的存储位置表示关系，则存储结构中只包含数据元素本身的信息；另一类是链式存储结构，它以附加的指针信息（后继元素的存储地址）表示关系。数据结构课程是离散

2、数学的后续课程，并是操作系统、编译原理、数据库系统、计算机算法设计与分析、计算机网络、软件工程、人工智能等的基础课程，是将来进行大型程序设计的一个训练过程。二 设计思想通过调用函数的方法进行二叉树的遍历，定义坐标固定结点的位置。自动建立树和手动建立树的标志,选择：2手动,1自动。文本模式下创建树的过程，如果选择1自动，电脑自动建立树，如果选择2手动，需要人工手动建立。手动提示输入结点，创建好树。再用图形显示创建好的树，进行先序，中序，后序遍历。遍历时显示每个结点的过程。最后关闭图形。三 主要问题的解决方法及技术关键 存在的主要问题是在手动创建树时怎样输入结点，当选择“人工手动建立”时，在提示后

3、依次输入26个字符或数字，每行一个。此时树就能建立，然后用图形显示出来。本程序的技术关键是建立二叉树和图形显示遍历的过程，分别用到tree *creattree(),void drawtree(tree *t)等函数。遍历结束后，图形关闭。四 流程图开始主函数文本模式下创建树选择常量2常量1printf()root=inittree()调用函数tree*inittree()图形显示创建的树前序遍历 中序遍历遍历时显示结点的过程后序遍历图形初始化图形关闭end五 程序清单/*tree2.c二叉树演示*/#include #include #include #include #include ty

4、pedef struct tree char data;/*树的结点数据*/ struct tree *lchild; struct tree *rchild; int x;/*树的x坐标*/ int y;/*树的y坐标*/tree;struct output int x;/*三种遍历的x坐标*/ int y;/*三种遍历的y坐标*/ int num;s;int nodenum=0;/*统计当前的结点数字,最多26个*/char way;/*自动建立树和手动建立树的标志,2手动,1自动*/char str3;/*显示结点数据的字符串*/void init();/*图形初始化*/void clo

5、se();/*图形关闭*/tree *creattree();/*文本模式下创建树的过程*/tree *inittree(int h,int t,int w);/*创建树,h层次,t横坐标,w树之间的宽度,n树的建立方式*/void drawtree(tree *t);/*用图形显示创建好的树*/void preorder(tree *t);/*前序遍历*/void midorder(tree *t);/*中序遍历*/void posorder(tree *t);/*后序遍历*/void drawnode(tree *t,int color);/*遍历时显示每个结点的过程*/void clrs

6、cr();/*清空树的区域*/void main() tree *root; randomize(); root=creattree();/*创建树*/ init(); drawtree(root);/*每次遍历前显示白色的树*/ sleep(1); s.x=100;s.y=300;s.num=1;/*每次遍历前设置显示遍历顺序显示的x,y坐标*/ preorder(root);/*前序遍历*/ getch(); clrscr(); drawtree(root); sleep(1); s.x=100; s.y=350; s.num=1; midorder(root);/*中序遍历*/ getc

7、h(); clrscr(); drawtree(root); sleep(1); s.x=100; s.y=400; s.num=1; posorder(root);/*后序遍历*/ close();/*清空树的区域*/void clrscr() setcolor(black); setfillstyle(solid_fill,black); bar(0,20,640,280);/*文本模式下创建树的过程*/tree *creattree() tree *root; clrscr(); printf(please input nn); printf(1.computer creatn); pr

8、intf(2.people creatn); way=getch();/*输入创建树的方法,1电脑自动建立,2人工手动建立*/ if(way!=2) way=1;/*其他数字默认自动建立*/ if(way=2)/*手动建立提示输入结点*/ printf(please creat the treen); root=inittree(1,320,150); system(pause); return root;/*生成二叉树，h表示层次，t表示横坐标，w表示结点左右子树的宽度，随机数n确定结点是空或非空，如n为0，则为空*，但要限定确保结点数不少于三个*/tree *inittree(int h,

9、int t,int w) char ch; int n;/*自动建立时随机赋值判断是否是null的标志*/ tree *node; if(way=2)/*手动建立需要自己输入*/ scanf(%c,&ch); else/*自动建立的赋值*/ n=random(5); if(n=0&nodenum=3)/*随机赋值时候确保自动建立的二叉树有三个结点*/ ch=.; else ch=65+random(25); if(ch=.)/*输入空格代表null*/ return null; else if(h=6|nodenum=26)/*如果树的层次已经到5或者结点树到达26个就自动返回null*/ r

10、eturn null; node=(tree*)malloc(sizeof(tree); node-data=ch; node-x=t;/*树的x坐标是传递过来的横坐标*/ node-y=h*50;/*树的y坐标与层次大小有关*/ nodenum+; node-lchild=inittree(h+1,t-w,w/2); node-rchild=inittree(h+1,t+w,w/2); return node;/*用图形显示创建好的树*/void drawtree(tree *t) if(t!=null) setcolor(black); setfillstyle(solid_fill,bl

11、ack); fillellipse(t-x,t-y,9,9); setcolor(white); circle(t-x,t-y,10); /*画圆*/ sprintf(str,%c,t-data);/*将内容转换成字符串输出*/ outtextxy(t-x-3,t-y-2,str); if(t-lchild!=null)/*左子树*/ line(t-x-5,t-y+12,t-lchild-x+5,t-lchild-y-12); drawtree(t-lchild); if(t-rchild!=null)/*右子树*/ line(t-x+5,t-y+12,t-rchild-x-5,t-rchil

12、d-y-12); drawtree(t-rchild); /*遍历时显示每个结点的过程*/void drawnode(tree *t,int color) setcolor(yellow); setfillstyle(solid_fill,yellow); fillellipse(t-x,t-y,10,10); setcolor(red); sprintf(str,%c,t-data);/*将内容转换成字符串输出*/ outtextxy(t-x-3,t-y-2,str); setcolor(color); outtextxy(s.x,s.y,str); setcolor(red); sprin

13、tf(str,%d,s.num);/*将遍历次序用数字显示在树的结点上*/ outtextxy(t-x-3,t-y-20,str); s.num+; sleep(1);/*前序遍历*/void preorder(tree *t) if(t!=null) s.x+=15; drawnode(t,green); preorder(t-lchild); preorder(t-rchild); /*中序遍历*/void midorder(tree *t) if(t!=null) midorder(t-lchild); s.x+=15; drawnode(t,yellow); midorder(t-rc

14、hild); /*后序遍历*/void posorder(tree *t) if(t!=null) posorder(t-lchild); posorder(t-rchild); s.x+=15; drawnode(t,blue); /*图形初始化*/void init() int gd=detect,gm; initgraph(&gd,&gm,c:tc); cleardevice(); setcolor(yellow); outtextxy(250,10,anykey to continue); setcolor(red); outtextxy(20,300,preorder); outtextxy(20,350,midorder); outtextxy(20,400,posorder); getc