完全三叉树解决长方形容器中光源反射点遍历的问题

[问题描述]：
在一个正方形的屋子里面（只考虑平面结构），有一个光源和一个目的点，从光源开始经过多次反射到达目的点，其间相对4个镜面有N个反射点，求经过m次反射的所有反射点，以及这些反射点到目的点的距离和反射角，

[程序设计]
1.在第一次反射之后，以4个第一次反射点为根节点，构造4个完全三叉树，
2.每个节点的构造为，编号，x,y坐标，到达目的点的距离，父节点指针，反射角指针，下一个节点指针

[程序说明]
本程序使用C语言编写，是用通用的C语言函数库（我用的是MinGW:windows下开发Linux程序的编译库），在windows下编写，在Linux下运行通过(可能定义稍事修改)

#include
#include
#include

static float box_width = 20.0;
static float box_lenght = 30.0;
static int node_total = 0;

typedef struct NODE{
int num ;
char mirror;
float x ;
float y ;
float distance ;
float incidence;
struct NODE *parent;
struct NODE *next;
}NODE;

int levelNums(int level){
if (level == 1){
return 1;
}else{
return levelNums(--level)*3;
}
}
/*
* to use recursion to count up the tree nodes' numbers ;
*
*/
int treeNums_recur(int level){
int sum;
sum = 0;
for(int i=1 ; i<=level ; i++){ sum = sum + levelNums(i); } return sum; } float rtnDistand(float rx0,float ry0,float node_x , float node_y){ return sqrt((node_x-rx0)*(node_x-rx0)+(node_y-ry0)*(node_y-ry0)); } /* * to use mathematics formula to count up the tree nodes' numbers ; * A1 = 1 ; A2 = 3 ; A3 = 9 ; ...... An = 3*(n-1); * S1 = 1 : S2 = 4 ; S3 = 13; ...... Sn = (3^n -1 )/2; * @param int level : this node in which level * @param return : the number from root to this level */ int treeNums_maths(int level){ int sum; int accumulate ; accumulate = 3; for (int n =1 ; n ＜level ; n ++){ accumulate = accumulate*3; } sum = (accumulate-1)/2; return sum; }

int levelInTree(int num){
int level;
level = 0;
while(num > 0){
level++ ;
num = num - levelNums(level);
}
return level;
}

/*
* @param int num : child node's number
* @param return : parent node's number
*/
int parentNum(int num){
int level,parentTreeNum,parent;
level = 0;
parentTreeNum = 0;
parent = 0;
level = levelInTree(num);

if (level == 1){
parent = 1;
}else if(level == 2){
parent = 1;
}else {
parentTreeNum = treeNums_maths(level-1);
if ((num-parentTreeNum)%3 == 0){
parent = treeNums_maths(level-2)+(num-parentTreeNum)/3;
}else{
parent = treeNums_maths(level-2)+(num-parentTreeNum)/3 + 1;
}
}
return parent;
}

struct NODE *parentOfNode(NODE *root,NODE *childNode ){
struct NODE *parent;
int pNum;
parent = root;
pNum = parentNum(childNode->num);
for (int i = 1; i<= pNum ; i++){ if(i == pNum){ break; }else{ parent = parent->next;
}
}
return parent;
}

float arctan(float width,float height,float t_x0,float t_y0,NODE *pNode){
float xSide,ySide,temp_x,temp_y,alpha;
xSide = pNode->x - t_x0;
ySide = pNode->y - t_y0;
xSide = xSide >= 0.0 ? xSide : -xSide;
ySide = ySide >= 0.0 ? ySide : -ySide;
if (pNode->mirror == 'A' || pNode->mirror == 'C'){
alpha = 180*atan2f(xSide,ySide)/M_PI;
}
if (pNode->mirror == 'B' || pNode->mirror == 'D'){
alpha = 180*atan2f(ySide,xSide)/M_PI;
}
return alpha;
}

/*
* @param float width: the width of box
* @param float height: the height of box
* @param float t_x0: x0 of the aim;
* @param float t_y0: y0 of the aim;
* @param int num : the number of treee;
* @param NODE *pNode : to input the node point of root;
* @return struct NODE *int : to output the node point of root;
*
*/
struct NODE *init(
float width,
float height,
float t_x0,
float t_y0,
int num ,
NODE *pNode
){
struct NODE *temp,*root,*parent,*curNode;
char ch ;
ch = pNode->mirror;
temp = pNode;

//init the all nodes of the tree,except parameter -- parent
for(int i = num ; i >= 1 ; i--){
struct NODE *nodes=(struct NODE *)malloc(sizeof(struct NODE));
nodes->num = i;
nodes->mirror = ch;
if (i ==1){
nodes->x = pNode->x;
nodes->y = pNode->y;
}
nodes->next = temp;
temp = nodes;
}
root = temp;

//init all nodes' parameter parent of the tree
for(int i = 1 ; i<=num ; i++){ temp->parent = parentOfNode(root,temp);
temp = temp->next;
}

temp = root;
parent = root;
curNode = root;

root->incidence = arctan(width, height, t_x0, t_y0,curNode);
root->distance = rtnDistand(t_x0,t_y0,curNode->x,curNode->y);

for(int i = 1 ; inext;
if(curNode->parent == temp->parent){
curNode->mirror = temp->mirror + 1;
}else{
curNode->mirror = curNode->parent->mirror + 1;
}
if (curNode->mirror == 'E'){
curNode->mirror = 'A';
}
switch(curNode->mirror){
case 'A':
curNode->x = curNode->parent->x;
curNode->y = curNode->parent->y*(-1);
break;
case 'B':
curNode->x = curNode->parent->x*(-1) + 2*width;
curNode->y = curNode->parent->y;
break;
case 'C':
curNode->x = curNode->parent->x;
curNode->y = curNode->parent->y*(-1) + 2*height;
break;
case 'D':
curNode->x = curNode->parent->x*(-1);
curNode->y = curNode->parent->y;
break;
}
curNode->incidence = arctan(width, height, t_x0, t_y0,curNode);
curNode->distance = rtnDistand(t_x0,t_y0,curNode->x,curNode->y);
}

return root;
}

