Destructor and Purge Member Functions

The destructor for the BinaryTree class is defined in Program . It simply calls the Purge member function to do the job. The Purge member function is part of the Container class interface which all container instance must provide. The purpose of the Purge routine is to delete all the owned objects in the container and to return the container to its initial empty state.

  
Program: BinaryTree Class Purge Member Function and Destructor Definitions

Clearly the Purge function has nothing to do if the tree is already the empty tree. If the tree is not the empty tree, then the Purge function has some cleaning-up to do. It begins by deleting the root only if the binary tree is the owner of the contained objects. Then, because a tree always owns its subtrees, the Purge routine deletes the left and right subtrees.

Suppose the binary tree contains n non-empty nodes. Theorem  tells us that there are n+1 empty nodes. Altogether there are 2n+1=O(n) nodes. Therefore, the running time of Purge is in the worst case.

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