一种可扩展四叉树结构及其先序遍历算法  

An Extended Quadtree Structure and Its Preorder Traversal Algorithm

作　　者：李启青[1] 马建文[1] 哈斯巴干[1] 刘志丽[1] 韩秀珍[1] 

机构地区：[1]中国科学院遥感应用研究所,北京100101

出　　处：《计算机工程与应用》2003年第28期22-23,41,共3页Computer Engineering and Applications

基　　金：国家863高技术研究发展计划项目"遥感数据智能处理技术与集成"(编号:CX020014);奥运科技专项项目(编号:2002BA904B07-2)

摘　　要：在图象处理领域,数据表达是一个核心问题。四叉树数据结构由于比空间占有树组方式使处理具有多分辨率能力而倍受青睐。文章提出并实现了一种可应用于多分辨率图象处理和地理信息数据表达的四叉树结构,该四叉树综合了循环链表和普通树结构的优点。具有较强的可扩展性和通用性,使得同一层次的结点之间可以顺利搜索,从而大大减少了查找和从子孙结点到父结点操作回溯的复杂度。该文对原先的四叉树结构做了相应改进,并给出了该四叉树数据结构的先根序遍历算法,是一种高效的数据结构。Data representation is a kernel problem in image processing field.Quadtree data structure is better than spa-tial array in its multiresolution ability.It is proposed that a special quadtree structure to represent geology information and multiresolution imagery data.The structure integrates the advantage of circle list and tree struture.It can extend to other type of tree structure easily and the implementation can be reused easily.Moreover,the traversal in the same level can be done to reduce the complication from child node to its siblings or from child node to its parent node.The im-provement is given in pre-order traversal algorithm and general quadtree structure.It is a efficient data structure.

关 键 词：四叉树结构 先根次序 遍历算法 游标 图象处理 

分 类 号：TK730.2[交通运输工程—轮机工程]