struct NODE *pntNode(int num, NODE *root){
struct NODE *pNode;
pNode = root;

printf("\n\n●●●●●●●●●●●●●●●●●●●");
printf("\n print all nodes' information");
printf("\nNUM\tMIRROR\tDISTANCE\tINCIDENCE\tX\t\tY\t\tPARENT\n");
for(int i=1 ; i <= num ; i++){ printf("%d",pNode->num);
printf("\t%c",pNode->mirror);
printf("\t%f",pNode->distance);
printf("\t%f",pNode->incidence);
printf("\t%f",pNode->x);
printf("\t%f",pNode->y);
printf("\t%d",pNode->parent->num);
printf("\n");
pNode = pNode->next;
}
return root;
}
/*int main(){
float rx0,ry0,node_x,node_y;
rx0 = 1;
ry0 = 3;
node_x = -6;
node_y = -1;
printf("\n%f_%f_%f",node_x,rx0,node_x-rx0);
printf("\n%f_%f_%f",node_y,ry0,node_y-ry0);
printf("\n%f",sqrt((node_x-rx0)*(node_x-rx0)+(node_y-ry0)*(node_y-ry0)));

return 0;
}*/

int main() {

int level,count;
float width,height,t_x0,t_y0;
struct NODE *rNode,*sRoot[4];
char chTemp = 'R';

rNode = (struct NODE *)malloc(sizeof(struct NODE));
rNode->num = 1;
rNode->x = 0.0;
rNode->y = 0.0;
rNode->mirror = chTemp;
rNode->parent = rNode;
rNode->next = rNode;
rNode->distance = 0.0;

// to input the box information
printf("\n●●●●●●●●●●●●●●●●●●●");
printf("\nplease input the box information");
printf("\n width of the box:");
scanf("%f",&width);
printf(" height of the box:");
scanf("%f",&height);
while((width <= 0.0 || width > 100.0)||(height <= 0.0 || height > 100.0)){
printf("\nsorry the range of the box width and height is between 0.0 and 100.0");
printf("\n width of the box:");
scanf("%f",&width);
printf(" height of the box:");
scanf("%f",&height);
}

// to input the light source information
printf("\n●●●●●●●●●●●●●●●●●●●");
printf("\nplease input the x,y of light source");
printf("\n x of light source:");
scanf("%f",&rNode->x);
printf(" y of light source:");
scanf("%f",&rNode->y);
while((rNode->x <=0.0 || rNode->x >=width ) || (rNode->y <=0.0 || rNode->y >=height)){
printf("\nsorry the range of light source is between 0.0 and box's width(%f) or height(%f)",width,height);
printf("\n x of light source:");
scanf("%f",&rNode->x);
printf(" y of light source:");
scanf("%f",&rNode->y);
}

// to input the x,y of aim
printf("\n●●●●●●●●●●●●●●●●●●●");
printf("\nplease input the x,y of aim");
printf("\n x of aim:");
scanf("%f",&t_x0);
printf(" y of aim:");
scanf("%f",&t_y0);
while((t_x0 <=0.0 || t_x0 >=width )|| (t_y0 <=0.0 || t_y0 >=height)){
printf("\nsorry the range of aim is between 0.0 and box's width(%f) or height(%f)",width,height);
printf("\n x of aim:");
scanf("%f",&t_x0);
printf(" y of aim:");
scanf("%f",&t_y0);
}


// to input the number of reflected times
printf("\n●●●●●●●●●●●●●●●●●●●");
printf("\nplease input the number of reflected times:");
scanf("%d",&level);
while (level <=0 || level >=10){
printf("\nsorry, the reflected range is between 1 and 10 :");
scanf("%d",&level);
}

count = 0;
count = treeNums_maths(level);

chTemp = 'A';
for (int i = 0 ; i <>mirror == 'E'){
(*(sRoot+i))->mirror = 'A';
}else{
(*(sRoot+i))->mirror = chTemp;
}

(*(sRoot+i))->num = 1;

switch((*(sRoot+i))->mirror){
case 'A':
(*(sRoot+i))->x = rNode->x;
(*(sRoot+i))->y = rNode->y*(-1);
break;
case 'B':
(*(sRoot+i))->x = rNode->x*(-1) + 2*width;
(*(sRoot+i))->y = rNode->y;
break;
case 'C':
(*(sRoot+i))->x = rNode->x;
(*(sRoot+i))->y = rNode->y*(-1) + 2*height;
break;
case 'D':
(*(sRoot+i))->x = rNode->x*(-1);
(*(sRoot+i))->y = rNode->y;
break;
}

*(sRoot+i)= init(width,height,t_x0,t_y0,count,(*(sRoot+i)));
}

for (int i = 0 ; i <>

return 0;
}