C-8.45 page 353 (each algorithm is 30 points and running time is 10 points) Add

ID: 3690014 • Letter: C

Question

C-8.45 page 353 (each algorithm is 30 points and running time is 10 points)

Add the running time as a comment inside your algorithms implementation.

Using the algorithms provided in the attached file, implement and test the following problem:

(Problem C-8.45, page 353 of the text)

• preorderNext(p): Return the position visited after p in a preorder traversal

of T (or null if p is the last node visited).

• inorderNext(p): Return the position visited after p in an inorder traversal

of T (or null if p is the last node visited).

• postorderNext(p): Return the position visited after p in a postorder traversal

of T (or null if p is the last node visited).

What are the worst-case running times of your algorithms?

Tree.java

/*
* Copyright 2014, Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
*
* Developed for use with the book:
*
* Data Structures and Algorithms in Java, Sixth Edition
* Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
* John Wiley & Sons, 2014
*
* 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. If not, see <http://www.gnu.org/licenses/>.
*/
//package net.datastructures;

import java.util.Iterator;

/**
* An interface for a tree where nodes can have an arbitrary number of children.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
public interface Tree<E> extends Iterable<E> {

/**
* 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)
*/
Position<E> 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.
*/
Position<E> parent(Position<E> p) throws IllegalArgumentException;

/**
* Returns the number of children of Position p.
*
* @param p A valid Position within the tree
* @return number of children of Position p
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
int numChildren(Position<E> p) throws IllegalArgumentException;

/**
* Returns true if Position p has one or more children.
*
* @param p A valid Position within the tree
* @return true if p has at least one child, false otherwise
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
boolean isInternal(Position<E> p) throws IllegalArgumentException;

/**
* Returns true if Position p does not have any children.
*
* @param p A valid Position within the tree
* @return true if p has zero children, false otherwise
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
boolean isExternal(Position<E> p) throws IllegalArgumentException;

/**
* Returns true if Position p represents the root of the tree.
*
* @param p A valid Position within the tree
* @return true if p is the root of the tree, false otherwise
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
boolean isRoot(Position<E> p) throws IllegalArgumentException;

/**
* Returns the number of nodes in the tree.
* @return number of nodes in the tree
*/
int size();

/**
* Tests whether the tree is empty.
* @return true if the tree is empty, false otherwise
*/
boolean isEmpty();

/**
* Returns an iterator of the elements stored in the tree.
* @return iterator of the tree's elements
*/
Iterator<E> iterator();

/**
* Returns an iterable collection of the positions of the tree.
* @return iterable collection of the tree's positions
*/
Iterable<Position<E>> positions();
}

Position.java

/**
* An interface for a position which is an abstraction for the
* location at which a single element is stored in a positional
* container.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
public interface Position<E> {
/**
* Returns the element stored at this position.
*
* @return the stored element
* @throws IllegalStateException if position no longer valid
*/
E getElement() throws IllegalStateException;
}

LinkedBinaryTree.java

/**
* Concrete implementation of a binary tree using a node-based, linked structure.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
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 IllegalArgumentException("p already has a left child");
Node<E> child = createNode(e, parent, null, null);
parent.setLeft(child);
size++;
return child;
}

/**
* Creates a new right child of Position p storing element e and returns its Position.
*
* @param p the Position to the right 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 right child
*/
public Position<E> addRight(Position<E> p, E e)
throws IllegalArgumentException {
Node<E> parent = validate(p);
if (parent.getRight() != null)
throw new IllegalArgumentException("p already has a right child");
Node<E> child = createNode(e, parent, null, null);
parent.setRight(child);
size++;
return child;
}

/**
* Replaces the element at Position p with element e and returns the replaced element.
*
* @param p the relevant Position
* @param e the new element
* @return the replaced element
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
public E set(Position<E> p, E e) throws IllegalArgumentException {
Node<E> node = validate(p);
E temp = node.getElement();
node.setElement(e);
return temp;
}

/**
* Attaches trees t1 and t2, respectively, as the left and right subtree of the
* leaf Position p. As a side effect, t1 and t2 are set to empty trees.
*
* @param p a leaf of the tree
* @param t1 an independent tree whose structure becomes the left child of p
* @param t2 an independent tree whose structure becomes the right child of p
* @throws IllegalArgumentException if p is not a valid Position for this tree
* @throws IllegalArgumentException if p is not a leaf
*/
public void attach(Position<E> p, LinkedBinaryTree<E> t1,
LinkedBinaryTree<E> t2) throws IllegalArgumentException {
Node<E> node = validate(p);
if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf");
size += t1.size() + t2.size();
if (!t1.isEmpty()) { // attach t1 as left subtree of node
t1.root.setParent(node);
node.setLeft(t1.root);
t1.root = null;
t1.size = 0;
}
if (!t2.isEmpty()) { // attach t2 as right subtree of node
t2.root.setParent(node);
node.setRight(t2.root);
t2.root = null;
t2.size = 0;
}
}

