Class GenealogyTree

java.lang.Object

GenealogyTree

public class GenealogyTree
extends java.lang.Object

A general tree that is can be used to keep track of parent child relationships between data. Nodes in a general tree can have multiple children. This tree is built by reading lines from a file. To help with program 4, this class also has a method that returns a stack of String (names) that are the ancestors of the specified node. See getAncestorStack.

Field Summary

Fields

Modifier and Type	Field and Description
static java.lang.String	LOAD_GENEALOGY_ERROR_MESSAGE

Constructor Summary

Constructors

Constructor and Description
GenealogyTree()

Method Summary

Modifier and Type	Method and Description
void	buildFromFile(java.lang.String filename) Load a tree from file.
StackADT<java.lang.String>	getAncestorStack(java.lang.String target) return a Stack that contains the ancestors of the node with matching data The root is at the bottom of the stack and the matching node is at the top and the stack contains all ancestors of the matching data node.
TreeNode<java.lang.String>	getRoot()
void	printTree() Print a tree with indent.

Methods inherited from class java.lang.Object

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

Field Detail

LOAD_GENEALOGY_ERROR_MESSAGE

public static final java.lang.String LOAD_GENEALOGY_ERROR_MESSAGE

See Also:

Constant Field Values

Constructor Detail

GenealogyTree

public GenealogyTree()

Method Detail

getRoot

public TreeNode<java.lang.String> getRoot()

getAncestorStack

public StackADT<java.lang.String> getAncestorStack(java.lang.String target)

return a Stack that contains the ancestors of the node with matching data The root is at the bottom of the stack and the matching node is at the top and the stack contains all ancestors of the matching data node. THIS METHOD CALLS A COMPANION (HELPER) METHOD that is recursive If the top of the stack is not target, return an empty stack indicating that the target was not found.

Parameters:

target - the data you are trying to find

Returns:

a stack with the target data node at top and the root at the bottom, or return an empty stack if the target was not found.

buildFromFile

public void buildFromFile(java.lang.String filename)
                   throws java.io.IOException

Load a tree from file. If there are IOException when loading the tree from file, print LOAD_GENEALOGY_ERROR_MESSAGE and throw the IOException. All the lines in the file "parent -> children" relationships. The relationships are listed in a pre-order traversal order starting from root. For example, for the following tree: a / | \ b c d | | \ e f g The input file must follow this form:

  a -> b
  a -> c
  a -> d
  b -> e
  d -> f
  d -> g
 

Note: all lines of a file must contain a relationship to be a valid format. Blank lines will cause exceptions. Pseudocode for the work done by this method:

        // Create a queue, add each new node to the queue
        // create a Scanner connect to the file
  // for each line of the file
        // read the line
      // parse the line into parent and child

      // if root is null
        // create the root node
          // add the root's first child
          // add the root and child to the queue

      // else Construct other TreeNode
        // while queue is not empty
                // get next node from queue without removing it from queue
              // if "front" node matches the parent
                // create a TreeNode for the child
                  // add the child node to the current "front" node (its parent)
                  // add the child to the queue
                  // break out of the loop
                // else dequeue the front node 

  // catch IO exceptions, display error message and rethrow the exception
        // close the file scanner
  

Parameters:

filename - the name of the file with the (professor->student) data pairs

Throws:

java.io.IOException - if file not found

printTree

public void printTree()

Print a tree with indent. You should use pre-order to print a tree, which means: (1) Print the data at current node (2) For all children nodes of current node, recursively use pre-order to print children nodes. Each line of output represents a node, use indent (number of spaces before node data) to indicate which level the current node belongs to. For root node (at level 0), use 0 spaces. For nodes at other levels, add 2 spaces of indent each level. Like for the following tree: a / | \ b c d | | \ e f g The displayed output should be:

  a
  ..b
  ....e
  ..c
  ..d
  ....f
  ....g