如何使用C或C++结构建立八叉树的模型
作者&投稿：秋炭 （若有异议请与网页底部的电邮联系）
(1). 设定最大递归深度(2). 找出场景的最大尺寸，并以此尺寸建立第一个立方体(3). 依序将单位元元素丢入能被包含且没有子节点的立方体(4). 若没有达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八个子立方体(5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目还是一样，会造成无穷切割的情形。(6). 重复3，直到达到最大递归深度。
树结构的构造在 数据结构相关书里面都有介绍， 楼主的难点在图形界面实现上吧？
简单界面：方块用按钮实现，箭头直接画线就行
要好看点的话就自定义控件吧。
如果要用C语言编写，则
（1）使用C结构建立八叉树的模型
1.typedef struct OctreeNode 2.{ 3. int value; 4. struct OctreeNode *Up; 5. struct OctreeNode *Down; 6. struct OctreeNode *Left; 7. struct OctreeNode *Right; 8. struct OctreeNode *Front; 9. struct OctreeNode *Back; 10.}OctreeNode;
（2）递归添加上下左右前后邻居，我这里只给一面
1.void AddUp(OctreeNode *Me, int v) 2.{ 3. Me->Up = (OctreeNode *)malloc(sizeof (OctreeNode)); 4. Me->Up->vvalue = v; 5. Me->Up->Up = NULL; 6. Me->Up->Down = Me; 7. Me->Up->Front = NULL; 8. OctreeMe->Up->Back = NULL; 9. Me->Up->Right = NULL; 10. Me->Up->Left = NULL; 11.}
实现Octree的原理
(1). 设定最大递归深度
(2). 找出场景的最大尺寸，并以此尺寸建立第一个立方体
(3). 依序将单位元元素丢入能被包含且没有子节点的立方体
(4). 若没有达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八
个子立方体
(5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止
细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目
还是一样，会造成无穷切割的情形。
(6). 重复3，直到达到最大递归深度。
#include <iostream.h>
using namespace std;//定义八叉树节点类
template<class T>
struct OctreeNode
{
T data; //节点数据
T xmin,xmax; //节点坐标，即六面体个顶点的坐标
T ymin,ymax;
T zmin,zmax;
OctreeNode <T> *top_left_front,*top_left_back; //该节点的个子结点
OctreeNode <T> *top_right_front,*top_right_back;
OctreeNode <T> *bottom_left_front,*bottom_left_back;
OctreeNode <T> *bottom_right_front,*bottom_right_back;
OctreeNode //节点类
(T nodeValue = T(),
T xminValue = T(),T xmaxValue = T(),
T yminValue = T(),T ymaxValue = T(),
T zminValue = T(),T zmaxValue = T(),
OctreeNode<T>* top_left_front_Node = NULL,
OctreeNode<T>* top_left_back_Node = NULL,
OctreeNode<T>* top_right_front_Node = NULL,
OctreeNode<T>* top_right_back_Node = NULL,
OctreeNode<T>* bottom_left_front_Node = NULL,
OctreeNode<T>* bottom_left_back_Node = NULL,
OctreeNode<T>* bottom_right_front_Node = NULL,
OctreeNode<T>* bottom_right_back_Node = NULL )
:data(nodeValue),
xmin(xminValue),xmax(xmaxValue),
ymin(yminValue),ymax(ymaxValue),
zmin(zminValue),zmax(zmaxValue),
top_left_front(top_left_front_Node),
top_left_back(top_left_back_Node),
top_right_front(top_right_front_Node),
top_right_back(top_right_back_Node),
bottom_left_front(bottom_left_front_Node),
bottom_left_back(bottom_left_back_Node),
bottom_right_front(bottom_right_front_Node),
bottom_right_back(bottom_right_back_Node){}
};
//创建八叉树
template <class T>
void createOctree(OctreeNode<T> * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)
{
cout<<"处理中，请稍候……"<<endl;
maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1
if(maxdepth>=0)
{
root=new OctreeNode<T>();
root->data = 9; //为节点赋值，可以存储节点信息，如物体可见性。由于是简单实现八叉树功能，简单赋值为。
root->xmin=xmin; //为节点坐标赋值
root->xmax=xmax;
root->ymin=ymin;
root->ymax=ymax;
root->zmin=zmin;
root->zmax=zmax;
double xm=(xmax-xmin)/2;//计算节点个维度上的半边长
double ym=(ymax-ymin)/2;
double zm=(ymax-ymin)/2;
//递归创建子树，根据每一个节点所处（是几号节点）的位置决定其子结点的坐标。
createOctree(root->top_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmax-zm,zmax);
createOctree(root->top_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmax-zm,zmax);
createOctree(root->top_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmax-zm,zmax);
createOctree(root->top_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmax-zm,zmax);
createOctree(root->bottom_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmin,zmax-zm);
createOctree(root->bottom_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmin,zmax-zm);
createOctree(root->bottom_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmin,zmax-zm);
createOctree(root->bottom_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmin,zmax-zm);
}
}
int i=1;
//先序遍历八叉树
template <class T>
void preOrder( OctreeNode<T> * & p)
{
if(p)
{
cout<<i<<".当前节点的值为："<<p->data<<"\n坐标为：";
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
i+=1;
cout<<endl;
preOrder(p->top_left_front);
preOrder(p->top_left_back);
preOrder(p->top_right_front);
preOrder(p->top_right_back);
preOrder(p->bottom_left_front);
preOrder(p->bottom_left_back);
preOrder(p->bottom_right_front);
preOrder(p->bottom_right_back);
cout<<endl;
}
}
//求八叉树的深度
template<class T>
int depth(OctreeNode<T> *& p)
{
if(p == NULL)
return -1;
int h = depth(p->top_left_front);
return h+1;
}
//计算单位长度，为查找点做准备
int cal(int num)
{
int result=1;
if(1==num)
result=1;
else
{
for(int i=1;i<num;i++)
result=2*result;
}
return result;
}
//查找点
int maxdepth=0;
int times=0;
static double xmin=0,xmax=0,ymin=0,ymax=0,zmin=0,zmax=0;
int tmaxdepth=0;
double txm=1,tym=1,tzm=1;
template<class T>
void find(OctreeNode<T> *& p,double x,double y,double z)
{
double xm=(p->xmax-p->xmin)/2;
double ym=(p->ymax-p->ymin)/2;
double zm=(p->ymax-p->ymin)/2;
times++;
if(x>xmax || x<xmin || y>ymax || y<ymin || z>zmax || z<zmin)
{
cout<<"该点不在场景中！"<<endl;
return;
}
if(x<=p->xmin+txm && x>=p->xmax-txm && y<=p->ymin+tym && y>=p->ymax-tym && z<=p->zmin+tzm && z>=p->zmax-tzm )
{
cout<<endl<<"找到该点！"<<"该点位于"<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<"节点内！"<<endl;
cout<<"共经过"<<times<<"次递归！"<<endl;
}
else if(x<(p->xmax-xm) && y<(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_left_back,x,y,z);
}
else if(x<(p->xmax-xm) && y<(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_left_back,x,y,z);
}
else if(x>(p->xmax-xm) && y<(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_right_back,x,y,z);
}
else if(x>(p->xmax-xm) && y<(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_right_back,x,y,z);
}
else if(x<(p->xmax-xm) && y>(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_left_front,x,y,z);
}
else if(x<(p->xmax-xm) && y>(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_left_front,x,y,z);
}
else if(x>(p->xmax-xm) && y>(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_right_front,x,y,z);
}
else if(x>(p->xmax-xm) && y>(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_right_front,x,y,z);
}
}
//main函数
int main ()
{
OctreeNode<double> * rootNode = NULL;
int choiced = 0;
while(true)
{
system("cls");
cout<<"请选择操作：\n";
cout<<"1.创建八叉树 2.先序遍历八叉树\n";
cout<<"3.查看树深度 4.查找节点 \n";
cout<<"0.退出\n\n";
cin>>choiced;
if(choiced == 0)
return 0;
else if(choiced == 1)
{
system("cls");
cout<<"请输入最大递归深度："<<endl;
cin>>maxdepth;
cout<<"请输入外包盒坐标，顺序如下：xmin,xmax,ymin,ymax,zmin,zmax"<<endl;
cin>>xmin>>xmax>>ymin>>ymax>>zmin>>zmax;
if(maxdepth>=0 || xmax>xmin || ymax>ymin || zmax>zmin || xmin>0 || ymin>0 ||zmin>0)
{
tmaxdepth=cal(maxdepth);
txm=(xmax-xmin)/tmaxdepth;
tym=(ymax-ymin)/tmaxdepth;
tzm=(zmax-zmin)/tmaxdepth;
createOctree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);
}
else
{
cout<<"输入错误！";
return 0;
}
}
else if(choiced == 2)
{
system("cls");
cout<<"先序遍历八叉树结果：\n";
i=1;
preOrder(rootNode);
cout<<endl;
system("pause");
}
else if(choiced == 3)
{
system("cls");
int dep = depth(rootNode);
cout<<"此八叉树的深度为"<<dep+1<<endl;
system("pause");
}
else if(choiced == 4)
{
system("cls");
cout<<"请输入您希望查找的点的坐标，顺序如下：x,y,z\n";
double x,y,z;
cin>>x>>y>>z;
times=0;
cout<<endl<<"开始搜寻该点……"<<endl;
find(rootNode,x,y,z);
system("pause");
}
else
{
system("cls");
cout<<"\n\n错误选择！\n";
system("pause");
}
}
}
代码在C-free下测试可用
采用链式结构存储
C语言基础知识总结大全
注意:只有局部自动变量和形式参数可以作为寄存器变量;一个计算机系统中的寄存器数目有限,不能定义任意多个寄存器变量;局部静态变量不能定义为寄存器变量。 用extern声明的的变量是外部变量,外部变量的意义是某函数可以调用在该函数之后定义的变量。 13.内部函数外部函数 ! 在C语言中不能被其他源文件调用的函数称为内部...
C语言结构体Struct怎么使用?
在Turbo C中，结构也是一种数据类型, 可以使用结构变量，因此，像其它类型的变量一样，在使用结构变量时要先对其定义。如果需要定义多个具有相同形式的结构变量时用这种方法比较方便，它先作结构说明，再用结构名来定义变量。
数据结构算法(C语言描述)和C或C++程序具体什么关系啊
算法和语言没有关系，任何一门功能完整的语言都可以描述算法，但是执行效率和实现者的水平，还有语言本身的执行效率有关。比如java就比c慢很多，所以在很多做题网站上，如果你用java提交，时限一般是几倍的。函数就是所谓的功能，没错，算法可以当函数用（正确来讲，算法本身就包含若干个函数），但是你不...
什么是C语言
4. C语言适用范围大。适合于多种操作系统，如Windows、DOS、UNIX等等；也适用于多种机型。C语言对编写需要硬件进行操作的场合，明显优于其它解释型高级语言，有一些大型应用软件也是用C语言编写的。C语言具有绘图能力强，可移植性，并具备很强的数据处理能力，因此适于编写系统软件，三维，二维图形和动画...
C语言结构体Struct怎么使用?
在C语言中，可以使用结构体（Struct）来存放一组不同类型的数据。结构体的定义形式为：struct 结构体名{ 结构体所包含的变量或数组 };结构体是一种集合，它里面包含了多个变量或数组，它们的类型可以相同，也可以不同，每个这样的变量或数组都称为结构体的成员（Member）。结构体定义：第一种：只有...
c与c++的区别有哪些
4. 头文件调用：C++使用尖括号 >来包含系统头文件，并在使用C语言头文件时，去除.h扩展名并在前面加上"C"前缀。5. 输入输出：C++的输入输出操作通常基于流对象进行，而C语言则依赖于标准输入输出库函数。6. 封装：C语言的封装主要通过结构体实现，而C++的封装特性更为丰富和完善。7. 编程风格：C...
如何用C++编写软件
2，学习了数据结构怎么应用到编写程序里去，我不会。学校里没有学到这样的，可以给我举个例子么，这个用的例子还是很多的,向数据结构中的链表, 百度上就有很多人问如何去写一个学生信息管理程序, 其实你如果学过链表,就可以使用链表来做, 每个学生是一个节点, 可以向链表中添加,删除,学生信息等.....
采用C#开发的C\/S结构应用程序的架构。
还需要通过特殊的端口来通信。明显当遇到防火墙时就会失败。WebService 1：在电子商务行业中应用如把某些通用的逻辑包装起来，供其他公司使用。2：应用集成 使用web service 吧，而且以后你不想使用c\/s结构时候，使用B\/s也是改动最小。
关于C语言的
循环结构可以减少源程序重复书写的工作量,用来描述重复执行某段算法的问题,这是程序设计中最能发挥计算机特长的程序结构,C语言中提供四种循环,即goto循环、while循环、do –while循环和for循环。四种循环可以用来处理同一问题,一般情况下它们可以互相代替换,但一般不提倡用goto循环,因为强制改变程序的顺序经常会给程序的...
如何学好C语言
Stroustrup的《C++语言的设计与演化》(The Design and Evolution of C++)和David R.Hanson 的《C语言接口与实现 创建可重用软件的技术》(C Interfaces and Implaementations Techniques for Creating Reusable Software)一定要看,这两本书讲述了如何用C来实现异常处理、实现类型的封装和扩展等一些大的项目中经常用到...
林养氨曲： 以下程序摘自互联网,是C++的
千山区13923268525： 请教c++八叉树建立问题 - ？
林养氨曲： 先定义一个节点结构,这个节点结构包含一个数据,八个节点指针,这样便可以构造一颗八叉树
千山区13923268525： 二叉树(C语言)怎么创建? - ？
林养氨曲： C语言中二叉树的创建需要用到结构体来定义一个树的数据类型.树这个数据结构有一些数据域,和多个指针域.当然,对于二叉树而言,一般可以定义两个指针域,分别指向root节点的左右子节点.数据结构定义:struct tree{ int data; //这里数据域以此为例 tree*right,*left;}; 真正构建二叉树可以使用动态内存申请,这是一种比较常见的方法(如果不会动态内存申请,可以先看看),但是这样做在子树很多时会耗费较多时间.因此可以事先开辟好一段内存空间用于存储树.比如 tree T[2000];如果需要建立新的子树,那么只需将数组中某个左右子节点赋值即可.如有疑问,欢迎继续追问.
千山区13923268525： 数据结构建树程序,C语言C++皆可 - ？
林养氨曲： #include <stdio.h> #include <stdlib.h> #include<iostream.h> #define maxnode 100 #define NULL 0 typedef char DataType; /*设数据域类型为字符型*/ typedef struct node{ DataType data; struct node *lchild,*rchild; /*左右链域为指向结点结构的指...
千山区13923268525： C++建立二叉树 - ？
林养氨曲： 根据楼主给出的图,可以用下面的代码来进行构建来构建,代码经过实际的运行验证,无错,运行结果是楼主所给的二叉树. 思想:结合先序和中序遍历来构建给定的二叉树. 所给的二叉树图中,先序:A,B,D,E,C,F,G 中序:D,B,E,A,F,C,G 下...
千山区13923268525： 请问C语言如何创建二叉树???? - ？
林养氨曲： 创建二叉树的源程序如下: #include <cstdlib>#include <stdio.h>typedef struct node{ //树的结点int data;struct node* left;struct node* right;} Node;typedef struct{ //树根Node* root;} Tree;void insert(Tree* tree, int value)//创建树{Node* ...
千山区13923268525： 利用链式存储创建二叉树,写出完整程序,(C\C++) - ？
林养氨曲： 线性表的链式存储结构: typedef int elemtype; typedef struct lnode {elemtype data;struct lnode *next; }lnode,*linklist; (被封装好的每个节点,都有一个数据域data和一个指针域*next用于指向下一个节点) 二叉树的二叉链表: typedef int ...
千山区13923268525： 如何用C语言创建二叉树 - ？
林养氨曲： 创建的方法有很多啊 可以用链表,可以用数组,而且你的创建到底是形成一个数据结构,还是实实在在的建树呢 假如这样 struct TreeNode {int data;TreeNode *leftChild;TreeNode *rightChild; }这就是一个树了.你建立很多节点,然后让左右孩子指向你想要的.也是树.
千山区13923268525： 二叉树的建立和遍历(C++) - ？
林养氨曲： 先序遍历 { if(root; PreOrder(root);/访问根节点 PreOrder(root-> typedef BTNode *BinTree;n＂这个代表空格;data=ch;data);/,root->,root->);rchild);/ }BTNode; printf(＂ '/rchild));//中序;/rchild); InOrder(root):＂遍历左子树 PreOrder(root-> struct ...
千山区13923268525： 用vc++编写建立二叉树以及二叉树的先序、中序、后序遍历的程序 - ？
林养氨曲： /*二叉树*/ typedef struct BNode{ DataType data; struct BNode *left,*right; }* LinkTree;/*建立*/ int LinkTreeCreate(LinkTree *T) { DataType d; scanf(＂%t＂,&d); if (d == 0) *T = NULL; else { if ((*T = malloc(sizeof(struct BNode))) == NULL) return -1; ...
