Wrap-Up

Answers to Self Review Exercises

21.1	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.
21.2	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.
21.3	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.
21.4	Classes allow us to instantiate as many data structure objects of a certain type (i.e., class) as we wish. 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. 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). 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. 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.
21.5	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

Exercises

21.6	Write a program that concatenates two linked list objects of characters. The program should include function concatenate, which takes references to both list objects as arguments and concatenates the second list to the first list.
21.7	Write a program that merges two ordered list objects of integers into a single ordered list object of integers. Function merge should receive references to each of the list objects to be merged and reference to a list object into which the merged elements will be placed.
21.8	Write a program that inserts 25 random integers from 0 to 100 in order in a linked list object. The program should calculate the sum of the elements and the floating-point average of the elements.
21.9	Write a program that creates a linked list object of 10 characters and creates a second list object containing a copy of the first list, but in reverse order.
21.10	Write a program that inputs a line of text and uses a stack object to print the line reversed.
21.11	Write a program that uses a stack object to determine if a string is a palindrome (i.e., the string is spelled identically backward and forward). The program should ignore spaces and punctuation.
21.12	Stacks are used by compilers to help in the process of evaluating expressions and generating machine language code. In this and the next exercise, we investigate how compilers evaluate arithmetic expressions consisting only of constants, operators and parentheses. Humans generally write expressions like 3 + 4 and 7 / 9 in which the operator (+ or / here) is written between its operandsthis is called infix notation. Computers "prefer" postfix notation in which the operator is written to the right of its two operands. The preceding infix expressions would appear in postfix notation as 3 4 + and 7 9 /, respectively. To evaluate a complex infix expression, a compiler would first convert the expression to postfix notation and evaluate the postfix version of the expression. Each of these algorithms requires only a single left-to-right pass of the expression. Each algorithm uses a stack object in support of its operation, and in each algorithm the stack is used for a different purpose. In this exercise, you will write a C++ version of the infix-to-postfix conversion algorithm. In the next exercise, you will write a C++ version of the postfix expression evaluation algorithm. Later in the chapter, you will discover that code you write in this exercise can help you implement a complete working compiler. Write a program that converts an ordinary infix arithmetic expression (assume a valid expression is entered) with single-digit integers such as (6 + 2) * 5 - 8 / 4   to a postfix expression. The postfix version of the preceding infix expression is 6 2 + 5 * 8 4 / -   The program should read the expression into character array infix and use modified versions of the stack functions implemented in this chapter to help create the postfix expression in character array postfix. The algorithm for creating a postfix expression is as follows: Push a left parenthesis '(' onto the stack. Append a right parenthesis ')' to the end of infix. While the stack is not empty, read infix from left to right and do the following: If the current character in infix is a digit, copy it to the next element of postfix. If the current character in infix is a left parenthesis, push it onto the stack. If the current character in infix is an operator, Pop operators (if there are any) at the top of the stack while they have equal or higher precedence than the current operator, and insert the popped operators in postfix. Push the current character in infix onto the stack. If the current character in infix is a right parenthesis Pop operators from the top of the stack and insert them in postfix until a left parenthesis is at the top of the stack. Pop (and discard) the left parenthesis from the stack. The following arithmetic operations are allowed in an expression: + addition - subtraction * multiplication / division ^ exponentiation % modulus [Note: We assume left to right associativity for all operators for the purpose of this exercise.] The stack should be maintained with stack nodes, each containing a data member and a pointer to the next stack node. Some of the functional capabilities you may want to provide are: function convertToPostfix that converts the infix expression to postfix notation function isOperator that determines whether c is an operator function precedence that determines whether the precedence of operator1 is less than, equal to or greater than the precedence of operator2 (the function returns1, 0 and 1, respectively) function push that pushes a value onto the stack function pop that pops a value off the stack function stackTop that returns the top value of the stack without popping the stack function isEmpty that determines if the stack is empty function printStack that prints the stack
21.13	Write a program that evaluates a postfix expression (assume it is valid) such as 6 2 + 5 * 8 4 / -   The program should read a postfix expression consisting of digits and operators into a character array. Using modified versions of the stack functions implemented earlier in this chapter, the program should scan the expression and evaluate it. The algorithm is as follows: Append the null character ('') to the end of the postfix expression. When the null character is encountered, no further processing is necessary. While '' has not been encountered, read the expression from left to right. If the current character is a digit, Push its integer value onto the stack (the integer value of a digit character is its value in the computer's character set minus the value of '0' in the computer's character set). Otherwise, if the current character is an operator, Pop the two top elements of the stack into variables x and y. Calculate y operator x. Push the result of the calculation onto the stack. When the null character is encountered in the expression, pop the top value of the stack. This is the result of the postfix expression. [Note: In Step 2 above, if the operator is '/', the top of the stack is 2 and the next element in the stack is 8, then pop 2 into x, pop 8 into y, evaluate 8 / 2 and push the result, 4, back onto the stack. This note also applies to operator '-'.] The arithmetic operations allowed in an expression are + addition subtraction * multiplication / division ^ exponentiation % modulus [Note: We assume left to right associativity for all operators for the purpose of this exercise.] The stack should be maintained with stack nodes that contain an int data member and a pointer to the next stack node. You may want to provide the following functional capabilities: function evaluatePostfixExpression that evaluates the postfix expression function calculate that evaluates the expression op1 operator op2 function push that pushes a value onto the stack function pop that pops a value off the stack function isEmpty that determines if the stack is empty function printStack that prints the stack
21.14	Modify the postfix evaluator program of Exercise 21.13 so that it can process integer operands larger than 9.
21.15	(Supermarket Simulation) Write a program that simulates a checkout line at a supermarket. The line is a queue object. Customers (i.e., customer objects) arrive in random integer intervals of 14 minutes. Also, each customer is served in random integer intervals of 14 minutes. Obviously, the rates need to be balanced. If the average arrival rate is larger than the average service rate, the queue will grow infinitely. Even with "balanced" rates, randomness can still cause long lines. Run the supermarket simulation for a 12-hour day (720 minutes) using the following algorithm: Choose a random integer between 1 and 4 to determine the minute at which the first customer arrives. At the first customer's arrival time: Determine customer's service time (random integer from 1 to 4); Begin servicing the customer; Schedule arrival time of next customer (random integer 1 to 4 added to the current time). For each minute of the day: If the next customer arrives, Say so, Enqueue the customer; Schedule the arrival time of the next customer; If service was completed for the last customer; Say so Dequeue next customer to be serviced Determine customer's service completion time (random integer from 1 to 4 added to the current time). Now run your simulation for 720 minutes, and answer each of the following: What is the maximum number of customers in the queue at any time? What is the longest wait any one customer experiences? What happens if the arrival interval is changed from 14 minutes to 13 minutes?
21.16	Modify the program of Figs. 21.2021.22 to allow the binary tree object to contain duplicates.
21.17	Write a program based on Figs. 21.2021.22 that inputs a line of text, tokenizes the sentence into separate words (you may want to use the strtok library function), inserts the words in a binary search tree and prints the inorder, preorder and postorder traversals of the tree. Use an OOP approach.
21.18	In this chapter, we saw that duplicate elimination is straightforward when creating a binary search tree. Describe how you would perform duplicate elimination using only a one-dimensional array. Compare the performance of array-based duplicate elimination with the performance of binary-search-tree-based duplicate elimination.
21.19	Write a function depth that receives a binary tree and determines how many levels it has.
21.20	(Recursively Print a List Backward) Write a member function printListBackward that recursively outputs the items in a linked list object in reverse order. Write a test program that creates a sorted list of integers and prints the list in reverse order.
21.21	(Recursively Search a List) Write a member function searchList that recursively searches a linked list object for a specified value. The function should return a pointer to the value if it is found; otherwise, null should be returned. Use your function in a test program that creates a list of integers. The program should prompt the user for a value to locate in the list.
21.22	(Binary Tree Delete) In this exercise, we discuss deleting items from binary search trees. The deletion algorithm is not as straightforward as the insertion algorithm. There are three cases that are encountered when deleting an itemthe item is contained in a leaf node (i.e., it has no children), the item is contained in a node that has one child or the item is contained in a node that has two children. If the item to be deleted is contained in a leaf node, the node is deleted and the pointer in the parent node is set to null. If the item to be deleted is contained in a node with one child, the pointer in the parent node is set to point to the child node and the node containing the data item is deleted. This causes the child node to take the place of the deleted node in the tree. The last case is the most difficult. When a node with two children is deleted, another node in the tree must take its place. However, the pointer in the parent node cannot be assigned to point to one of the children of the node to be deleted. In most cases, the resulting binary search tree would not adhere to the following characteristic of binary search trees (with no duplicate values): The values in any left subtree are less than the value in the parent node, and the values in any right subtree are greater than the value in the parent node. Which node is used as a replacement node to maintain this characteristic? Either the node containing the largest value in the tree less than the value in the node being deleted, or the node containing the smallest value in the tree greater than the value in the node being deleted. Let us consider the node with the smaller value. In a binary search tree, the largest value less than a parent's value is located in the left subtree of the parent node and is guaranteed to be contained in the rightmost node of the subtree. This node is located by walking down the left subtree to the right until the pointer to the right child of the current node is null. We are now pointing to the replacement node, which is either a leaf node or a node with one child to its left. If the replacement node is a leaf node, the steps to perform the deletion are as follows: Store the pointer to the node to be deleted in a temporary pointer variable (this pointer is used to delete the dynamically allocated memory). Set the pointer in the parent of the node being deleted to point to the replacement node. Set the pointer in the parent of the replacement node to null. Set the pointer to the right subtree in the replacement node to point to the right subtree of the node to be deleted. Delete the node to which the temporary pointer variable points. The deletion steps for a replacement node with a left child are similar to those for a replacement node with no children, but the algorithm also must move the child into the replacement node's position in the tree. If the replacement node is a node with a left child, the steps to perform the deletion are as follows: Store the pointer to the node to be deleted in a temporary pointer variable. Set the pointer in the parent of the node being deleted to point to the replacement node. Set the pointer in the parent of the replacement node to point to the left child of the replacement node. Set the pointer to the right subtree in the replacement node to point to the right subtree of the node to be deleted. Delete the node to which the temporary pointer variable points. Write member function deleteNode, which takes as its arguments a pointer to the root node of the tree object and the value to be deleted. The function should locate in the tree the node containing the value to be deleted and use the algorithms discussed here to delete the node. The function should print a message that indicates whether the value is deleted. Modify the program of Figs. 21.2021.22 to use this function. After deleting an item, call the inOrder, preOrder and postOrder TRaversal functions to confirm that the delete operation was performed correctly.
21.23	(Binary Tree Search) Write member function binaryTreeSearch, which attempts to locate a specified value in a binary search tree object. The function should take as arguments a pointer to the root node of the binary tree and a search key to be located. If the node containing the search key is found, the function should return a pointer to that node; otherwise, the function should return a null pointer.
21.24	(Level-Order Binary Tree Traversal) The program of Figs. 21.2021.22 illustrated three recursive methods of traversing a binary treeinorder, preorder and postorder traversals. This exercise presents the level-order traversal of a binary tree, in which the node values are printed level by level, starting at the root node level. The nodes on each level are printed from left to right. The levelorder traversal is not a recursive algorithm. It uses a queue object to control the output of the nodes. The algorithm is as follows: Insert the root node in the queue While there are nodes left in the queue, Get the next node in the queue Print the node's value If the pointer to the left child of the node is not null Insert the left child node in the queue If the pointer to the right child of the node is not null Insert the right child node in the queue. Write member function levelOrder to perform a level-order traversal of a binary tree object. Modify the program of Figs. 21.2021.22 to use this function. [Note: You will also need to modify and incorporate the queue-processing functions of Fig. 21.16 in this program.]
21.25	(Printing Trees) Write a recursive member function outputTree to display a binary tree object on the screen. The function should output the tree row by row, with the top of the tree at the left of the screen and the bottom of the tree toward the right of the screen. Each row is output vertically. For example, the binary tree illustrated in Fig. 21.24 is output as follows: 99 97 92 83 72 71 69 49 44 40 32 28 19 18 11     Note that the rightmost leaf node appears at the top of the output in the rightmost column and the root node appears at the left of the output. Each column of output starts five spaces to the right of the previous column. Function outputTree should receive an argument totalSpaces representing the number of spaces preceding the value to be output (this variable should start at zero, so the root node is output at the left of the screen). The function uses a modified inorder traversal to output the treeit starts at the rightmost node in the tree and works back to the left. The algorithm is as follows: While the pointer to the current node is not null Recursively call outputTree with the right subtree of the current node and totalSpaces + 5 Use a for structure to count from 1 to totalSpaces and output spaces Output the value in the current node Set the pointer to the current node to point to the left subtree of the current node Increment totalSpaces by 5.