QuestionQuestion

1.

Chapter 3: Implement an algorithm for reversing a singly linked list. You can use the linked list classes provided in Chapter 3.

This program should ask for the user to input the number of nodes and the values for all the nodes (the values should be of type int).

It should output the reverse of the list.

Your program should be called singlyLinkedListReverse.

2.

Chapter 5: Write a recursive method that takes a character string $ and out- puts its reverse.

For example, the reverse of "potspans" would be"snapstop". This program should for the user to input a string and should output the reverse of that string.

You program should be called stringReverse.

3.

Chapter 8: Implement an algorithm that will perform a preorder traversal of a binary tree.

You can use the Tree class provided in Chapter 8. You should hard code the arithmetic expression tree from Figure 8.6 in Chapter 8 in the book, and your program should output the preorder traversal of that tree.

You should treat all nodes as Strings.

You program should be called preorderTraversal.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

/*
*
*
* Developed for use with the book:
*
*    Data Structures and Algorithms in Java, Sixth Edition
*   
*   
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program.
*/
package net.datastructures;

/**
* Concrete implementation of a binary tree using a node-based, linked structure.
*
* @author
* @author
* @author
*/
public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {

//---------------- nested Node class ----------------
/** Nested static class for a binary tree node. */
protected static class Node<E> implements Position<E> {
    private E element;          // an element stored at this node
    private Node<E> parent;    // a reference to the parent node (if any)
    private Node<E> left;       // a reference to the left child (if any)
    private Node<E> right;      // a reference to the right child (if any)

    /**
    * Constructs a node with the given element and neighbors.
    *
    * @param e the element to be stored
    * @param above       reference to a parent node
    * @param leftChild   reference to a left child node
    * @param rightChild reference to a right child node
    */
    public Node(E e, Node<E> above, Node<E> leftChild, Node<E> rightChild) {
      element = e;
      parent = above;
      left = leftChild;
      right = rightChild;
    }

    // accessor methods
    public E getElement() { return element; }
    public Node<E> getParent() { return parent; }
    public Node<E> getLeft() { return left; }
    public Node<E> getRight() { return right; }

    // update methods
    public void setElement(E e) { element = e; }
    public void setParent(Node<E> parentNode) { parent = parentNode; }
    public void setLeft(Node<E> leftChild) { left = leftChild; }
    public void setRight(Node<E> rightChild) { right = rightChild; }
} //----------- end of nested Node class -----------

/** Factory function to create a new node storing element e. */
protected Node<E> createNode(E e, Node<E> parent,
                                  Node<E> left, Node<E> right) {
    return new Node<E>(e, parent, left, right);
}

// LinkedBinaryTree instance variables
/** The root of the binary tree */
protected Node<E> root = null;    // root of the tree

/** The number of nodes in the binary tree */
private int size = 0;             // number of nodes in the tree

// constructor
/** Construts an empty binary tree. */
public LinkedBinaryTree() { }      // constructs an empty binary tree

// nonpublic utility
/**
   * Verifies that a Position belongs to the appropriate class, and is
   * not one that has been previously removed. Note that our current
   * implementation does not actually verify that the position belongs
   * to this particular list instance.
   *
   * @param p   a Position (that should belong to this tree)
   * @return    the underlying Node instance for the position
   * @throws IllegalArgumentException if an invalid position is detected
   */
protected Node<E> validate(Position<E> p) throws IllegalArgumentException {
    if (!(p instanceof Node))
      throw new IllegalArgumentException("Not valid position type");
    Node<E> node = (Node<E>) p;       // safe cast
    if (node.getParent() == node)    // our convention for defunct node
      throw new IllegalArgumentException("p is no longer in the tree");
    return node;
}

// accessor methods (not already implemented in AbstractBinaryTree)
/**
   * Returns the number of nodes in the tree.
   * @return number of nodes in the tree
   */
@Override
public int size() {
    return size;
}

/**
   * Returns the root Position of the tree (or null if tree is empty).
   * @return root Position of the tree (or null if tree is empty)
   */
@Override
public Position<E> root() {
    return root;
}

/**
   * Returns the Position of p's parent (or null if p is root).
   *
   * @param p    A valid Position within the tree
   * @return Position of p's parent (or null if p is root)
   * @throws IllegalArgumentException if p is not a valid Position for this tree.
   */
@Override
public Position<E> parent(Position<E> p) throws IllegalArgumentException {
    Node<E> node = validate(p);
    return node.getParent();
}

/**
   * Returns the Position of p's left child (or null if no child exists).
   *
   * @param p A valid Position within the tree
   * @return the Position of the left child (or null if no child exists)
   * @throws IllegalArgumentException if p is not a valid Position for this tree
   */
@Override
public Position<E> left(Position<E> p) throws IllegalArgumentException {
    Node<E> node = validate(p);
    return node.getLeft();
}

/**
   * Returns the Position of p's right child (or null if no child exists).
   *
   * @param p A valid Position within the tree
   * @return the Position of the right child (or null if no child exists)
   * @throws IllegalArgumentException if p is not a valid Position for this tree
   */
@Override
public Position<E> right(Position<E> p) throws IllegalArgumentException {
    Node<E> node = validate(p);
    return node.getRight();
}

// update methods supported by this class
/**
   * Places element e at the root of an empty tree and returns its new Position.
   *
   * @param e   the new element
   * @return the Position of the new element
   * @throws IllegalStateException if the tree is not empty
   */
public Position<E> addRoot(E e) throws IllegalStateException {
    if (!isEmpty()) throw new IllegalStateException("Tree is not empty");
    root = createNode(e, null, null, null);
    size = 1;
    return root;
}

/**
   * Creates a new left child of Position p storing element e and returns its Position.
   *
   * @param p   the Position to the left of which the new element is inserted
   * @param e   the new element
   * @return the Position of the new element
   * @throws IllegalArgumentException if p is not a valid Position for this tree
   * @throws IllegalArgumentException if p already has a left child
   */
public Position<E> addLeft(Position<E> p, E e)
                         throws IllegalArgumentException {
    Node<E> parent = validate(p);
    if (parent.getLeft() != null)
      throw new IllegalArgumentE...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$50.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats