Java Software Structures, 4th Edition Exercise Solutions, Ch. 10
Chapter 10 Exercise Solutions
EX 10.1 Develop a pseudocode algorithm for a level-order traversal of a binary tree.
Create a new queue(traversalQueue) and add the root to the queue
Create a list(resultsList) to hold the resulting traversal
EX 10.2 Draw either a matrilineage (following your mother’s lineage) or a patrilineage (following
your father’s lineage) diagram for a couple of generations. Develop a pseudocode
algorithm for inserting a person into their proper place in the tree.
EX 10.3 Develop a pseudocode algorithm to build an expression tree from a prefix expression.
Create an expressiontree stack
Create an operator stack
While there is input
{
get the next term
if the term is an operand
}
While the operator stack is not empty
{
pop one operator from the operator stack
pop two nodes from the expression tree stack
EX 10.4 Develop a pseudocode algorithm to build an expression tree from an infix expression.
This algorithm handles infix expressions without parenthesis or brackets
Create an expression tree stack
{
get the next term
if the term is an operand
{
create a node containing the operand
push the node onto the expression tree stack
{
While the operator stack is not empty and the operator has precedence over the
one on top of the stack
{
pop the operator off of the operator stack
pop two nodes off of the expression tree stack
{
pop the operator off of the operator stack
pop two nodes off of the expression tree stack
EX 10.5 Calculate the time complexity of the find method.
EX 10.6 Calculate the time complexity of the iteratorInOrder method.
EX 10.7 Develop a pseudocode algorithm for the size method assuming that there is not a count
variable.
Java Software Structures, 4th Edition Exercise Solutions, Ch. 10
EX 10.8 Develop a pseudocode algorithm for the isEmpty operation assuming that there is not a
count variable.
EX 10.9 Draw an expression tree for the expression (9 + 4) * 5 + (4 – (6 – 3)).
+
*
–