Linear algorithms on recursive representations of trees

摘要

A recursive labeling of a tree T with M vertices is any assignment of the labels 1, 2,…, M to the vertices of T which has the property that every vertex, except the vertex labeled ‘1’ is adjacent to exactly one vertex with a smaller label. A corresponding recursive representation of T is the array C(2), C(3),…, C(M), where C(i) is the unique vertex adjacent to i having a smaller label. In this paper we discuss the feasibility, advantages and relative efficiency of using this representation to design algorithms on trees.