tree.rar

/*2006.5.2 熊小辉 湖南理工学院物电楼506 本程序功能：直观的显示了二树的三种基本遍历方法。 */ #include<stdio.h> #include<math.h> #include<graphics.h> #include<dos.h> #include<stdlib.h> #include<time.h> //利用结构体创建树结点 typedef struct TREE { char data; //存储数据 struct TREE *lchild; //左孩子 struct TREE *rchild; //右孩子 int x; //树结点的坐标 int y; } tree; struct output { int x;//三种遍历的坐标 int y; int num; //遍历时是第几个结点。 }s; char str[5]; int nodenum=0;//统计当前结点的数目 void init(void); //图形的初始化 void close(void);//关闭图形 tree *inittree(int h,int t,int w);//建立二叉树 void showtree(tree *first); //显示树的函数 void posorder(tree *first); //前序遍历函数 void midorder(tree *first); //中序遍历函数 void preorder(tree *first); //后序遍历函数 //================================================================= //=========主函数==================================================== //================================================================== void main(void) { tree *node; init(); //图形初始化 node=inittree(1,320,150); //创建树 showtree(node); //树的显示 s.x=80; s.y=410; //字母显示的初始化 s.num=1; preorder(node); //前序遍历函数 getch(); clrscr(); //清屏 showtree(node); //显示初始化时的图形 s.x=80; s.y=430; //字母显示的初始化 s.num=1; midorder(node);//中序遍历 getch(); clrscr(); //清屏 showtree(node); //显示初始化时的图形 s.x=80; s.y=450; //字母显示的初始化 s.num=1; posorder(node); //后序遍历 close(); //关闭图形 } //======显示遍历每个结点的过程============================== void shownode(tree *first,int color) { setcolor(YELLOW); setfillstyle(SOLID_FILL,YELLOW); fillellipse(first->x,first->y,10,10); //将结点填充黄色 setcolor(4); sprintf(str,"%c",first->data); //用红色来填写字符 outtextxy(first->x-3,first->y-2,str); setcolor(color); outtextxy(s.x,s.y,str); //在字符序列表中加入遍历的字符 sprintf(str,"%d",s.num); outtextxy(first->x,first->y-10,str); //在结点旁边加上序列号 s.num++; } //======前序遍历函数========================================= void preorder(tree *first) { if(first!=NULL) { getch(); //实现逐个显示 s.x+=15; shownode(first,4); //显示当前结点 preorder(first->lchild); //利用递归法查询左子树 preorder(first->rchild); //利用递归查询右子树 } } //======= 中序遍历函数============================================= void midorder(tree *first) { if(first!=NULL) { midorder(first->lchild); //利用递归法查询左子树 getch(); //实现逐个显示 s.x+=15; shownode(first,6); midorder(first->rchild); //利用递归查询右子树 } } //======= 后序遍历============================================= void posorder(tree *first) { if(first!=NULL) { posorder(first->lchild); //利用递归法查询左子树 posorder(first->rchild); //利用递归查询右子树 s.x+=15; getch(); //实现逐个显示 shownode(first,4); } } //========后序遍历函数============================================= /* 生成二叉树，H 表示层次，T表示横坐标，W 表示结点左右子树的宽度，随机数N确定结点是否为空， 如果N为0，则为空，但要限定结点数不少于三个*/ tree *inittree(int h,int t,int w) { char ch; int n; tree *node; ch=65+random(25); { if(h==6||nodenum==40) return NULL; node=(tree*)malloc(sizeof(tree)); node->data=ch; node->x=t; node->y=h*50; nodenum++; //采用递归法建立树 node->lchild=inittree(h+1,t-w,w/2); node->rchild=inittree(h+1,t+w,w/2); } return node; } //========用图形显示建立的树========================== void showtree(tree *first) { if(first!=NULL) { setcolor(WHITE); circle(first->x,first->y,10); //画圆， //outtextxy(20,20,"a"); //用于测试符号 sprintf(str,"%c",first->data); outtextxy(first->x-3,first->y-2,str); if(first->lchild!=NULL)//左子树不为0 { //outtextxy(20,40,"b"); //用于测试符号 line(first->x-5,first->y+10,first->lchild->x+5,first->lchild->y-10); showtree(first->lchild); } if(first->rchild!=NULL) { // outtextxy(20,60,"c"); //用于测试符号 line(first->x+5,first->y+10,first->rchild->x-5,first->rchild->y-10); showtree(first->rchild); } } // else // outtextxy(20,80,"f"); //用于测试符号 } //==========关闭图形函数======================== void close(void) { getch(); closegraph(); } //===========图形初始化函数====================== void init(void) { int gdriver=DETECT,gmode; registerbgidriver(EGAVGA_driver); initgraph(&gdriver,&gmode,""); setbkcolor(0); cleardevice(); setcolor(5); outtextxy(230,10,"input any key to continue"); outtextxy(20,410,"preorder:"); outtextxy(20,430,"midorder:"); outtextxy(20,450,"posorder:"); getch(); }