tree.c

本程序在WinTC下调试通过

/*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();
      }