/**
* Removes the node at Position p and replaces it with its child, if any.
*
* @param p the relevant Position
* @return element that was removed
* @throws IllegalArgumentException if p is not a valid Position for this tree.
* @throws IllegalArgumentException if p has two children.
*/
public E remove(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
if (numChildren(p) == 2)
throw new IllegalArgumentException("p has two children");
Node<E> child = (node.getLeft() != null ? node.getLeft() : node.getRight() );
if (child != null)
child.setParent(node.getParent()); // child's grandparent becomes its parent
if (node == root)
root = child; // child becomes root
else {
Node<E> parent = node.getParent();
if (node == parent.getLeft())
parent.setLeft(child);
else
parent.setRight(child);
}
size--;
E temp = node.getElement();
node.setElement(null); // help garbage collection
node.setLeft(null);
node.setRight(null);
node.setParent(node); // our convention for defunct node
return temp;
}
} //----------- end of LinkedBinaryTree class -----------

BinaryTree.java

/**
* An interface for a binary tree, in which each node has at most two children.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
public interface BinaryTree<E> extends Tree<E> {

/**
* 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
*/
Position<E> left(Position<E> p) throws IllegalArgumentException;

/**
* 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
*/
Position<E> right(Position<E> p) throws IllegalArgumentException;

AbstractTree.java

import java.util.Iterator;
import java.util.List; // for use as snapshot iterator
import java.util.ArrayList; // for use as snapshot iterator

/**
* An abstract base class providing some functionality of the Tree interface.
*
* The following three methods remain abstract, and must be
* implemented by a concrete subclass: root, parent, children. Other
* methods implemented in this class may be overridden to provide a
* more direct and efficient implementation.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
public abstract class AbstractTree<E> implements Tree<E> {

/**
* Returns true if Position p has one or more children.
*
* @param p A valid Position within the tree
* @return true if p has at least one child, false otherwise
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
@Override
public boolean isInternal(Position<E> p) { return numChildren(p) > 0; }

/**
* Returns true if Position p does not have any children.
*
* @param p A valid Position within the tree
* @return true if p has zero children, false otherwise
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
@Override
public boolean isExternal(Position<E> p) { return numChildren(p) == 0; }

/**
* Returns true if Position p represents the root of the tree.
*
* @param p A valid Position within the tree
* @return true if p is the root of the tree, false otherwise
*/
@Override
public boolean isRoot(Position<E> p) { return p == root(); }

/**
* Returns the number of children of Position p.
*
* @param p A valid Position within the tree
* @return number of children of Position p
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
@Override
public int numChildren(Position<E> p) {
int count=0;
for (Position child : children(p)) count++;
return count;
}

/**
* Returns the number of nodes in the tree.
* @return number of nodes in the tree
*/
@Override
public int size() {
int count=0;
for (Position p : positions()) count++;
return count;
}

/**
* Tests whether the tree is empty.
* @return true if the tree is empty, false otherwise
*/
@Override
public boolean isEmpty() { return size() == 0; }

//---------- support for computing depth of nodes and height of (sub)trees ----------

/** Returns the number of levels separating Position p from the root.
*
* @param p A valid Position within the tree
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
public int depth(Position<E> p) throws IllegalArgumentException {
if (isRoot(p))
return 0;
else
return 1 + depth(parent(p));
}

/** Returns the height of the tree.
*
* Note: This implementation works, but runs in O(n^2) worst-case time.
*/
private int heightBad() { // works, but quadratic worst-case time
int h = 0;
for (Position<E> p : positions())
if (isExternal(p)) // only consider leaf positions
h = Math.max(h, depth(p));
return h;
}

/**
* Returns the height of the subtree rooted at Position p.
*
* @param p A valid Position within the tree
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
public int height(Position<E> p) throws IllegalArgumentException {
int h = 0; // base case if p is external
for (Position<E> c : children(p))
h = Math.max(h, 1 + height(c));
return h;
}

//---------- support for various iterations of a tree ----------

//---------------- nested ElementIterator class ----------------
/* This class adapts the iteration produced by positions() to return elements. */
private class ElementIterator implements Iterator<E> {
Iterator<Position<E>> posIterator = positions().iterator();
public boolean hasNext() { return posIterator.hasNext(); }
public E next() { return posIterator.next().getElement(); } // return element!
public void remove() { posIterator.remove(); }
}

