Main Page

Previous Page
Next Page

[Page 1037 (continued)]

Answers to Self-Review Exercises


a) referential. b) new. c) stack. d) predicate. e) first-in, first-out (FIFO). f) link. g) delete. h) queue. i) tree. j) last-in, first-out (LIFO). k) binary. l) root. m) child or subtree. n) leaf. o) inorder, preorder, postorder and level order.


It is possible to insert a node anywhere in a linked list and remove a node from anywhere in a linked list. Nodes in a stack may only be inserted at the top of the stack and removed from the top of a stack.


A queue data structure allows nodes to be removed only from the head of the queue and inserted only at the tail of the queue. A queue is referred to as a first-in, first-out (FIFO) data structure. A stack data structure allows nodes to be added to the stack and removed from the stack only at the top. A stack is referred to as a last-in, first-out (LIFO) data structure.


  1. Classes allow us to instantiate as many data structure objects of a certain type (i.e., class) as we wish.

  2. Class templates enable us to instantiate related classes, each based on different type parameterswe can then generate as many objects of each template class as we like.

  3. Inheritance enables us to reuse code from a base class in a derived class, so that the derived-class data structure is also a base-class data structure (with public inheritance, that is).

  4. Private inheritance enables us to reuse portions of the code from a base class to form a derived-class data structure; because the inheritance is private, all public base-class member functions become private in the derived class. This enables us to prevent clients of the derived-class data structure from accessing base-class member functions that do not apply to the derived class.

  5. Composition enables us to reuse code by making a class object data structure a member of a composed class; if we make the class object a private member of the composed class, then the class object's public member functions are not available through the composed object's interface.


The inorder traversal is

11 18 19 28 32 40 44 49 69 71 72 83 92 97 99

The preorder traversal is

49 28 18 11 19 40 32 44 83 71 69 72 97 92 99

The postorder traversal is

11 19 18 32 44 40 28 69 72 71 92 99 97 83 49

Previous Page
Next Page