前序
也称为四叉树或四叉树。四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等，而八叉树（Octree）主要应用于3D图形处理。对游戏编程，这会很有用。本文重点介绍了四叉树和四叉树的原理和结构，有助于在头脑中构建四叉树和四叉树的基本思想。 本文并不同时深入求解这两种数据结构，而是仅对四叉树进行深入研究。 这是因为四叉树的构建可以通过四叉树的构建来推测。 如果有不足的地方，希望不遗余力地加以改善。 欢迎使用^ _ ^ email:chanxinhang @ Gmail.com
四叉树与八叉树的结构与原理
四叉树是树的数据结构。 四叉树的定义可以在每个节点下最多具有四个子节点，通常将二维空间的一部分细分为四个象限或者区域，并将该区域内的相关信息存储在四叉树节点中。 该区域可以是正方形、矩形或任意形状。 以下是四叉树的二维空间结构(左)和存储结构(右)的图像。 请注意节点的颜色和网格的边框颜色。
四叉树中的每个节点表示一个矩形区域，上图中的黑色根节点表示最外围的黑框矩形区域，每个矩形区域再划分为四个小矩形区域，这四个小矩形区域就是四个子节点表示的矩形区域。
对于四叉树，四叉树将场景从二维空间扩展到了三维空间。 八分树(Octree )被定义为，如果不是空树，树上的任何节点的子节点都不会有正好8个，或者零个，也就是说子节点不会有0和8以外的数。 那么，这个用来做什么？ 想象一下立方体。 最少可以切几个相同等份的小立方体？ 答案是八个。 八叉树的结构图如下所示。
四叉树存储结构的c语言描述：
/*一个矩形区域的四象限划分：ul(1(|ur(0(--------|----ll ) )|lr ) ) (3)以下为此四象限类型的枚举*/typedefenum /* }quadrect_t； /*quadrect_t{quadrect_trect； //节点表示的矩形区域list_t *lst_object； //节点数据、节点类型一般为链表，多个对象struct quadnode_t *sub[4]； //指向节点的四个孩子}quadnode_t； /*quadnode_t{quadnode_t*root； int depth； }四叉树_ t；
四叉树的建立
1、利用四叉树划分网格，如本文第一张图绘制四层完全四叉树结构的图像，由左图的网格图形建立如右图的完全四叉树。
伪代码：
funtionquadtreebuild(Depth，rect ) )。
{
四叉树深度=深度；
/*创建分支、根树的根、深度和根节点表示的矩形区域*/
quadcreatebranch(root，depth，rect )；
}
funtionquadcreatebranch(n，depth，rect )。
{
深度！=0)
{
n=new node； //开辟新节点
n -rect=rect； //将该节点表示的矩形领域收纳在该节点中
将rect转换为四个rect[UR]、rect[UL]、rect[LL]、rect[LR]；
/*创建每个孩子的分支*
quadcreatebranch(n-sub[ur]，depth-1，rect [UR] )；
quadcreatebranch(n-sub[ul]，depth-1
, rect [UL] );QuadCreateBranch ( n->sub[LL], depth-1, rect [LL] );
QuadCreateBranch ( n->sub[LR], depth-1, rect [LR] );
}
}
2、假设在一个矩形区域里有N个对象，如下左图一个黑点代表一个对象，每个对象的坐标位置都是已知的，用四叉树的一个节点存储一个对象，构建成如下右图所示的四叉树。
方法也是采用递归的方法对该矩形进行划分分区块，分完后再往里分，直到每一个子矩形区域里只包含一个对象为止。
伪码：
Funtion QuadtreeBuild()
{
Quadtree = {empty}；
For (i = 1;i<n;i++) //遍历所有对象
{
QuadInsert(i, root)；//将i对象插入四叉树
}
剔除多余的节点； //执行完上面循环后，四叉树中可能有数据为空的叶子节点需要剔除
}
Funtion QuadInsert(i,n) //该函数插入后四叉树中的每个节点所存储的对象数量不是1就是0
{
if（节点n有孩子）
{
通过划分区域判断i应该放置于n节点的哪一个孩子节点c；
QuadInsert(i,c)；
}
else if（节点n存储了一个对象）
{
为n节点创建四个孩子；
将n节点中的对象移到它应该放置的孩子节点中；
通过划分区域判断i应该放置于n节点的哪一个孩子节点c；
QuadInsert(i,c)；
}
else if（n节点数据为空）
{
将i存储到节点n中；
}
}
（以上两种建立方法作为举一反三之用）
用四叉树查找某一对象
1、采用盲目搜索，与二叉树的递归遍历类似，可采用后序遍历或前序遍历或中序遍历对其进行搜索某一对象，时间复杂度为O（n）。
2、根据对象在区域里的位置来搜索，采用分而治之思想，时间复杂度只与四叉树的深度有关。比起盲目搜索，这种搜索在区域里的对象越多时效果越明显
伪码：
Funtion find ( n, pos, )
{
If (n节点所存的对象位置为 pos所指的位置 )
Return n;
If ( pos位于第一象限 )
temp = find ( n->sub[UR], pos );
else if ( pos位于第二象限)
temp = find ( n->sub[UL], pos );
else if ( pos位于第三象限 )
temp = find ( n->sub[LL], pos );
else //pos 位于第四象限
temp = find ( n->sub[LR], pos );
return temp;
}
结语：
熟话说：结构之法，算法之道。多一种数据结构就多一种解决问题的方法，多一种方法就多一种思维模式。祝君学习愉快！^_^
==============================================
声明：版权所有，转载请注明出处： http://blog.csdn.net/zhanxinhang/article/details/6706217
参考：维基百科、百度百科
参考：CS267: Lecture 24, Apr 11 1996 Fast Hierarchical Methods for the N-body Problem, Part 1