/**
* Returns an iterator of the elements stored in the tree.
* @return iterator of the tree's elements
*/
@Override
public Iterator<E> iterator() { return new ElementIterator(); }

/**
* Returns an iterable collection of the positions of the tree.
* @return iterable collection of the tree's positions
*/
@Override
public Iterable<Position<E>> positions() { return preorder(); }

/**
* Adds positions of the subtree rooted at Position p to the given
* snapshot using a preorder traversal
* @param p Position serving as the root of a subtree
* @param snapshot a list to which results are appended
*/
private void preorderSubtree(Position<E> p, List<Position<E>> snapshot) {
snapshot.add(p); // for preorder, we add position p before exploring subtrees
for (Position<E> c : children(p))
preorderSubtree(c, snapshot);
}

/**
* Returns an iterable collection of positions of the tree, reported in preorder.
* @return iterable collection of the tree's positions in preorder
*/
public Iterable<Position<E>> preorder() {
List<Position<E>> snapshot = new ArrayList<>();
if (!isEmpty())
preorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}

/**
* Adds positions of the subtree rooted at Position p to the given
* snapshot using a postorder traversal
* @param p Position serving as the root of a subtree
* @param snapshot a list to which results are appended
*/
private void postorderSubtree(Position<E> p, List<Position<E>> snapshot) {
for (Position<E> c : children(p))
postorderSubtree(c, snapshot);
snapshot.add(p); // for postorder, we add position p after exploring subtrees
}

/**
* Returns an iterable collection of positions of the tree, reported in postorder.
* @return iterable collection of the tree's positions in postorder
*/
public Iterable<Position<E>> postorder() {
List<Position<E>> snapshot = new ArrayList<>();
if (!isEmpty())
postorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}

/**
* Returns an iterable collection of positions of the tree in breadth-first order.
* @return iterable collection of the tree's positions in breadth-first order
*/
public Iterable<Position<E>> breadthfirst() {
List<Position<E>> snapshot = new ArrayList<>();
if (!isEmpty()) {
Queue<Position<E>> fringe = new LinkedQueue<>();
fringe.enqueue(root()); // start with the root
while (!fringe.isEmpty()) {
Position<E> p = fringe.dequeue(); // remove from front of the queue
snapshot.add(p); // report this position
for (Position<E> c : children(p))
fringe.enqueue(c); // add children to back of queue
}
}
return snapshot;
}
}

AbstractBinaryTree.java

import java.util.List;
import java.util.ArrayList;

/**
* An abstract base class providing some functionality of the BinaryTree interface.
*
* The following five methods remain abstract, and must be implemented
* by a concrete subclass: size, root, parent, left, right.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
public abstract class AbstractBinaryTree<E> extends AbstractTree<E>
implements BinaryTree<E> {

/**
* Returns the Position of p's sibling (or null if no sibling exists).
*
* @param p A valid Position within the tree
* @return the Position of the sibling (or null if no sibling exists)
* @throws IllegalArgumentException if p is not a valid Position for this tree
*/
@Override
public Position<E> sibling(Position<E> p) {
Position<E> parent = parent(p);
if (parent == null) return null; // p must be the root
if (p == left(parent)) // p is a left child
return right(parent); // (right child might be null)
else // p is a right child
return left(parent); // (left child might be null)
}

/**
* Returns the number of children of Position p.
*
* @param p A valid Position within the tree
* @return number of children of Position p
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
@Override
public int numChildren(Position<E> p) {
int count=0;
if (left(p) != null)
count++;
if (right(p) != null)
count++;
return count;
}

/**
* Returns an iterable collection of the Positions representing p's children.
*
* @param p A valid Position within the tree
* @return iterable collection of the Positions of p's children
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
@Override
public Iterable<Position<E>> children(Position<E> p) {
List<Position<E>> snapshot = new ArrayList<>(2); // max capacity of 2
if (left(p) != null)
snapshot.add(left(p));
if (right(p) != null)
snapshot.add(right(p));
return snapshot;
}

/**
* Adds positions of the subtree rooted at Position p to the given
* snapshot using an inorder traversal
* @param p Position serving as the root of a subtree
* @param snapshot a list to which results are appended
*/
private void inorderSubtree(Position<E> p, List<Position<E>> snapshot) {
if (left(p) != null)
inorderSubtree(left(p), snapshot);
snapshot.add(p);
if (right(p) != null)
inorderSubtree(right(p), snapshot);
}

