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

Tree Generation Algorithm Based on Prefix Code

为了使树生成算法更为通用且效率更高,提出一种基于前缀编码的树生成算法.算法中的节点采用前缀编码的数据结构,便于用户对树中节点及其下层子节点上的关联数据进行快速查询和统计.由于在构造树之前已采用先根遍历的方式对节点进行了排序,同时建树过程中记录了最近各层节点的信息,因此无需搜索节点的上下层信息就可直接建立起树,大幅提高了建树效率,算法时间复杂度为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.