基于前缀编码的先根遍历树生成算法的研究与应用  

ON GENERATION ALGORITHM OF PREFIX CODE-BASED PREORDER TRAVERSAL TREE AND ITS APPLICATION

作　　者：况立群[1] 熊风光[1] 韩燮[1] 

机构地区：[1]中北大学电子与计算机科学技术学院,山西太原030051

出　　处：《计算机应用与软件》2011年第4期67-70,94,共5页Computer Applications and Software

基　　金：国家重点自然科学基金项目(60532080)

摘　　要：在管理信息系统的层次分类树中,为了快速查询分类信息并高效地生成层次分类子树,提出了一种基于前缀编码的先根遍历树生成算法。该算法中的节点采用前缀编码的数据结构,便于快速检索出子树节点集合;在构造子树时预先对其进行先根遍历,产生有序遍历表,同时记录最近各层节点的信息,使得建立子树的效率得到大幅提高。最后通过实例验证了所提算法的有效性,为管理信息系统中层次分类树的建立提供了可行的解决途径。In hierarchical classification tree in management information system,in order to query classification information quickly and to generate hierarchical sub-tree efficiently,a generation algorithm of prefix code-based preorder traversal tree is proposed.In the algorithm the nodes use prefix encoded data structure,which enables to facilitate fast retrieval of a collection of sub-tree nodes.When constructing a sub-tree,the preorder traversal is conducted on it in advance to build an orderly traversal table,and the information of recent nodes on each layer are recorded simultaneously,so the substantial improvement in the efficiency of building a sub-tree is achieved.In the end of the paper the validity of the proposed algorithm is verified with an example;the algorithm provides a feasible way of solving the establishment of hierarchical classification tree in management information system.

关 键 词：前缀树 递归树 树生成算法 先根遍历 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]