在linux svgalib环境下用c创建绘制二叉树的函数－建立自己的c数据结构与算法库系列(12)
夹谷星剑
前面我已经向大家介绍了怎么样安装linux下svgalib这个古老的图形库，为了方便演示后面一些有关二叉树的算法，现在就接着完成在linux控制台下绘制二叉树，实现放在一个函数中，函数目标：
1。给出任意一个二叉树t和一些函数指针，调用此函数即可在控制台下以图形打印此二叉树。
2。调用基本参数，二叉树 t，获取孩子节点的函数指针fgetChild,获取节点键值的函数指针fgetKey.
提示，关于svga一些入门的话，可以直接查看vga.h头文件，并且编译源代码的时候可以编译出许多很用的例子，在编译目录 下 demos文件夹下可以找到这些简单而有趣的例子，当然你也可以查相关的在线手册，我曾经看到一个英文的在线tutorials，但忘了地址了，可以google一下(估计百度不出来^_^)
一。算法分析：
先想像一下，我们把整个屏幕分成网格的逻辑，我们将在网格中一个个的放入二叉树的节点，绘制一个节点时，如果它有子节点，则再绘制相应的线段。
画图算法描述：
设要画的树高度为h（此时树有h+1层），画树要考虑到画布必须至少要有容纳得下满树的空间，则考虑满树时，
叶子节点个数为:2^h,则可以把每个层的横向空间分为2^h个基本单位(想像分割成正方形空间)，设此单位值为w,w=TreeWidth/2^h,节点可以画在线上或正方形垂直边上，
第i层(1<=i<=h+1)的节点数为,2^(i-1),因此，第i层可以被平均的分为2^(i-1)空间，每个空间取中点就是节点的位置。
对于第i层的每个节点的位置，他们的位置是：((2^h/2^(i-1))*j+(2^h/2^(i-1))*(j-1))/2=(2^h/2^(i-1))(2*j-1)/2=2^(h-i)*(2*j-1),j=1,2,..,2^(i-1),
如果节点画成圆，且对应上像素点，则得到最后每个节点的位置公式为：
(2^(h-i)*(2*j-1)*w,(i)*w),
(i=1,2,..,h+1 ;j=1,2,...,2^(i-1);w=TreeWidth/(2^h)),圆半径r=w/2
可以加个纵向上偏移，调整树的高度如：
(2^(h-i)*(2*j-1)*w,(i)*w+py)
(i=1,2,..,h+1 ;j=1,2,...,2^(i-1);w=TreeWidth/(2^h)),圆半径r=w/2
任意节点P（2^(h-i)*(2*j-1)*w，(i)*w）的左右孩子中心坐标分别为：
左孩子：L(2^(h-i)*(2*j-1)*w-(2^h/2^(i+1))*w,(i+1)*w)
右孩子：R(2^(h-i)*(2*j-1)*w+(2^h/2^(i+1))*w,(i+1)*w)
设线段PL与水平线夹角为a,则
tan(a)=1/(2^h/(2^(i+1))=1/(2^(h-i-1))
并且易得，PR与水平线的夹角等于a.
设PL与左孩子节点圆的交点为A，与节点圆P的交点为B,已经LA＝w／2,根据平面几何易得A的坐标为
(2^(h-i)*(2*j-1)*w+cos(a)*r-(2^(h-i-1))*w,(i+1)*w-sin(a)*r)
B坐标为：
(2^(h-i)*(2*j-1)*w-cos(a)*r,(i)*w+sin(a)*r)
而sin(a)=sqrt(tan(a)*tan(a)/(1+tan(a)*tan(a)))
cos(a)=sqrt(1/(1+tan(a)*tan(a)))
同时，设PR与P节点圆和R孩子的交点分别为C ,D；则C ，D坐标分别为
(2^(h-i)*(2*j-1)*w-cos(a)*r+(2^h/2^(i+1))*w,(i+1)*w-sin(a)*r)
(2^(h-i)*(2*j-1)*w+cos(a)*r,(i)*w+sin(a)*r)
要特别说明的是，1～h层的节点都处于正方形的垂直边上，而第h＋1层节点（叶子节点)正好处于正方形内，且正好用完第h＋1层的正方形。
还有一个关系需要理清楚，设当前节点处在树的每i层（从根算起)的第j个节点,则把树从根向叶子和从左向右排序号，当前节点的序号是
2^(i-1)+j,设它的左右孩子的层数和层数内的节点编号分别为 li,lj,ri,rj则有
li=ri=i+1;
lj=2*j-1
rj=2*j
二。代码。
下面代码经过测试，成功，只是svgalib库可能不太稳定。
我乐意帮助大家，q上我349871604我直接传代码。^_^
今天到此是为了早上买火车票，真是倒霉啊！
/*头文件drawBitTree.h*/
/********************************** *
*author:Felix
*last update:Mon Jan 14 11:51:31 EST 2008
*Address me and exchange our idea ^_^,QQ:349871604,e-mail:lzqziliao2004@163.com
*description:
*
*
*
*/
#ifndef ___DRAWBITTREE___
#define ___DRAWBITTREE___
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<vga.h>
#include<vgagl.h>
#define DB_GetWidth() 800
#define DB_GetHeight() 600
#define DB_LEFTCHILD 1
#define DB_RIGHTCHILD 2
/*a node's maximum area of retangle:**/
#define MAX_NODE 50
#define MIN_NODE 5
typedef void * DB_GetChild(void * p,int mode);
typedef int DB_GetKey(void * p);
/*
*t:the tree to be draw
*fgetKey:pointer to a funtion that return a key of a node
*fgetChild:pointer to a function that return a pointer to a left child of a node
*/
void DB_DrawBitTree(void * t, DB_GetChild fgetChild, DB_GetKey fgetKey);
#endif
/*实现文件*/
/*last update:Mon Jan 14 11:51:31 EST 2008
*Address me and exchange our idea ^_^,QQ:349871604,e-mail:lzqziliao2004@163.com
*description:
*
*
*
*/
#include "drawBitTree.h"
/**获取树的高度,fgetChild是一个函数指针，t是一个二叉树*/
static int DB_GetTreeHeight(void * t,DB_GetChild fgetChild);
/**在屏幕中画圆*/
static void DB_DrawCircle(int x,int y,int r,int key);
/**画当前节点与其孩子节点的连线*/
static void DB_DrawStick(int i,int j,int h,int r,int w,int mode,int shifty);
/**调用便是此函数，即绘制二叉树**/
void DB_DrawNode(void *t,DB_GetChild fgetChild,DB_GetKey fgetKey,int i,int j,int r,int h,int w,int shifty);
/**具体实现，时间关系，暂时不过多注释,这些代码其实就是实现第一部分中的算法分析**/
static void DB_DrawStick(int i,int j,int h,int r,int w,int mode,int shifty)
{
int x1,x2,y1,y2;
double cosa,sina,tana;
tana=1/pow(2,h-i-1);
sina=sqrt(tana*tana/(1+tana*tana));
cosa=sqrt(1/(1+tana*tana));
if(mode==DB_LEFTCHILD)
{
x1=pow(2,h-i)*(2*j-1)*w+cosa*r-pow(2,h-i-1)*w;
y1=(i+1)*w-sina*r;
x2=pow(2,h-i)*(2*j-1)*w-cosa*r;
y2=i*w+sina*r+shifty;
}else
{
x1=pow(2,h-i)*(2*j-1)*w-cosa*r+pow(2,h-i-1)*w;
y1=(i+1)*w-sina*r;
x2=pow(2,h-i)*(2*j-1)*w+cosa*r+1;
y2=i*w+sina*r+shifty+1;
}
vga_drawline(x1,y1,x2,y2);
}
/*static void DB_DrawCircle(int x,int y,int r,int key)
{
int i;
int x1,y1,x2,y2;
x1=x-r;
y1=y-sqrt(r*r-(x-x1)*(x-x1));
for(i=x-r+1;i<=x+r+1;i++)
{
x2=i;
y2=y-sqrt(r*r-(x-x1)*(x-x1));
vga_drawline(x1,y1,x2,y2);
vga_drawline(x1,y1+2*(y-y1),x2,y2+2*(y-y2));
x1=x2;y1=y2;
}
}*/
static void DB_DrawCircle(int x,int y,int r,int key)
{
int i;
int x1,y1,x2,y2;
x1=x-r;
y1=y-sqrt(r*r-(x-x1)*(x-x1));
for(i=x-r+1;i<=x+r+1;i++)
{
x2=i;
y2=y-sqrt(r*r-(x-x1)*(x-x1));
vga_drawline(x1,y1,x2,y2);
vga_drawline(x1,y1+2*(y-y1),x2,y2+2*(y-y2));
x1=x2;y1=y2;
}
}
void DB_DrawNode(void *t,DB_GetChild fgetChild,DB_GetKey fgetKey,int i,int j,int r,int h,int w,int shifty)
{
void * pc;
if (t==NULL)return;
/*画点*/
DB_DrawCircle(pow(2,h-i)*(2*j-1)*w,(i)*w,r,fgetKey(t));
/*打印节点名字*/
gl_printf(pow(2,h-i)*(2*j-1)*w-2.0/3*r,i*w,"%d",fgetKey(t));
if((pc=fgetChild(t,DB_LEFTCHILD)))
{/*递归画左孩子及其连线*/
DB_DrawStick(i,j,h,r,w,DB_LEFTCHILD,shifty);
DB_DrawNode(pc,fgetChild,fgetKey,i+1,2*j-1,r,h,w,shifty);
}
if((pc=fgetChild(t,DB_RIGHTCHILD)))
{/*递归画右孩子及其连线*/
DB_DrawStick(i,j,h,r,w,DB_RIGHTCHILD,shifty);
DB_DrawNode(pc,fgetChild,fgetKey,i+1,2*j,r,h,w,shifty);
}
}
static int DB_GetTreeHeight(void * t,DB_GetChild fgetChild)
{
int lh,rh;
if(t==NULL)return -1;
lh=DB_GetTreeHeight(fgetChild(t,DB_LEFTCHILD),fgetChild);
rh=DB_GetTreeHeight(fgetChild(t,DB_RIGHTCHILD),fgetChild);
return lh>rh?lh+1:rh+1;
}
/****************绘制二叉树的调用接口*************/
*t,二叉树
*fgetchild,传入的函数指针，此函数接受一个节点返回孩子节点，函数由调用的客户自己编写
*fgetKey，传入的函数指针，此函数接受一个节点并返回其键值（整数），由调用的客户自己实*现
/
void DB_DrawBitTree(void * t, DB_GetChild fgetChild, DB_GetKey fgetKey)
{
int h,w,vgamode;
h=DB_GetTreeHeight(t,fgetChild);
w=DB_GetWidth()/pow(2,h);
if(w<MIN_NODE)
{
printf("tree's height is too large now,program exit");
return 0;
}
w=w>50?50:w;
vga_init();
vgamode=G800x600x256;
vga_setmode(vgamode);
vga_setcolor(5);
gl_setcontextvga(vgamode);
gl_enableclipping();
gl_setfont(8,8,gl_font8x8);
gl_setwritemode(FONT_COMPRESSED+WRITEMODE_OVERWRITE);
gl_setfontcolors(0,222);
/*画二叉树*/
DB_DrawNode(t,fgetChild,fgetKey,1,1,w/3,h,w,0);
vga_getch();
vga_setmode(TEXT);
}
/***测试文件****此程序修改前面提到的对ST_Tree的测试文件***/
/*///
*author:Felix
*create date:Fri Jan 11 03:45:18 EST 2008
*last update:Fri Jan 11 03:45:18 EST 2008
*description:
*
*
*//
#include "menu_c.h"
#include<stdio.h>
#include<stdlib.h>
#include"ST_tree.h"
#include"drawBitTree.h"
struct ST_TreeNode
{
ST_Element e;
ST_Tree left;
ST_Tree right;
};
/******define some function to show the tree*******/
int getkey(void * t)
{
return ((ST_Tree)t)->e;
}
void * getchild(void * t,int mode)
{
if(mode==DB_LEFTCHILD)return ((ST_Tree)t)->left;
else return ((ST_Tree)t)->right;
}
/*****************/
int main()
{
int n;
ST_Tree t;
ST_Position p;
t=ST_MakeEmpty(NULL);
while(SELECT())
{
switch (SELECTION)
{
case '1':
printf("integer:>");
scanf("%d",&n);
t=ST_Insert(n,t);
break;
case '2':
printf("integer to delete:>");
scanf("%d",&n);
if(!ST_Find(n,t))printf("sorry,no integer match");
else {
t=ST_Delete(n,t);
printf("deletion done");
}
break;
case '3':
while(p=ST_FindMin(t))
{
printf("%d " ,ST_Retrieve(p),t);
t= ST_Delete(ST_Retrieve(p),t);
}
break;
case '4':
while(p=ST_FindMax(t))
{
printf("%d " ,ST_Retrieve(p));
t=ST_Delete(ST_Retrieve(p),t);
}
break;
case '5':
if(!(p=ST_FindMax(t)))printf("sorry,the tree is NULL");
else
printf("%d",ST_Retrieve(p));
break;
case '6':
if(!(p=ST_FindMin(t)))printf("sorry ,the tree is NULL");
else
printf("%d",ST_Retrieve(p));
break;
case '7':
DB_DrawBitTree(t,getchild,getkey);
break;
case '9':
system("less ../ST_tree.h");
break;
default:break;
}
}
return 0;
}
/***menu_c.h**/
/*///
*author:Felix
*create date:Fri Jan 11 03:45:18 EST 2008
*last update:Fri Jan 11 03:45:18 EST 2008
*description:
*
*
*/
#include <stdio.h>
#ifndef __MENU____
#define __MENU____
#define SELECT() ((___sel=___select())!='0')
#define SELECTION ___sel
char ___sel;
char ___select();
/*
define the menu:
*/
#endif
/***menu_c.c**/
/*///
*author:Felix
*create date:Fri Jan 11 03:45:18 EST 2008
*last update:Fri Jan 11 03:45:18 EST 2008
*description:
*
*
*/
#include "menu_c.h"
char *___menu[]={
"1.Insert a integer.",
"2.Delete an integer from the tree.",
"3.Sort and show from small to big(will delete the tree)",
"4.Sort and show from big to small(will delete the tree)",
"5.show the max",
"6.show the min", "9.Print the file ST_tree.h",
"7.show the tree",
"0.EXIT",
NULL
};
void ___showMenu()
{
printf("please select:/n");
char **p=___menu;
while(*p)printf("%s/n",*p++);
printf(":>");
}
char ___select()
{
char c;
___showMenu();
while((c=getchar())=='/n');
return c;
}
/**Makefile*假设你已经看过我前面的文章，如果没有的话，你需要找到我前面的ST_Tree的源代码，注意加上 编译选项加上-lvga -lvgagl*/
include ~/.FelixInit
objects=menu_c.o testST_tree.o
testST_tree:$(objects)
$(cc) $^ $(CFLAGS) -lvga -lvgagl -o $@
clean:
-rm *.o
-rm testST_tree
1。给出任意一个二叉树t和一些函数指针，调用此函数即可在控制台下以图形打印此二叉树。
2。调用基本参数，二叉树 t，获取孩子节点的函数指针fgetChild,获取节点键值的函数指针fgetKey.
提示，关于svga一些入门的话，可以直接查看vga.h头文件，并且编译源代码的时候可以编译出许多很用的例子，在编译目录 下 demos文件夹下可以找到这些简单而有趣的例子，当然你也可以查相关的在线手册，我曾经看到一个英文的在线tutorials，但忘了地址了，可以google一下(估计百度不出来^_^)
一。算法分析：
先想像一下，我们把整个屏幕分成网格的逻辑，我们将在网格中一个个的放入二叉树的节点，绘制一个节点时，如果它有子节点，则再绘制相应的线段。
画图算法描述：
设要画的树高度为h（此时树有h+1层），画树要考虑到画布必须至少要有容纳得下满树的空间，则考虑满树时，
叶子节点个数为:2^h,则可以把每个层的横向空间分为2^h个基本单位(想像分割成正方形空间)，设此单位值为w,w=TreeWidth/2^h,节点可以画在线上或正方形垂直边上，
第i层(1<=i<=h+1)的节点数为,2^(i-1),因此，第i层可以被平均的分为2^(i-1)空间，每个空间取中点就是节点的位置。
对于第i层的每个节点的位置，他们的位置是：((2^h/2^(i-1))*j+(2^h/2^(i-1))*(j-1))/2=(2^h/2^(i-1))(2*j-1)/2=2^(h-i)*(2*j-1),j=1,2,..,2^(i-1),
如果节点画成圆，且对应上像素点，则得到最后每个节点的位置公式为：
(2^(h-i)*(2*j-1)*w,(i)*w),
(i=1,2,..,h+1 ;j=1,2,...,2^(i-1);w=TreeWidth/(2^h)),圆半径r=w/2
可以加个纵向上偏移，调整树的高度如：
(2^(h-i)*(2*j-1)*w,(i)*w+py)
(i=1,2,..,h+1 ;j=1,2,...,2^(i-1);w=TreeWidth/(2^h)),圆半径r=w/2
任意节点P（2^(h-i)*(2*j-1)*w，(i)*w）的左右孩子中心坐标分别为：
左孩子：L(2^(h-i)*(2*j-1)*w-(2^h/2^(i+1))*w,(i+1)*w)
右孩子：R(2^(h-i)*(2*j-1)*w+(2^h/2^(i+1))*w,(i+1)*w)
设线段PL与水平线夹角为a,则
tan(a)=1/(2^h/(2^(i+1))=1/(2^(h-i-1))
并且易得，PR与水平线的夹角等于a.
设PL与左孩子节点圆的交点为A，与节点圆P的交点为B,已经LA＝w／2,根据平面几何易得A的坐标为
(2^(h-i)*(2*j-1)*w+cos(a)*r-(2^(h-i-1))*w,(i+1)*w-sin(a)*r)
B坐标为：
(2^(h-i)*(2*j-1)*w-cos(a)*r,(i)*w+sin(a)*r)
而sin(a)=sqrt(tan(a)*tan(a)/(1+tan(a)*tan(a)))
cos(a)=sqrt(1/(1+tan(a)*tan(a)))
同时，设PR与P节点圆和R孩子的交点分别为C ,D；则C ，D坐标分别为
(2^(h-i)*(2*j-1)*w-cos(a)*r+(2^h/2^(i+1))*w,(i+1)*w-sin(a)*r)
(2^(h-i)*(2*j-1)*w+cos(a)*r,(i)*w+sin(a)*r)
要特别说明的是，1～h层的节点都处于正方形的垂直边上，而第h＋1层节点（叶子节点)正好处于正方形内，且正好用完第h＋1层的正方形。
还有一个关系需要理清楚，设当前节点处在树的每i层（从根算起)的第j个节点,则把树从根向叶子和从左向右排序号，当前节点的序号是
2^(i-1)+j,设它的左右孩子的层数和层数内的节点编号分别为 li,lj,ri,rj则有
li=ri=i+1;
lj=2*j-1
rj=2*j
二。代码。
下面代码经过测试，成功，只是svgalib库可能不太稳定。
我乐意帮助大家，q上我349871604我直接传代码。^_^
今天到此是为了早上买火车票，真是倒霉啊！
/*头文件drawBitTree.h*/
/********************************** *
*author:Felix
*last update:Mon Jan 14 11:51:31 EST 2008
*Address me and exchange our idea ^_^,QQ:349871604,e-mail:lzqziliao2004@163.com
*description:
*
*
*
*/
#ifndef ___DRAWBITTREE___
#define ___DRAWBITTREE___
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<vga.h>
#include<vgagl.h>
#define DB_GetWidth() 800
#define DB_GetHeight() 600
#define DB_LEFTCHILD 1
#define DB_RIGHTCHILD 2
/*a node's maximum area of retangle:**/
#define MAX_NODE 50
#define MIN_NODE 5
typedef void * DB_GetChild(void * p,int mode);
typedef int DB_GetKey(void * p);
/*
*t:the tree to be draw
*fgetKey:pointer to a funtion that return a key of a node
*fgetChild:pointer to a function that return a pointer to a left child of a node
*/
void DB_DrawBitTree(void * t, DB_GetChild fgetChild, DB_GetKey fgetKey);
#endif
/*实现文件*/
/*last update:Mon Jan 14 11:51:31 EST 2008
*Address me and exchange our idea ^_^,QQ:349871604,e-mail:lzqziliao2004@163.com
*description:
*
*
*
*/
#include "drawBitTree.h"
/**获取树的高度,fgetChild是一个函数指针，t是一个二叉树*/
static int DB_GetTreeHeight(void * t,DB_GetChild fgetChild);
/**在屏幕中画圆*/
static void DB_DrawCircle(int x,int y,int r,int key);
/**画当前节点与其孩子节点的连线*/
static void DB_DrawStick(int i,int j,int h,int r,int w,int mode,int shifty);
/**调用便是此函数，即绘制二叉树**/
void DB_DrawNode(void *t,DB_GetChild fgetChild,DB_GetKey fgetKey,int i,int j,int r,int h,int w,int shifty);
/**具体实现，时间关系，暂时不过多注释,这些代码其实就是实现第一部分中的算法分析**/
static void DB_DrawStick(int i,int j,int h,int r,int w,int mode,int shifty)
{
int x1,x2,y1,y2;
double cosa,sina,tana;
tana=1/pow(2,h-i-1);
sina=sqrt(tana*tana/(1+tana*tana));
cosa=sqrt(1/(1+tana*tana));
if(mode==DB_LEFTCHILD)
{
x1=pow(2,h-i)*(2*j-1)*w+cosa*r-pow(2,h-i-1)*w;
y1=(i+1)*w-sina*r;
x2=pow(2,h-i)*(2*j-1)*w-cosa*r;
y2=i*w+sina*r+shifty;
}else
{
x1=pow(2,h-i)*(2*j-1)*w-cosa*r+pow(2,h-i-1)*w;
y1=(i+1)*w-sina*r;
x2=pow(2,h-i)*(2*j-1)*w+cosa*r+1;
y2=i*w+sina*r+shifty+1;
}
vga_drawline(x1,y1,x2,y2);
}
/*static void DB_DrawCircle(int x,int y,int r,int key)
{
int i;
int x1,y1,x2,y2;
x1=x-r;
y1=y-sqrt(r*r-(x-x1)*(x-x1));
for(i=x-r+1;i<=x+r+1;i++)
{
x2=i;
y2=y-sqrt(r*r-(x-x1)*(x-x1));
vga_drawline(x1,y1,x2,y2);
vga_drawline(x1,y1+2*(y-y1),x2,y2+2*(y-y2));
x1=x2;y1=y2;
}
}*/
static void DB_DrawCircle(int x,int y,int r,int key)
{
int i;
int x1,y1,x2,y2;
x1=x-r;
y1=y-sqrt(r*r-(x-x1)*(x-x1));
for(i=x-r+1;i<=x+r+1;i++)
{
x2=i;
y2=y-sqrt(r*r-(x-x1)*(x-x1));
vga_drawline(x1,y1,x2,y2);
vga_drawline(x1,y1+2*(y-y1),x2,y2+2*(y-y2));
x1=x2;y1=y2;
}
}
void DB_DrawNode(void *t,DB_GetChild fgetChild,DB_GetKey fgetKey,int i,int j,int r,int h,int w,int shifty)
{
void * pc;
if (t==NULL)return;
/*画点*/
DB_DrawCircle(pow(2,h-i)*(2*j-1)*w,(i)*w,r,fgetKey(t));
/*打印节点名字*/
gl_printf(pow(2,h-i)*(2*j-1)*w-2.0/3*r,i*w,"%d",fgetKey(t));
if((pc=fgetChild(t,DB_LEFTCHILD)))
{/*递归画左孩子及其连线*/
DB_DrawStick(i,j,h,r,w,DB_LEFTCHILD,shifty);
DB_DrawNode(pc,fgetChild,fgetKey,i+1,2*j-1,r,h,w,shifty);
}
if((pc=fgetChild(t,DB_RIGHTCHILD)))
{/*递归画右孩子及其连线*/
DB_DrawStick(i,j,h,r,w,DB_RIGHTCHILD,shifty);
DB_DrawNode(pc,fgetChild,fgetKey,i+1,2*j,r,h,w,shifty);
}
}
static int DB_GetTreeHeight(void * t,DB_GetChild fgetChild)
{
int lh,rh;
if(t==NULL)return -1;
lh=DB_GetTreeHeight(fgetChild(t,DB_LEFTCHILD),fgetChild);
rh=DB_GetTreeHeight(fgetChild(t,DB_RIGHTCHILD),fgetChild);
return lh>rh?lh+1:rh+1;
}
/****************绘制二叉树的调用接口*************/
*t,二叉树
*fgetchild,传入的函数指针，此函数接受一个节点返回孩子节点，函数由调用的客户自己编写
*fgetKey，传入的函数指针，此函数接受一个节点并返回其键值（整数），由调用的客户自己实*现
/
void DB_DrawBitTree(void * t, DB_GetChild fgetChild, DB_GetKey fgetKey)
{
int h,w,vgamode;
h=DB_GetTreeHeight(t,fgetChild);
w=DB_GetWidth()/pow(2,h);
if(w<MIN_NODE)
{
printf("tree's height is too large now,program exit");
return 0;
}
w=w>50?50:w;
vga_init();
vgamode=G800x600x256;
vga_setmode(vgamode);
vga_setcolor(5);
gl_setcontextvga(vgamode);
gl_enableclipping();
gl_setfont(8,8,gl_font8x8);
gl_setwritemode(FONT_COMPRESSED+WRITEMODE_OVERWRITE);
gl_setfontcolors(0,222);
/*画二叉树*/
DB_DrawNode(t,fgetChild,fgetKey,1,1,w/3,h,w,0);
vga_getch();
vga_setmode(TEXT);
}
/***测试文件****此程序修改前面提到的对ST_Tree的测试文件***/
/*///
*author:Felix
*create date:Fri Jan 11 03:45:18 EST 2008
*last update:Fri Jan 11 03:45:18 EST 2008
*description:
*
*
*//
#include "menu_c.h"
#include<stdio.h>
#include<stdlib.h>
#include"ST_tree.h"
#include"drawBitTree.h"
struct ST_TreeNode
{
ST_Element e;
ST_Tree left;
ST_Tree right;
};
/******define some function to show the tree*******/
int getkey(void * t)
{
return ((ST_Tree)t)->e;
}
void * getchild(void * t,int mode)
{
if(mode==DB_LEFTCHILD)return ((ST_Tree)t)->left;
else return ((ST_Tree)t)->right;
}
/*****************/
int main()
{
int n;
ST_Tree t;
ST_Position p;
t=ST_MakeEmpty(NULL);
while(SELECT())
{
switch (SELECTION)
{
case '1':
printf("integer:>");
scanf("%d",&n);
t=ST_Insert(n,t);
break;
case '2':
printf("integer to delete:>");
scanf("%d",&n);
if(!ST_Find(n,t))printf("sorry,no integer match");
else {
t=ST_Delete(n,t);
printf("deletion done");
}
break;
case '3':
while(p=ST_FindMin(t))
{
printf("%d " ,ST_Retrieve(p),t);
t= ST_Delete(ST_Retrieve(p),t);
}
break;
case '4':
while(p=ST_FindMax(t))
{
printf("%d " ,ST_Retrieve(p));
t=ST_Delete(ST_Retrieve(p),t);
}
break;
case '5':
if(!(p=ST_FindMax(t)))printf("sorry,the tree is NULL");
else
printf("%d",ST_Retrieve(p));
break;
case '6':
if(!(p=ST_FindMin(t)))printf("sorry ,the tree is NULL");
else
printf("%d",ST_Retrieve(p));
break;
case '7':
DB_DrawBitTree(t,getchild,getkey);
break;
case '9':
system("less ../ST_tree.h");
break;
default:break;
}
}
return 0;
}
/***menu_c.h**/
/*///
*author:Felix
*create date:Fri Jan 11 03:45:18 EST 2008
*last update:Fri Jan 11 03:45:18 EST 2008
*description:
*
*
*/
#include <stdio.h>
#ifndef __MENU____
#define __MENU____
#define SELECT() ((___sel=___select())!='0')
#define SELECTION ___sel
char ___sel;
char ___select();
/*
define the menu:
*/
#endif
/***menu_c.c**/
/*///
*author:Felix
*create date:Fri Jan 11 03:45:18 EST 2008
*last update:Fri Jan 11 03:45:18 EST 2008
*description:
*
*
*/
#include "menu_c.h"
char *___menu[]={
"1.Insert a integer.",
"2.Delete an integer from the tree.",
"3.Sort and show from small to big(will delete the tree)",
"4.Sort and show from big to small(will delete the tree)",
"5.show the max",
"6.show the min", "9.Print the file ST_tree.h",
"7.show the tree",
"0.EXIT",
NULL
};
void ___showMenu()
{
printf("please select:/n");
char **p=___menu;
while(*p)printf("%s/n",*p++);
printf(":>");
}
char ___select()
{
char c;
___showMenu();
while((c=getchar())=='/n');
return c;
}
/**Makefile*假设你已经看过我前面的文章，如果没有的话，你需要找到我前面的ST_Tree的源代码，注意加上 编译选项加上-lvga -lvgagl*/
include ~/.FelixInit
objects=menu_c.o testST_tree.o
testST_tree:$(objects)
$(cc) $^ $(CFLAGS) -lvga -lvgagl -o $@
clean:
-rm *.o
-rm testST_tree
类似资料：