Pseudocode: Project 4
Function: Tree Application Class
Description: Creates a class, which will provide functions to access a doubly linked list.
Initialize number of nodes to zero
Function: Tree Constructer
Description: Provides a constructer to create an empty tree
Calls: N/A
Called by: Main
Input Parameters: N/A
Returns: N/A
Set root to null
Function: Insert
Description: Method to insert a node into the tree
Calls: get Abbr, Compare To
Called by: Main
Input Parameters: tree node
Returns: N/A
Get abbr of tree node
If root is null
Set root to tree node
Else
Create current node and set to root of tree
Create parent node
While true
Set parent node to current
If abbr is less than abbr of current node
Set current to current.leftChild
If current is null
Set left child of parent to tree node
Return
End If
Else
Set current to current.rightChild
If current is null
Set right child of parent to tree node
Return
EndIf
End Else
End While
End Else
Function: Traverse
Description: Traverses the tree based on type of scan required
Calls: LNR Recursive, NLR Recursive, NLR Iterative, RNL Iterative
Called by: Main
Input Parameters: type of traversal
Returns: N/A
Switch (Input traverse type)
Case 1: Print tree using LNR recursive scan
Print header consisting of node num, abbr, population and state
Call LNR Recursive method to traverse tree staring at the root
Break;
Case 2: Print tree using NRL recursive scan
Print header consisting of node num, abbr, population and state
Call NRL Recursive method to traverse tree staring at the root
Break;
Case 3: Print tree using NLR Iterative scan
Print header consisting of node num, abbr, population and state
Call NLR Iterative method to traverse tree staring at the root
Break;
Case 4: Print tree using RNL Iterative scan
Print header consisting of node num, abbr, population and state
Call RNL Iterative method to traverse tree staring at the root
Break;
End switch
Function: LNR Recursive
Description: Performs a In order traversal on the tree using recursion
Calls: LNR Recursive (itself), display Node
Called by: Traverse
Input Parameters: tree node
Returns: N/A
If the tree node is not null
Call itself to perform function on left child
Display the node
Call itself to perform function on right child
EndIf
Function: NLR Recursive
Description: Performs a In order traversal on the tree using recursion
Calls: NLR Recursive (itself), display Node
Called by: Traverse
Input Parameters: tree node
Returns: N/A
If the tree node is not null
Display the node
Call itself to perform function on left child
Call itself to perform function on right child
EndIf
Function: RNL Iterative
Description: Performs a RNL Iterative scan on the tree
Calls: is Empty, Stack constructor, push, pop, display Node
Called by: Traverse
Input Parameters: tree node
Returns: N/A
Create stack of type tree node
Set node to the root of tree
While true
While node isn’t null
Push node onto stack
Set node to right child of node
End while
If the stack is not empty
Pop last item on stack
Display the node
Set node to left child of node
End if
Else
Break;
End while
Function: NLR Iterative
Description: Performs a non recursive Pre Order traversal on the tree
Calls: is Empty, Stack constructor, push, pop, display Node
Called by: Traverse
Input Parameters: tree node
Returns: N/A
Create stack of type tree node
Set node to the root of tree
While true
While node isn’t null
Display the node
Push node onto stack
Set node to left child of node
End while
If the stack is not empty
Pop last item on stack
Set node to right child of node
End if
Else
Break;
End while
Function: Delete
Description: Deletes given node in the tree
Calls: Compare To, get Successor
Called by: Main
Input Parameters: abbreviation
Returns: true or false
Set current node to root
Set parent node to root
Set is left child to true
//find node in the tree
While there is no match
Set parent to current
If given abbreviation is less than current
Set is left child to true
Set current to current.leftChild
End if
Else
Set is left child to false
Set current to current.rightChild
End Else
If current is null
Returns false
Print that the state could not be found
End If
End While
//if the node has no children…
if current has no left child and no right child
if current is root
set root to null
else if it is left child (check Boolean variable)
set left child of parent to null
else
set right child of parent to null
end if
//if node only had one child..
Else if node does not have right child
If current is root
Set root to left child of current
Else if it is left child
Set parent.leftChild to current.leftChild
Else
Set parent.rightChild to current.leftChild
//if node has two children…
Else
Get the successor of current node (call get successor method)
If current is root
Set root to successor
Else if current is left child
Set parent.leftChild to successor
Else
Set parent.rightChild to successor
Set successor.leftChild to current.leftChild
End Else
Print that state has been deleted
Return true
Function: get successor
Description: gets the next in order successor of the node being deleted
Calls: N/A
Called by: Delete
Input Parameters: node
Returns: node
Set successor parent to node
Set successor to node
Set current to node.rightChild
While current is not null
Set successor parent to successor
Set successor to current
Set current to current.leftChild
End While
If successor isn’t right child of node
Set successor parent to successor.rightChild
Set successor.rightChild to node.rightChild
End if
Return successor
Function: Find
Description: finds a node in the tree using abbreviation
Calls: N/A
Called by: Main
Input Parameters: abbreviation
Returns: true or false
Set current node to root
Set searched nodes to zero
While there is no match
If given abbreviation is less than current
Set current to current.leftChild
Increment searched nodes
End if
Else
Set current to current.rightChild
Increment searched nodes
End Else
If current is null
Return false
Print node couldn’t be found
End if
End While
Return true
Print node was found