Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Heap-Ordered Binomial Trees

Since binomial trees are simply general trees with a special shape, we can make use of the GeneralTree class presented in Section gif to implement the BinomialTree class. (See Figure gif).

Program gif introduces the BinomialQueue class and the inner class BinomialTree. The BinomialTree class extends the GeneralTree class introduced in Program gif.

No new fields a declared in the BinomialTree class. Remember that the implementation of the GeneralTree class uses a linked list to contain the pointers to the subtrees, since the degree of a node in a general tree may be arbitrarily large. Also, the GeneralTree class already keeps track of the degree of a node in its degree field. Since the degree of the root node of a binomial tree of order k is k, it is not necessary to keep track of the order explicitly. The degree variable serves this purpose nicely.

   program26388
Program: BinomialTree class.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.