ap
Class TreeNode

java.lang.Object
  ap.TreeNode

public class TreeNode

extends java.lang.Object

The class for nodes in a binary tree that will be used and tested on the Advanced Placement Computer Science exam. For example, the question below, similar to Question 14 on the 1992 released AB exam, shows many of the TreeNode methods in use.

Consider methods m and f below. If the precondition for f is satisfied, which of the following is the best postcondition?

1. Returns the greatest value stored in the tree
2. Returns the least value stored in the tree
3. Returns the value at the root of the tree
4. Returns the last value visited during execution of f
5. Returns the first duplicated value encountered during execution of f.

 public class T
 {
     public static Object m(Object a, Object b)
     {
        if ( ( (Comparable) a).compareTo(b) >= 0) {
            return a;
        }
        else {
            return b;
        }
      }

 
  // precondition: t != null, that is t is not an empty tree
  // postcondition:

    public static Object f(TreeNode t)
    {
       if (t.getLeft() == null && t.getRight() == null) {
           return t.getValue();
       }
       else if (t.getLeft() == null) {
           return m(t.getValue(), f(t.getRight()));
       }
       else if (t.getRight() == null) {
           return m(t.getValue(), f(t.getLeft()));
       }
       else {
           return m(m(t.getValue(), f(t.getLeft())), f(t.getRight()));
       }
    }
 }
 

Note: this class has nothing to do with the standard Java interface javax.swing.tree.TreeNode.

This implementation is provided at apcentral.

Constructor Summary

TreeNode(java.lang.Object initValue)
Construct a tree node with specified value, with null left and right subtrees.

TreeNode(java.lang.Object initValue, TreeNode initLeft, TreeNode initRight)
Construct a tree node with specified value, left, and right subtrees.

Method Summary

TreeNode	getLeft() Returns the left subtree of this node.
TreeNode	getRight() Returns the right subtree of this node.
java.lang.Object	getValue() Returns the value stored in this tree node.
void	setLeft(TreeNode theNewLeft) Sets the value of the left subtree of this node.
void	setRight(TreeNode theNewRight) Sets the value of the right subtree of this node.
void	setValue(java.lang.Object theNewValue) Sets the value of this tree node.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TreeNode

public TreeNode(java.lang.Object initValue)

Construct a tree node with specified value, with null left and right subtrees.

Parameters:

initValue - is the value stored in the node

TreeNode

public TreeNode(java.lang.Object initValue,
                TreeNode initLeft,
                TreeNode initRight)

Construct a tree node with specified value, left, and right subtrees.

Parameters:

initValue - is the value stored in the node

initLeft - is the left subtree of the node

initRight - is the right subtree of the node

Method Detail

getValue

public java.lang.Object getValue()

Returns the value stored in this tree node.

Returns:

this tree node's value

getLeft

public TreeNode getLeft()

Returns the left subtree of this node.

Returns:

a reference to the left subtree of this node

getRight

public TreeNode getRight()

Returns the right subtree of this node.

Returns:

a reference to the right subtree of this node

setValue

public void setValue(java.lang.Object theNewValue)

Sets the value of this tree node.

Parameters:

theNewValue - is the (new) value stored in this node

setLeft

public void setLeft(TreeNode theNewLeft)

Sets the value of the left subtree of this node.

Parameters:

theNewLeft - is the (new) left subtree of this node

setRight

public void setRight(TreeNode theNewRight)

Sets the value of the right subtree of this node.

Parameters:

theNewRight - is the (new) right subtree of this node