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

getKey and getSubtree Methods

Program gif defines the various GeneralTree class methods for manipulating general trees. The getKey method is a field accessor that simply returns the object contained by the root node of the tree. Clearly, its running time is O(1).

   program15930
Program: GeneralTree class getKey, getSubtree, attachSubtreeand detachSubtree methods.

The getSubtree method takes as its argument an int, i, which must be between 0 and tex2html_wrap_inline62812, where degree is the degree of the root node of the tree. It returns the tex2html_wrap_inline62814 subtree of the given tree. The getSubtree method simply takes i steps down the linked list and returns the appropriate subtree. Assuming that i is valid, the worst case running time for getSubtree is O(d), where tex2html_wrap_inline62818 is the degree of the root node of the tree.


next up previous contents index

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