C语言程序设计--------二叉树的遍历

C语言综合实验设计报告题目：数据结构：二叉树的遍历学院:化学工程学院专业:制药工程班级:050607学号：20051643姓名：李宏昊设计日期:2007年1月11日指导老师：顾煜新一选题背景数据结构是由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。由关系不同可将数据结构分为四类：线性结构、树形结构、图状结构和集合结构。数据的存储结构是数据逻辑结构在计算机中的映象，由关系的两种映象方法可得到两类存储结构：一类是顺序存储结构，它以数据元素相对的存储位置表示关系，则存储结构中只包含数据元素本身的信息；另一类是链式存储结构，它以附加的指针信息（后继元素的存储地址）表示关系。数据结构课程是离散数学的后续课程，并是操作系统、编译原理、数据库系统、计算机算法设计与分析、计算机网络、软件工程、人工智能等的基础课程，是将来进行大型程序设计的一个训练过程。二设计思想通过调用函数的方法进行二叉树的遍历，定义坐标固定结点的位置。自动建立树和手动建立树的标志,选择：2手动,1自动。文本模式下创建树的过程，如果选择1自动，电脑自动建立树，如果选择2手动，，需要人工手动建立。手动提示输入结点，创建好树。再用图形显示创建好的树，进行先序，中序，后序遍历。遍历时显示每个结点的过程。最后关闭图形。三主要问题的解决方法及技术关键存在的主要问题是在手动创建树时怎样输入结点，当选择“人工手动建立”时，在提示后依次输入26个字符或数字，每行一个。此时树就能建立，然后用图形显示出来。本程序的技术关键是建立二叉树和图形显示遍历的过程，分别用到Tree*CreatTree(),VoidDrawTree(Tree*t)等函数。遍历结束后，图形关闭。四流程图开始主函数文本模式下创建树选择常量2常量1Printf()Root=InitTree()调用函数Tree*InitTree()图形显示创建的树五程序清单/********tree2.c二叉树演示********/图形初始化图形关闭END遍历时显示结点的过程前序遍历中序遍历后序遍历#includegraphics.h#includestdio.h#includestdlib.h#includedos.h#includetime.htypedefstructTREE{chardata;/*树的结点数据*/structTREE*lchild;structTREE*rchild;intx;/*树的x坐标*/inty;/*树的y坐标*/}Tree;structOUTPUT{intx;/*三种遍历的x坐标*/inty;/*三种遍历的y坐标*/intnum;}s;intnodeNUM=0;/*统计当前的结点数字,最多26个*/charway;/*自动建立树和手动建立树的标志,2手动,1自动*/charstr[3];/*显示结点数据的字符串*/voidInit();/*图形初始化*/voidClose();/*图形关闭*/Tree*CreatTree();/*文本模式下创建树的过程*/Tree*InitTree(inth,intt,intw);/*创建树,h层次,t横坐标,w树之间的宽度,n树的建立方式*/voidDrawTree(Tree*t);/*用图形显示创建好的树*/voidPreorder(Tree*t);/*前序遍历*/voidMidorder(Tree*t);/*中序遍历*/voidPosorder(Tree*t);/*后序遍历*/voidDrawNode(Tree*t,intcolor);/*遍历时显示每个结点的过程*/voidClrScr();/*清空树的区域*/voidmain(){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);/*中序遍历*/getch();ClrScr();DrawTree(root);sleep(1);s.x=100;s.y=400;s.num=1;Posorder(root);/*后序遍历*/Close();}/*清空树的区域*/voidClrScr(){setcolor(BLACK);setfillstyle(SOLID_FILL,BLACK);bar(0,20,640,280);}/*文本模式下创建树的过程*/Tree*CreatTree(){Tree*root;clrscr();printf(pleaseinputn\n);printf(1.computercreat\n);printf(2.peoplecreat\n);way=getch();/*输入创建树的方法,1电脑自动建立,2人工手动建立*/if(way!='2')way='1';/*其他数字默认自动建立*/if(way=='2')/*手动建立提示输入结点*/printf(Pleasecreatthetree\n);root=InitTree(1,320,150);system(pause);returnroot;}/*生成二叉树，h表示层次，t表示横坐标，w表示结点左右子树的宽度，随机数n确定结点是空或非空，如n为0，则为空*，但要限定确保结点数不少于三个*/Tree*InitTree(inth,intt,intw){charch;intn;/*自动建立时随机赋值判断是否是NULL的标志*/Tree*node;if(way=='2')/*手动建立需要自己输入*/scanf(%c,&ch);else/*自动建立的赋值*/{n=random(5);if(n==0&&nodeNUM=3)/*随机赋值时候确保自动建立的二叉树有三个结点*/ch='.';elsech=65+random(25);}if(ch=='.')/*输入空格代表NULL*/returnNULL;else{if(h==6||nodeNUM==26)/*如果树的层次已经到5或者结点树到达26个就自动返回NULL*/returnNULL;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);}returnnode;}/*用图形显示创建好的树*/voidDrawTree(Tree*t){if(t!=NULL){setcolor(BLACK);setfillstyle(SOLID_FILL,BLACK);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-rchild-y-12);DrawTree(t-rchild);}}}/*遍历时显示每个结点的过程*/voidDrawNode(Tree*t,intcolor){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);sprintf(str,%d,s.num);/*将遍历次序用数字显示在树的结点上*/outtextxy(t-x-3,t-y-20,str);s.num++;sleep(1);}/*前序遍历*/voidPreorder(Tree*t){if(t!=NULL){s.x+=15;DrawNode(t,GREEN);Preorder(t-lchild);Preorder(t-rchild);}}/*中序遍历*/voidMidorder(Tree*t){if(t!=NULL){Midorder(t-lchild);s.x+=15;DrawNode(t,YELLOW);Midorder(t-rchild);}}/*后序遍历*/voidPosorder(Tree*t){if(t!=NULL){Posorder(t-lchild);Posorder(t-rchild);s.x+=15;DrawNode(t,BLUE);}}/*图形初始化*/voidInit(){intgd=DETECT,gm;initgraph(&gd,&gm,c:\\tc);cleardevice();setcolor(YELLOW);outtextxy(250,10,anykeytocontinue);setcolor(RED);outtextxy(20,300,preorder);outtextxy(20,350,midorder);outtextxy(20,400,posorder);getch();}/*图形关闭*/voidClose(){getch();closegraph();}六设计结果说明本程序主函数简洁易懂，用了坐标设定树结点的位置，使运算方便。设置了选择功能，其中自动创建起着示范作用，还显示出程序的自动化程度。调用了众多功能函数，且函数表达较详细。用图形显示了遍历的经过使人更好地明白二叉树的遍历。不足的是在手动建立树时，没有清楚说明运用的变量的性质，让使用者在输入数据时产生疑惑，且有些具体函数的作用没有很好的体现。