文章基本信息

标题：An Optimal Algorithm for Prufer Codes
本地全文：下载
作者：Xiaodong Wang ; Lei Wang ; Yingjie Wu 等
期刊名称：Journal of Software Engineering and Applications
印刷版ISSN：1945-3116
电子版ISSN：1945-3124
出版年度：2009
卷号：2
期号：2
页码：111-115
DOI：10.4236/jsea.2009.22016
出版社：Scientific Research Publishing
摘要：This paper studies the algorithms for coding and decoding Prufer codes of a labeled tree. The algorithms for coding and decoding Prufer codes of a labeled tree in the literatures require time usually. Although there exist linear time algorithms for Prufer-like codes [1,2,3], the algorithms utilize the integer sorting algorithms. The special range of the integers to be sorted is utilized to obtain a linear time integer sorting algorithm. The Prufer code problem is reduced to integer sorting. In this paper we consider the Prufer code problem in a different angle and a more direct manner. We start from a naïve algorithm, then improved it gradually and finally we obtain a very practical linear time algorithm. The techniques we used in this paper are of interest in their own right.
关键词：Design of Algorithm; Labeled Trees; Prufer Codes; Integer Sorting