/**
* Returns an iterable collection of positions of the tree, reported in inorder.
* @return iterable collection of the tree's positions reported in inorder
*/
public Iterable<Position<E>> inorder() {
List<Position<E>> snapshot = new ArrayList<>();
if (!isEmpty())
inorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}

/**
* Returns an iterable collection of the positions of the tree using inorder traversal
* @return iterable collection of the tree's positions using inorder traversal
*/
@Override
public Iterable<Position<E>> positions() {
return inorder();
}
}

Explanation / Answer

code for :

• preorderNext(p): Return the position visited after p in a preorder traversal

of T (or null if p is the last node visited).

Linked binary tree :

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 IllegalArgumentException("p already has a left child");

Node<E> child = createNode(e, parent, null, null);

parent.setLeft(child);

size++;

return child;

}

/**

* Creates a new right child of Position p storing element e and returns its Position.

* @param p the Position to the right 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 right child

public Position<E> addRight(Position<E> p, E e)

throws IllegalArgumentException {

Node<E> parent = validate(p);

if (parent.getRight() != null)

throw new IllegalArgumentException("p already has a right child");

Node<E> child = createNode(e, parent, null, null);

parent.setRight(child);

size++;

return child;

}

/**

* Replaces the element at Position p with element e and returns the replaced element.

* @param p the relevant Position

* @param e the new element

* @return the replaced element

* @throws IllegalArgumentException if p is not a valid Position for this tree.

public E set(Position<E> p, E e) throws IllegalArgumentException {

Node<E> node = validate(p);

E temp = node.getElement();

node.setElement(e);

return temp;

}

/**

* Attaches trees t1 and t2, respectively, as the left and right subtree of the

* leaf Position p. As a side effect, t1 and t2 are set to empty trees.

* @param p a leaf of the tree

* @param t1 an independent tree whose structure becomes the left child of p

* @param t2 an independent tree whose structure becomes the right child of p

* @throws IllegalArgumentException if p is not a valid Position for this tree

* @throws IllegalArgumentException if p is not a leaf

public void attach(Position<E> p, LinkedBinaryTree<E> t1,

LinkedBinaryTree<E> t2) throws IllegalArgumentException {

Node<E> node = validate(p);

if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf");

size += t1.size() + t2.size();

if (!t1.isEmpty()) { // attach t1 as left subtree of node

t1.root.setParent(node);

node.setLeft(t1.root);

t1.root = null;

t1.size = 0;

}

if (!t2.isEmpty()) { // attach t2 as right subtree of node

t2.root.setParent(node);

node.setRight(t2.root);

t2.root = null;

t2.size = 0;

}

/**

* Removes the node at Position p and replaces it with its child, if any.

* @param p the relevant Position

* @return element that was removed

* @throws IllegalArgumentException if p is not a valid Position for this tree.

* @throws IllegalArgumentException if p has two children.

public E remove(Position<E> p) throws IllegalArgumentException {

Node<E> node = validate(p);

if (numChildren(p) == 2)

throw new IllegalArgumentException("p has two children");

Node<E> child = (node.getLeft() != null ? node.getLeft() : node.getRight() );

if (child != null)

child.setParent(node.getParent()); // child's grandparent becomes its parent

if (node == root)

root = child; // child becomes root

else {

Node<E> parent = node.getParent();

if (node == parent.getLeft())

parent.setLeft(child);

else

parent.setRight(child);

}

size--;

E temp = node.getElement();

node.setElement(null); // help garbage collection

node.setLeft(null);

node.setRight(null);

node.setParent(node); // our convention for defunct node

return temp;

}

public Position<E> PreorderNext(Position<E> v)

{

if(isInternal(v))

{

return left(v);

}

else

{

Position<E> p = parent(v);

if( v.equals(left(p)))

{

return right(p);

}

else

{

while(!v.equals(left(p)))

{

v = p;

p = parent(p);

}

return right(p);

}

Navigate

C-8.33 Two ordered trees T and T are said to be isomorphic if one of the followi

C-Cell Wireless needed additional capital to expand, so the business incorporate

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

C-8.45 page 353 (each algorithm is 30 points and running time is 10 points) Add

Question

Explanation / Answer

Related Questions

Navigate