Hu82] and [Knu73b].
The Hu-Tucker algorithm consists of three phases: Combination, Level Assignment, and Reconstruction. During the first phase, Combination, the initial sequence of nodes is used to build an optimal tree, which is not necessary alphabetic. At this stage the minimality of the cost of the tree is achieved.
During the second stage, Level Assignment, the tree obtained in step one is traversed and the levels of the terminal nodes are calculated, beginning at the root of the tree, which is at level 0. At the end of stage two, the tree obtained in stage one is disregarded.
Stage three, Recombination, builds an optimal alphabetic binary tree bottom up, from the initial sequence of nodes and their corresponding level assignments produced at the end of stage two, by combining adjacent nodes which have the same levels (level by level construction). The resulting Hu-Tucker tree is an optimal alphabetic binary tree.
-- Respectfully, Roger L. Bagula tftn@..., 11759Waterhill Road, Lakeside,Ca 92040-2905,tel: 619-5610814 : URL : http://home.earthlink.net/~tftn URL : http://victorian.fortunecity.com/carmelita/435/