一种基于前缀编码的树生成算法  

Tree Generation Algorithm Based on Prefix Code

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

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

出　　处：《小型微型计算机系统》2010年第5期849-852,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60532080)资助

摘　　要：为了使树生成算法更为通用且效率更高,提出一种基于前缀编码的树生成算法.算法中的节点采用前缀编码的数据结构,便于用户对树中节点及其下层子节点上的关联数据进行快速查询和统计.由于在构造树之前已采用先根遍历的方式对节点进行了排序,同时建树过程中记录了最近各层节点的信息,因此无需搜索节点的上下层信息就可直接建立起树,大幅提高了建树效率,算法时间复杂度为O(n).该算法无需额外的数据预处理即可构造任意子树,且不会增加算法复杂度.In order to make the tree generation algorithm more general and to improve its operating efficiency,a tree generation algorithm based on the prefix code （TGABPC） is proposed. The nodes use prefix encoded data structure,which enables to facilitate fast queries and statistics on the data associated with the tree nodes and their lower sub-nodes. Because the nodes are sorted by preorder traversal before constructing a tree,and the recent nodes information on each layer are being recorded during building the tree,so the tree can be established directly without searching upper and lower nodes. As a result,a substantial increase in the efficiency of building a tree is achieved-the algorithm time complexity is O （n）.The TGABPC can also construct an arbitrary sub-tree without any additional data pre-processing,and does not increase the algorithm complexity.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]