TITLE:
An Optimal Algorithm for Prufer Codes
AUTHORS:
Xiaodong Wang, Lei Wang, Yingjie Wu
KEYWORDS:
Design of Algorithm, Labeled Trees, Prufer Codes, Integer Sorting
JOURNAL NAME:
Journal of Software Engineering and Applications,
Vol.2 No.2,
July
15,
2009
ABSTRACT: 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.