Transcript An Example

Programming and Problem Solving
With Java
Chapter 14: Trees
Binary Trees
Binary Search Trees
Threaded Binary Trees
General Trees
Copyright 1999, James M. Slack
Tree Terms
Tree
Set of nodes
One root node
Root may have child nodes
Each child node is
root of its own
B
subtree
Root node
A
C
D
Leaf node
E
H
Programming and Problem Solving With Java
I
F
G
J
2
Tree Terms
More terminology
Parent
Sibling
Descendent
Ancestor
Edge
Level
Root node
A
B
C
D
Leaf node
E
H
Programming and Problem Solving With Java
I
F
G
J
3
Tree Applications
Can represent an outline as a tree
Features of Object-orientation
I. Introduction
A. Vocabulary
B. Topics
II. Encapsulation
A. Abstraction
B. Example
III. Polymorphism
A. Benefits
B. Example
IV. Inheritance
A. Single inheritance
1. Example
B. Multiple inheritance
1. Advantages
2. Disadvantages
3. Example
IV. Conclusion
Vocabulary
Introduction
Topics
Abstraction
Encapsulation
Example
Benefits
Polymorphism
Features of
Object-orientation
Example
Single
inheritance
Inheritance
Example
Advantages
Multiple
inheritance
Disadvantages
Example
Programming and Problem Solving With Java
Conclusion
4
Tree Applications
An organizational chart is a tree
XYZ Corporation
President
Assistant to the
Presi dent
Vi ce President
Fi nance
M anager
Accounting
M anager
Audi ti ng
Programming and Problem Solving With Java
Vi ce President
M anufacturi ng
Vi ce President
M arketi ng
M anager
Engi neeri ng
M anager
Sal es
Vi ce President
Information
M anager
Operati ons
M anager
Software
Devel opment
5
Tree Applications
Can represent an arithmetic expression as a tree
+
*
-
((12 / 3) * 2) + (5 - 1)
/
12
Programming and Problem Solving With Java
2
5
1
3
6
Tree Applications
Many compilers represent programs as trees
statement
selection-statement
if (x == y)
{
return;
}
if
(
)
condition
statement
expression
identifier
==
compound-statement
identifier
{
x
}
statement-list
y
jump-statement
return
Programming and Problem Solving With Java
;
7
Binary Trees
Binary tree
Tree
Each node has
0, 1, or 2 children
+
Example
Expression tree
(binary operators
only)
*
/
12
Programming and Problem Solving With Java
2
5
1
3
8
Binary Trees
Binary trees have distinguished children
Each child distinguished
as “left” or “right”
(Other trees don’t
distinguish children)
A
A
Not equal
B
Programming and Problem Solving With Java
B
9
Binary Tree Traversals
Traversing a structure: visit each element once
List traversals are natural
Forward (singly-linked list)
Forward or backward
(doubly-linked list)
+
Apparently, no “natural”
tree traversals
*
Level by level?
Up and down?
Start in the middle?
/
12
Programming and Problem Solving With Java
2
3
5
1
??
10
Binary Tree Traversals
Three common traversals: inorder, preorder,
postorder
All start at root
All are recursive
Inorder traversal
Process each node after all nodes in node’s left subtree,
and before any node in node’s right subtree
Pseudocode
// inOrderTraverse: Process each node in the subtree rooted
//
at node with an inorder traversal
void inOrderTraverse(node)
{
if (node exists)
{
inOrderTraverse(node's left child);
process(node);
inOrderTraverse(node's right child);
}
}
Programming and Problem Solving With Java
11
Binary Tree Traversals
Inorder traversal example
4+
2*
1
A
Programming and Problem Solving With Java
5C
3
B
Output: A * B + C
12
Binary Tree Traversals
Easy way to remember inorder traversal
Imagine balloon around tree, then let air out
Follow path
When under node,
+
process it
*
A
C
B
Notice that inorder traversal
visits each node three times
Programming and Problem Solving With Java
13
Binary Tree Traversals
Inorder traversal visits each node three times
Before processing the left subtree
After processing left subtree, before processing right
After processing right subtree
Usually, we only process a node between subtrees
Sometimes, we want to do something at each visit
Example: display a fully parenthesized expression
// displayExpression: Displays a fully parenthesized expression
//
in inorder fashion
+
void displayExpression(node)
{
if (node exists)
{
*
System.out.println('(');
displayExpression(node's left child);
System.out.println(node's value;
displayExpression(node's right child);
/
2
5
System.out.println(')');
}
}
Programming and Problem Solving With Java
Output: ((A * B) + C)
12
3
1
14
Binary Tree Traversals
Preorder traversal
Do all processing for a node before processing left or
right subtree
Uses
Compare two trees for equality
Copy a tree
Pseudocode
// preOrderTraverse: Process each node in the subtree rooted
//
at node with a preorder traversal
void preOrderTraverse(node)
{
if (node exists)
{
process(node);
preOrderTraverse(node's left child);
preOrderTraverse(node's right child);
}
}
Programming and Problem Solving With Java
15
Binary Tree Traversals
Preorder traversal example
1+
2*
3
A
Programming and Problem Solving With Java
5C
4
B
Output: + * A B C
16
Binary Tree Traversals
Postorder traversal
Do all processing for a node after processing left and
right subtree
Uses
Generate postfix version of expression
Delete a tree
Pseudocode
// postOrderTraverse: Process each node in the subtree rooted
//
at node with a postorder traversal
void postOrderTraverse(node)
{
if (node exists)
{
postOrderTraverse(node's left child);
postOrderTraverse(node's right child);
process(node);
}
}
Programming and Problem Solving With Java
17
Binary Tree Traversals
Postorder traversal example
5+
3*
1
A
Programming and Problem Solving With Java
4C
2
B
Output: A B * C +
18
Binary Tree Traversals
Can use balloon analogy for pre- and postorder
For preorder: when left of node, process it
For postorder, when
right of node,
+
process it
*
A
Programming and Problem Solving With Java
C
B
19
BinaryTree Class: Design
Will have two binary tree classes
Unordered
Ordered (binary search tree)
These will share many of the same methods
So -- make an abstract parent class: BinaryTree
BinaryTre e
BinaryUnorde re dTre e
Programming and Problem Solving With Java
BinarySe archTre e
20
BinaryTree Class: Methods
Method for inserting new values?
No, depends on whether the tree is ordered or not
Leave node insertion method to subclasses
Method to change values
put(): Change value in current node
Method to delete nodes?
Can safely delete leaf node, but not others
Before
deletion
After
deletion
+
*
A
+
C
B
?
A
?
C
B
removeSubtree(): delete node and its descendents
Programming and Problem Solving With Java
21
BinaryTree Class: Methods
Method to search for values
find(): Search for node containing a value
Set current node and return true if value found
Search technique depends on whether tree is ordered
Therefore, find() is abstract
Methods to move current node around the tree
goRoot(), goLeft(), goRight(), goParent()
Methods to traverse the tree
goFirstInOrder(), goNextInOrder()
Method to retrieve value of current node
get()
Methods to save and restore the current node
savePosition(), restorePosition()
Programming and Problem Solving With Java
22
BinaryTree Class: Methods
Utility methods
empty(), count()
Methods for information about the current node
isDefined(), isRoot(), hasLeftChild(), hasRightChild()
Debugging
display(): Show textual representation of the tree
Programming and Problem Solving With Java
23
BinaryUnorderedTree Class: Design
BinaryUnorderedTree is subclass of BinaryTree
Inherits all methods of BinaryTree (get, put, goRight,
display, ...)
Only need to add
Methods for inserting new values
find()
BinaryTre e
BinaryUnorde re dTre e
Programming and Problem Solving With Java
BinarySe archTre e
24
BinaryTree: Guess the Animal
Example how to use a binary tree: Guess the
Animal game
You think of an animal
Program tries to guess it by asking yes/no questions
If program is wrong, asks you to enter a new yes/no
question that will help it next time
Programming and Problem Solving With Java
25
BinaryTree: Guess the Animal
Example run of Guess the Animal
--- Guess the Animal Game---
Think of an animal and the computer will try
to guess the animal you are thinking of.
Does it fly?: y
Does it eat meat?: y
Is it hawk?: n
What animal were you thinking of?
falcon
Give a question that, when answered Yes,
will mean to select falcon, and when answered No,
will mean to select hawk
Does it have a notched beak?
Play again?: y
Think of an animal and the computer will try
to guess the animal you are thinking of.
Does it fly?: y
Does it eat meat?: y
Does it have a notched beak?: y
Is it falcon?: y
Guessed it!
Play again?: n
Programming and Problem Solving With Java
26
BinaryTree: Guess the Animal
How Guess
the Animal
Works
Original Tree
Does fly?
No
Yes
Does it walk on four legs?
No
Does it eat meat?
Yes
human
No
horse
Extended with
New Question
sparrow
New
question
Yes
Does it walk on four legs?
human
hawk
Does fly?
No
No
Yes
Does it eat meat?
Yes
No
horse
sparrow
Yes
Does it have a notched beak?
No
Programming and Problem Solving With Java
hawk
Yes
falcon
27
BinaryTree: Guess the Animal
GuessAnimalGame class
Instance variables
// Instance variables
BinaryUnorderedTree question = new BinaryUnorderedTree();
Constructor: loads game
// Constructor: Initializes a new game
public GuessAnimalGame()
{
question.insertRoot("Does it fly?");
question.goRoot();
question.insertLeftChild("Does it walk on four legs?");
question.goLeft();
question.insertLeftChild("human");
question.insertRightChild("horse");
question.goParent();
question.insertRightChild("Does it eat meat?");
question.goRight();
question.insertLeftChild("sparrow");
question.insertRightChild("hawk");
}
Programming and Problem Solving With Java
28
BinaryTree: Guess the Animal
play(): high-level control of game
// play: Asks discriminating questions to try to guess the
//
animal. If the program doesn't guess the correct
//
answer, it asks the user to enter a question that
//
will identify the animal.
public void play()
throws java.io.IOException
{
askQuestions();
}
System.out.println();
if (Keyboard.readChar("Is it " + question.get() + "? ",
"yn") == 'y')
{
System.out.println("Guessed it!");
}
else
{
addNewAnimal();
}
Programming and Problem Solving With Java
29
BinaryTree: Guess the Animal
askQuestions(): tries to guess
// askQuestions: Asks questions from the root to a leaf node
// Note: Each node of the tree must have either zero or two
//
children, and the tree cannot be empty.
void askQuestions()
throws java.io.IOException
{
System.out.println("Think of an animal and the computer will try");
System.out.println("to guess the animal you are thinking of.");
}
question.goRoot();
while (question.hasLeftChild() && question.hasRightChild())
{
if (Keyboard.readChar((String) question.get() + " ", "yn") == 'n')
{
question.goLeft();
}
else
{
question.goRight();
}
}
Programming and Problem Solving With Java
30
BinaryTree: Guess the Animal
How new question
and new animal
added to tree
Adding a new
question
Old question
No
New question
Yes
Yes
Guess
New animal
After
Old question
No
Yes
New question
No
Programming and Problem Solving With Java
Guess
Yes
New animal
31
BinaryTree: Guess the Animal
addNewAnimal(): adds new animal to tree
// addNewAnimal: Prompts the user for the correct answer and a yes/no
//
question. The question replaces the guess in the tree,
//
the guess becomes the left child of the new question,
//
and the correct answer becomes the right child of the
//
new question.
// Note: The current node of the binary tree must be a leaf node
void addNewAnimal()
throws java.io.IOException
{
String oldAnimal, animal;
animal = Keyboard.readString("What animal were you thinking of? ");
System.out.println("Give a question that, when " + "answered Yes,");
System.out.println("will mean to select " + animal + ", and ”
+ "when answered No,");
System.out.println("will mean to select " + question.get());
oldAnimal = (String) question.get();
question.put(Keyboard.readString());
}
question.insertLeftChild(oldAnimal);
question.insertRightChild(animal);
Programming and Problem Solving With Java
32
BinaryTree: Guess the Animal
Starting the game
public static void main(String[] args)
throws java.io.IOException
{
GuessAnimalGame game = new GuessAnimalGame();
System.out.println("--- Guess the Animal Game---");
}
do
{
System.out.println();
game.play();
} while (Keyboard.readChar("Play again? ", "yn") == 'y');
Programming and Problem Solving With Java
33
BinaryTree Implementation
Several possible implementations of binary tree
classes
Array approaches
Linked approaches
Programming and Problem Solving With Java
34
BinaryTree Linear Implementation
Array of objects approach
Array of
Objects
Representation
Tree
+
0
1
*
C
2
3
A
B
4
Data
Left
child
Right
child
+
*
C
A
B
1
3
-1
-1
-1
2
4
-1
-1
-1
Running times
O(1): inserting new node, put(), get(), moving current
node (except goParent())
O(n): find(), removeSubTree(), goParent()
Programming and Problem Solving With Java
35
BinaryTree Linear Implementation
Array of objects approach
Array of
Objects
Representation
Tree
+
0
1
*
C
2
3
A
B
4
Data
Left
child
Right
child
+
*
C
A
B
1
3
-1
-1
-1
2
4
-1
-1
-1
Advantage: simple
Disadvantages:
Array size fixed (wasted space, node number limit)
Can use Vector to remove some of these problems
Programming and Problem Solving With Java
36
BinaryTree Linear Implementation
Another approach works well for complete trees
Tree is complete if all leaves are at the bottom two levels,
and the leaves at the bottom level are as far left as
possible (heap-structuring property)
Noncomplete
Tree
Complete Tree
+
*
A
+
C
B
Programming and Problem Solving With Java
C
*
A
B
37
BinaryTree Linear Implementation
Complete tree approach for arrays
Put elements from tree level-by-level in array
Array
Representation
Tree
Data
+
*
A
C
B
Node i’s left child:
Node i’s right child:
Node i’s parent:
Programming and Problem Solving With Java
0
+
1
*
2
3
C
A
4
B
(i * 2) + 1
(i * 2) + 2
(i - 1) / 2
38
BinaryTree Linear Implementation
Complete tree approach also works for “almost
complete” trees
Must remember to leave empty space
Array
Representation
Tree
Data
+
C
*
0
+
1
C
*
2
3
A
B
4
5
Programming and Problem Solving With Java
6
A
B
39
BinaryTree Linked Implementation
Another approach uses dynamic memory allocation
Allocate nodes as needed
Link nodes together with references
Will write separate classes for nodes and tree
BinaryTreeNode
BinaryTree (abstract superclass)
BinaryUnorderedTree (subclass of BinaryTree)
Programming and Problem Solving With Java
40
BinaryTree Linked Implementation
BinaryTreeNode implementation
Data
References to parent, left child, right child
(parent reference not really necessary; makes some
methods simpler and faster)
To parent
Data
Programming and Problem Solving With Java
To left child
To right child
41
BinaryTree Linked Implementation
public class BinaryTreeNode
Instance variables
// Instance variables
private Object item;
private BinaryTreeNode leftChild, rightChild, parent;
Constructor
// Constructor
public BinaryTreeNode(Object item,
BinaryTreeNode leftChild,
BinaryTreeNode rightChild,
BinaryTreeNode parent)
{
this.item = item;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.parent = parent;
}
To parent
Data
Programming and Problem Solving With Java
To left child
To right child
42
BinaryTree Linked Implementation
setLeftChild(), setRightChild(), setParent()
// setLeftChild: Sets the left child of this node to the given node
public void setLeftChild(BinaryTreeNode leftChild)
{
this.leftChild = leftChild;
}
// Set the left child's parent to this one
if (leftChild != null)
{
leftChild.setParent(this);
}
// setRightChild: Sets the right child of this node to the given node
public void setRightChild(BinaryTreeNode rightChild)
{
To parent
this.rightChild = rightChild;
}
// Set the right child's parent to this one
if (rightChild != null)
{
rightChild.setParent(this);
}
Data
// setParent: Sets the parent of this node to the given node
public void setParent(BinaryTreeNode parent)
{
this.parent = parent;
}
Programming and Problem Solving With Java
To left child
To right child
43
BinaryTree Linked Implementation
makeLeftChildOf()
Makes this node the left child of some other node
// makeLeftChildOf: Sets the parent of this node to the
//
given node, and makes this node the
//
left child of the given node. (If the
//
given node is null, then this method
//
makes the parent of this node null.)
public void makeLeftChildOf(BinaryTreeNode parent)
{
if (parent == null)
{
this.parent = null;
}
To parent
else
{
parent.setLeftChild(this);
}
}
Data
Programming and Problem Solving With Java
To left child
To right child
44
BinaryTree Linked Implementation
makeRightChildOf()
Makes this node the right child of some other node
// makeRightChildOf: Sets the parent of this node to the
//
given node, and makes this node the
//
right child of the given node. (If the
//
given node is null, then this method
//
makes the parent of this node null.)
public void makeRightChildOf(BinaryTreeNode parent)
{
if (parent == null)
{
this.parent = null;
}
To parent
else
{
parent.setRightChild(this);
}
}
Data
Programming and Problem Solving With Java
To left child
To right child
45
BinaryTree Linked Implementation
 setItem(), getLeftChild, getRightChild(), getParent(), getItem()
// setItem: Sets the item of this node to the value
public void setItem(Object item)
{
this.item = item;
}
// getLeftChild: returns the left child of this node
public BinaryTreeNode getLeftChild()
{
return leftChild;
}
// getRightChild: returns the right child of this node
public BinaryTreeNode getRightChild()
{
To parent
return rightChild;
}
// getParent: returns the parent of this node
public BinaryTreeNode getParent()
{
return parent;
}
// getItem: returns the value of this node
public Object getItem()
{
return item;
}
Programming and Problem Solving With Java
To left child
Data
To right child
46
BinaryTree Linked Implementation
BinaryTree class
Instance variables
// Instance variables
protected BinaryTreeNode root, currentNode, savedCurrentNode;
protected int numNodes;
Protected variables
Subclasses can access protected variables and methods
Easier to write BinaryUnorderedTree and
BinarySearchTree if they can get to these variables
Other classes can’t access (like private)
Alternative
Write public get() and set() methods for each variable
BUT then ALL other classes can access variables
through these methods
Programming and Problem Solving With Java
47
BinaryTree Linked Implementation
displaySubtree() method
Uses a recursive traversal to display tree in outline form
Tree
Text Display
+
*
A
C
*: +
L: *
L: A
R: B
R: C
B
Preorder traversal pseudocode
// preOrderTraverse: Process each node in the subtree rooted
//
at node with a preorder traversal
void preOrderTraverse(node)
{
if (node exists)
{
process(node);
preOrderTraverse(node's left child);
preOrderTraverse(node's right child);
}
Programming}and Problem Solving With Java
48
BinaryTree Linked Implementation
displaySubtree() method
// displaySubtree: Displays the subtree rooted at node in an
//
outline format. (This is useful for
//
debugging.)
private void displaySubtree(BinaryTreeNode node,
char childLabel,
int level)
{
if (node != null)
{
// Indent
for (int i = 0; i < level; i++)
{
System.out.print(" ");
}
System.out.println(childLabel + ": " + node.getItem());
}
}
// Recursively display children
this.displaySubtree(node.getLeftChild(), 'L', level + 1);
this.displaySubtree(node.getRightChild(), 'R', level + 1);
(This is a private method, called by public method
display())
Programming and Problem Solving With Java
49
BinaryTree Linked Implementation
Constructor for BinaryTree
// Default constructor
public BinaryTree()
{
this.root = null;
this.currentNode = null;
this.savedCurrentNode = null;
this.numNodes = 0;
}
put() method: change current node
// put: Changes the value of the currentNode node to item
// Note: currentNode must be defined
public void put(Object newItem)
{
Debug.assert(isDefined(),
"BinaryTree.put: currentNode not defined");
currentNode.setItem(newItem);
}
Programming and Problem Solving With Java
50
BinaryTree Linked Implementation
removeSubtree() method
// removeSubtree: Removes the subtree with currentNode as the root. Sets
//
currentNode to parent node of the root of the subtree,
//
unless deleting the root node. In that case, currentNode
//
is undefined.
// Note: currentNode must be defined
public void removeSubtree()
{
BinaryTreeNode parentNode;
Debug.assert(isDefined(),
"BinaryTree.removeSubtree: currentNode not defined");
if (isRoot())
{
root = null;
currentNode = null;
}
else
{
parentNode = currentNode.getParent();
if (parentNode.getLeftChild() == currentNode)
{
parentNode.setLeftChild(null);
}
else
{
parentNode.setRightChild(null);
}
currentNode = parentNode;
}
} and Problem Solving With Java
Programming
51
BinaryTree Linked Implementation
find() method: find an element in the tree
Abstract method -- subclass must implement
// find: If a particular value is in the tree, sets
//
currentNode to that node and returns true.
//
Otherwise, leaves currentNode as it was and
//
returns false.
public abstract boolean find(Object item);
Programming and Problem Solving With Java
52
BinaryTree Linked Implementation
goRoot(), goLeft() methods
// goRoot: Sets currentNode to the root of the tree
// Node: The tree must not be empty
public void goRoot()
{
Debug.assert(!empty(),
"BinaryTree.goRoot(): tree is empty");
currentNode = root;
}
// goLeft: Sets currentNode to its left child
// Note: currentNode must be defined and have
//
a left child
public void goLeft()
{
Debug.assert(isDefined() && hasLeftChild(),
"BinaryTree.goLeft(): currentNode undefined"
+ " or no left child");
currentNode = currentNode.getLeftChild();
}
Programming and Problem Solving With Java
53
BinaryTree Linked Implementation
goRight(), goParent() methods
// goRight: Sets currentNode to its right child
// Note: currentNode must be defined and have
//
a right child
public void goRight()
{
Debug.assert(isDefined() && hasRightChild(),
"BinaryTree.goRight(): currentNode undefined"
+ " or no right child");
currentNode = currentNode.getRightChild();
}
// goParent: Sets currentNode to its parent
// Note: currentNode must be defined and cannot
//
be the root
public void goParent()
{
Debug.assert(isDefined() && !isRoot(),
"BinaryTree.goParent(): currentNode undefined"
+ " or is root");
currentNode = currentNode.getParent();
}
Programming and Problem Solving With Java
54
BinaryTree Linked Implementation
goFirstInorder(), goNextInorder()
One approach: use recursion
Pseudocode for recursive inorder traversal
// inOrderTraverse: Process each node in the subtree rooted
//
at node with an inorder traversal
void inOrderTraverse(node)
{
if (node exists)
{
inOrderTraverse(node's left child);
process(node);
inOrderTraverse(node's right child);
}
}
Can’t use recursion
goFirstInorder(), goNextInorder() each return to caller
after one move
So no run-time stack
Programming and Problem Solving With Java
55
BinaryTree Linked Implementation
goFirstInorder() method
First node in inorder traversal:
go left as far as possible
Code
// goFirstInOrder: Sets currentNode to first
//
node in an inorder
A
//
traversal
public void goFirstInOrder()
{
currentNode = root;
if (!empty())
{
while (hasLeftChild())
{
currentNode = currentNode.getLeftChild();
}
}
}
Programming and Problem Solving With Java
+
*
F
/
%
B
C
D
E
56
BinaryTree Linked Implementation
goNextInorder() method: first case
Current node has a right child
Next node is leftmost node in right subtree
+
*
F
A
/
%
B
Programming and Problem Solving With Java
C
D
E
57
BinaryTree Linked Implementation
goNextInorder() method: second case
Current node has no right child, and is a left child
Next node is parent
+
*
F
A
/
%
B
Programming and Problem Solving With Java
C
D
E
58
BinaryTree Linked Implementation
goNextInorder() method: third case
Current node has no child, is a right child
To get to next node, follow parent references until we
arrive at a node from its left child
+
*
F
A
/
%
Programming and Problem Solving With Java
B
C
D
E
59
BinaryTree Linked Implementation
Pseudocode for getNextInorder()
if (currentNode has a right child)
{
move to currentNode's right child
keep moving to the left child until there are no more
}
else if (currentNode is the left child of its parent)
{
move to currentNode's parent
}
else
{
keep moving to the parent until we arrive at a node from its left child
(stop if we reach the root)
}
Programming and Problem Solving With Java
60
BinaryTree Linked Implementation
goNextInorder(): first case
// goNextInOrder: Sets currentNode to the node following the
//
previous value of currentNode in an inorder
//
traversal
// Note: currentNode must be defined
public void goNextInOrder()
{
// if (currentNode has a right child)
// {
//
move to currentNode's right child
//
keep moving to the left child until there are no more
// }
+
if (hasRightChild())
{
currentNode = currentNode.getRightChild();
while (hasLeftChild())
*
{
currentNode = currentNode.getLeftChild();
}
A
/
}
F
%
B
Programming and Problem Solving With Java
C
D
E
61
BinaryTree Linked Implementation
getNextInOrder(): second case
// else if (currentNode is the left child of its parent)
// {
//
move to currentNode's parent
// }
else if (currentNode != root
&& currentNode.getParent().getLeftChild()
== currentNode)
{
currentNode = currentNode.getParent();
}
+
*
F
A
/
%
B
Programming and Problem Solving With Java
C
D
E
62
BinaryTree Linked Implementation
goFirstInorder(): third case
}
// else
// {
//
keep moving to the parent until we arrive at a node
//
from its left child
//
(stop if we reach the root)
// }
else
{
while (currentNode != root
&& currentNode.getParent().getRightChild()
== currentNode)
{
currentNode = currentNode.getParent();
}
*
if (currentNode == root)
{
currentNode = null;
}
A
else
{
currentNode = currentNode.getParent();
%
}
}
B
Programming and Problem Solving With Java
C
+
F
/
D
E
63
BinaryTree Linked Implementation
savePosition(), restorePosition(), empty(), count()
// savePosition: Saves currentNode
public void savePosition()
{
savedCurrentNode = currentNode;
}
// restorePosition: Restores currentNode
public void restorePosition()
{
currentNode = savedCurrentNode;
}
// empty: Returns true if the tree is empty
public boolean empty()
{
return root == null;
}
// count: Returns the number of elements in the tree
public int count()
{
return numNodes;
}
Programming and Problem Solving With Java
64
BinaryTree Linked Implementation
get(), isDefined(), isRoot()
// get: Gets the value at the currentNode location
// Note: currentNode must be defined
public Object get()
{
Debug.assert(isDefined(),
"BinaryTree.get(): currentNode not defined");
return currentNode.getItem();
}
// isDefined: Returns true if current node points to a valid
//
node in the tree.
public boolean isDefined()
{
return currentNode != null;
}
// isRoot: Returns true if currentNode points to root of the
//
tree
// Note: currentNode must be defined
public boolean isRoot()
{
Debug.assert(isDefined(),
"BinaryTree.isRoot(): currentNode not defined");
return currentNode == root;
}
Programming and Problem Solving With Java
65
BinaryTree Linked Implementation
hasLeftChild(), hasRightChild(), display()
// hasLeftChild: Returns true if currentNode has a left child
// Note: currentNode must be defined
public boolean hasLeftChild()
{
Debug.assert(isDefined(),
"BinaryTree.hasLeftChild(): currentNode not defined");
return currentNode.getLeftChild() != null;
}
// hasRightChild: Returns true if currentNode has a right child
// Note: currentNode must be defined
public boolean hasRightChild()
{
Debug.assert(isDefined(),
"BinaryTree.hasRightChild(): currentNode not defined");
return currentNode.getRightChild() != null;
}
// display: Displays a tree on the screen (for debugging)
public void display()
{
System.out.println("--- Tree ---");
displaySubtree(root, '*', 0);
}
Programming and Problem Solving With Java
66
BinaryTree Linked Implementation
copyParent()
replaces fromNode with toNode in the tree
// copyParent: Copies fromNode's parent to toNode, and
//
makes the parent reference toNode instead of
//
fromNode
protected static void copyParent(BinaryTreeNode toNode,
BinaryTreeNode fromNode)
{
BinaryTreeNode fromNodeParent = fromNode.getParent();
}
if (fromNodeParent == null)
{
toNode.setParent(null);
}
else if (fromNodeParent.getLeftChild() == fromNode)
{
toNode.makeLeftChildOf(fromNodeParent);
}
else
{
toNode.makeRightChildOf(fromNodeParent);
}
Programming and Problem Solving With Java
67
BinaryUnorderedTree Implementation
BinaryUnorderedTree is subclass of BinaryTree
Inherits all the methods of BinaryTree (removeSubtree(),
get(), put(), goFirstInorder(), ...)
class BinaryUnorderedTree extends BinaryTree
{
// Methods go here
}
Only need to add insertion methods and implement find()
insertRoot() method
// insertRoot: Inserts a new root in an empty tree
// Note: The tree must be empty
public void insertRoot(Object item)
{
Debug.assert(empty(),
"BinaryUnorderedTree.insertRoot(): Tree is not empty");
root = new BinaryTreeNode(item, null, null, null);
numNodes++;
}
Programming and Problem Solving With Java
68
BinaryUnorderedTree Implementation
insertLeftChild(), insertRightChild()
// insertLeftChild: Inserts a new item as the left child
//
of the current node.
// Note: Current node must be defined, and there cannot
//
be a left child of the current node
public void insertLeftChild(Object item)
{
Debug.assert(isDefined() && !hasLeftChild(),
"BinaryUnorderedTree.insertLeftChild(): "
+ "currentNode undefined or has left child");
currentNode.setLeftChild(
new BinaryTreeNode(item, null, null, currentNode));
numNodes++;
}
// insertRightChild: Inserts a new item as the right child
//
of the current node.
// Note: Current node must be defined, and there cannot
//
be a right child of the current node
public void insertRightChild(Object item)
{
Debug.assert(isDefined() && !hasRightChild(),
"BinaryUnorderedTree.insertRightChild(): "
+ "currentNode undefined or has right child");
currentNode.setRightChild(
new BinaryTreeNode(item, null, null, currentNode));
numNodes++;
}
Programming and Problem Solving With Java
69
BinaryUnorderedTree Implementation
find() method: finds a value in the tree
Uses findNode(), a private recursive method
// find: If a particular value is in the tree, sets
//
currentNode to that node and returns true.
//
Otherwise, leaves currentNode
//
as it was and returns false.
public boolean find(Object data)
{
BinaryTreeNode node = findNode(data, root);
}
if (node == null)
{
return false;
}
currentNode = node;
return true;
Programming and Problem Solving With Java
70
BinaryUnorderedTree Implementation
findNode(): Uses preorder traversal to find value
Preorder is most efficient: compares node at first visit to
the node
Need to stop the recursion when
We find the node
The recursive call to the left subtree finds the node
The recursive call to the right subtree finds the node
If none of these happen, return null
Programming and Problem Solving With Java
71
BinaryUnorderedTree Implementation
// findNode: Returns a pointer to the parent of a node
//
containing a particular value, or null if
//
not in the tree. Uses preorder traversal.
private BinaryTreeNode findNode(Object data, BinaryTreeNode node)
{
BinaryTreeNode temp;
// Make sure we didn't go off the tree
if (node == null)
{
return null;
}
// See if this node is the one we want
if (node.getItem().equals(data))
{
return node;
}
// See if node is in left subtree
temp = findNode(data, node.getLeftChild());
if (temp != null)
{
return temp;
}
// See if node is in right subtree
temp = findNode(data, node.getRightChild());
if (temp != null)
{
return temp;
}
// Didn't find it
return null;
}
Programming and Problem Solving With Java
72
Binary Search Trees
Binary search tree
Binary tree, and
Satisfies the ordering property
The Ordering Property
For each node in the tree,
all values in the node's left subtree
are less than the node's value,
and all values in the right subtree
are greater than or equal to the node's value
Programming and Problem Solving With Java
73
Binary Search Trees
Binary search tree example
50
32
18
Programming and Problem Solving With Java
61
44
61
74
Binary Search Trees
Can have more than one binary search tree with the
same values
44
50
32
18
18
61
44
61
50
32
61
61
Programming and Problem Solving With Java
75
Binary Search Trees
To find a value in a binary search tree
Start at root -- does it have the value?
If so, stop
If value is less than root’s, look in left subtree
If value is greater than or equal to root’s, look in right
subtree
Continue until we find value or reach empty subtree
50
32
Programming and Problem Solving With Java
18
61
44
61
76
Binary Search Trees
Finding a value in a binary search tree similar to
binary search of array
In array, start in middle
In binary search tree, start at root -- approximate “middle”
value if tree is balanced
At each comparison, eliminate about 1/2 of remaining
values
Running time
Binary search of array: O(log n)
Binary search tree search of balanced tree: O(log n)
Binary search tree search of unbalanced tree: ???
Programming and Problem Solving With Java
77
Binary Search Trees
Inserting new nodes: value determines position
Insert 18
Insert 50
18
Insert 61
18
18
50
50
61
Insert 61
again
Insert 32
18
18
50
32
Insert 44
18
50
61
Programming and Problem Solving With Java
32
50
61
32
61
61
44
61
78
Binary Search Trees
Inserting new nodes: order determines tree shape
Insert 18
Insert 32
18
Insert 44
18
18
32
32
44
Insert 50
Insert 61
again
Insert 61
18
18
32
18
32
44
32
44
50
44
50
50
61
Programming and Problem Solving With Java
61
61
79
Binary Search Trees
Binary search tree ordering property allows
Efficient searching (assuming balanced tree)
Easy way to traverse values in ascending order
Inorder traversal processes nodes in ascending order
Programming and Problem Solving With Java
80
Binary Search Trees: Deletion
Deleting values from a binary search tree
In BinaryTree class, couldn’t delete a non-leaf node
without deleting the whole subtree
With binary search tree, can delete any node -- just need
to restore the ordering property
Four cases
Node to delete has no children
Node to delete has a left child, but no right child
Node to delete has a right child, but no left child
Node to delete has two children
Each has three subcases
Node to delete is a left child
Node to delete is a right child
Node to delete is the root
Programming and Problem Solving With Java
81
Binary Search Trees: Deletion
First case: Node has no children
Just take the node out of the tree
Delete root
node
Delete
other nodes
25
25
10
5
0
40
15
30
20
50
35
45
(Note the three subcases)
Programming and Problem Solving With Java
82
Binary Search Trees: Deletion
Second case: node has a left child, but no right
Link around the node to delete
Delete root
node
Delete
other nodes
25
25
10
10
5
0
40
15
30
20
50
35
45
(Note the three subcases)
Programming and Problem Solving With Java
83
Binary Search Trees: Deletion
Third case: node has a right child, but no left
Just link around the node
Delete root
node
Delete
other nodes
25
25
40
10
5
0
40
15
30
20
50
35
45
(Note the three subcases)
Programming and Problem Solving With Java
84
Binary Search Trees: Deletion
25
10
25
40
10
5
15
0
30
20
40
25
10
0
50
35
10
5
Programming and Problem Solving With Java
40
Result
Find replacement
value (smallest
value in right
subtree)
Copy replacement
value to node
Delete replacement
node
Delete
other nodes
Result
Fourth case: node
has two children
Delete root
node
45
45
15
30
20
50
35
85
Binary Search Trees: Tree Sort
Example: use a binary search tree to sort data
Insert values into binary search tree
Inorder traversal processes values in ascending order
// treeSort: Arranges the elements in array into ascending order
static void treeSort(String[] array)
{
BinarySearchTree tree
= new BinarySearchTree(new StringComparator());
// Copy elements from array into binary search tree
for (int i = 0; i < array.length; i++)
{
tree.insert(array[i]);
}
}
Note use of
comparator
// Copy elements from tree back to array using inorder traversal
int i = 0;
for (tree.goFirstInOrder(); tree.isDefined(); tree.goNextInOrder())
{
array[i] = (String) tree.get();
i++;
}
Programming and Problem Solving With Java
86
Binary Search Trees: Tree Sort
Worst-case running time behavior for treeSort()
Inorder traversal: O(n) for n nodes
Insertion: depends on shape of tree
If tree is balanced (best case): O(log n)
If tree is degenerate (worst case)
n(n  1)
1  2  3 n  2  n  1 
2
2
 O( n )
Average-case running time? (hard to analyze
mathematically, easier empirically)
Programming and Problem Solving With Java
87
Binary Search Tree Implementation
BinarySearchTree is a subclass of BinaryTree
Only need to add methods to insert values and search
public class BinarySearchTree extends BinaryTree
{
// Methods go here
}
Instance variables
Need a comparator to tell us when one value is less than,
greater than, or equal to another
// Instance variables
Comparator comparator;
Constructor
Initializes comparator
// Constructor
public BinarySearchTree(Comparator comparator)
{
this.comparator = comparator;
}
Programming and Problem Solving With Java
88
Binary Search Tree Implementation
insert() method: inserts a new value
First search for the parent, starting at root until we find
null
Using trailing reference to keep track of parent
Cases when we find insertion location
Tree is empty: insert new root
Inserting new left child of parent
Inserting new right child of parent
Programming and Problem Solving With Java
89
Binary Search Tree Implementation
insert() method (part 1)
// insert: Inserts a new value as a new leaf so the resulting
//
tree obeys the ordering property.
// Note: The tree must satisfy the ordering property
public void insert(Object item)
{
BinaryTreeNode node = root, parentNode = null, newNode;
// Find parent of new node
while (node != null)
{
parentNode = node;
if (comparator.compareTo(item, node.getItem()) < 0)
{
node = node.getLeftChild();
}
else
{
node = node.getRightChild();
}
}
Programming and Problem Solving With Java
90
Binary Search Tree Implementation
insert() method (part 2)
// Set new node's parent
newNode = new BinaryTreeNode(item, null, null, parentNode);
numNodes++;
// Make parent refer to the new node (determine which child it
// should be)
if (parentNode == null)
{
root = newNode;
}
else if (comparator.compareTo(item, parentNode.getItem()) < 0)
{
parentNode.setLeftChild(newNode);
}
else
{
parentNode.setRightChild(newNode);
}
}
// Make the new node the current one
currentNode = newNode;
Programming and Problem Solving With Java
91
Binary Search Tree Implementation
remove() method: delete current node
Four cases
node has no children
node has a left child, but no right child
node has a right child, but no left child
node has two children
Each has three subcases
node is root
node is left child
node is right child
Can combine last two cases
In both cases, node has a right child
(only works if replacement node from right subtree)
Programming and Problem Solving With Java
92
Binary Search Tree Implementation
remove(): startup
// remove: Removes currentNode, leaving the tree so it
//
satisfies the ordering property. Sets currentNode
//
to its parent, unless deleting the root, in which
//
case currentNode becomes undefined.
// Note: The tree must satisfy the ordering property, and
//
currentNode must be defined
public void remove()
{
BinaryTreeNode parentNode, replacementNode;
Debug.assert(isDefined(),
"BinarySearchTree.remove(): currentNode not defined");
// Get the parent of currentNode
if (currentNode == root)
{
parentNode = null;
}
else
{
parentNode = currentNode.getParent();
}
Programming and Problem Solving With Java
93
Binary Search Tree Implementation
remove() case 1: Node has no children
Just take the node out of the tree
Delete root
node
Delete
other nodes
25
25
10
5
0
Programming and Problem Solving With Java
40
15
30
20
50
35
45
94
Binary Search Tree Implementation
remove() case 1: Node has no children
// Case 1: Node has no children - just delete the node
if (!hasLeftChild() && !hasRightChild())
{
if (currentNode == root)
{
root = null;
}
else
{
if (parentNode.getRightChild() == currentNode)
{
parentNode.setRightChild(null);
}
else
{
parentNode.setLeftChild(null);
}
}
}
Programming and Problem Solving With Java
95
Binary Search Tree Implementation
remove() case 2: Node has left child but no right
Link around the node to delete
Delete root
node
Delete
other nodes
25
25
10
10
5
0
Programming and Problem Solving With Java
40
15
30
20
50
35
45
96
Binary Search Tree Implementation
remove() case 2: Node has left child but no right
// Case 2: Node has a left child and no right child //
link around the node
// (This is as before)
else if (!hasRightChild())
{
if (currentNode == root)
{
root = currentNode.getLeftChild();
}
else
{
if (parentNode.getRightChild() == currentNode)
{
parentNode.setRightChild(currentNode.getLeftChild());
}
else
{
parentNode.setLeftChild(currentNode.getLeftChild());
}
currentNode.getLeftChild().setParent(parentNode);
}
}
Programming and Problem Solving With Java
97
Binary Search Tree Implementation
25
10
25
40
10
5
15
0
30
20
40
25
10
0
50
35
10
5
Programming and Problem Solving With Java
40
Result
Find replacement
value (smallest
value in right
subtree)
Copy replacement
value to node
Delete replacement
node
Delete
other nodes
Result
remove() cases 3&4:
Node has right child
Delete root
node
45
45
15
30
20
50
35
98
Binary Search Tree Implementation
remove() cases 3&4: Node has right child
// Case 3: Node has a right child and no left child, or
// Case 4: Node has both left and right children
// In either case, get a replacement node from the right
// subtree and delete the replacement instead
else
{
// Find the smallest value in currentNode's right subtree
replacementNode = currentNode.getRightChild();
while (replacementNode.getLeftChild() != null)
{
replacementNode = replacementNode.getLeftChild();
}
// Copy the value of the replacement node to currentNode
currentNode.setItem(replacementNode.getItem());
}
}
// Remove the replacement node recursively
currentNode = replacementNode;
remove();
// Set currentNode to its parent
currentNode = parentNode;
numNodes--;
Programming and Problem Solving With Java
99
Binary Search Tree Implementation
find() method: find a value in the tree
// find: If a particular value is in the tree, sets currentNode to
//
the node and returns true. Otherwise, leaves currentNode
//
as it was and returns false. Note: if there are duplicates
//
of the value, this function finds the one closest to the
//
root.
// Note: The tree must satisfy the ordering property
public boolean find(Object item)
{
BinaryTreeNode node = root;
while (node != null
&& (comparator.compareTo(item, node.getItem()) != 0))
{
if (comparator.compareTo(item, node.getItem()) < 0)
{
node = node.getLeftChild();
}
else
{
node = node.getRightChild();
}
}
}
if (node == null)
{
return false;
}
currentNode = node;
return true;
Programming and Problem Solving With Java
100
Binary Search Tree Dictionary
Example of how to use BinarySearchTree class:
BSTdictionary
Dictionary: container class that stores values and
their associated keys
Java has an abstract java.util.Dictionary class that works
this way (java.util.Hashtable is concrete implementation)
Implement dictionary as binary search tree
Each node in dictionary is a binary search tree node
Example: can use dictionary to store abbreviations
and meanings
Programming and Problem Solving With Java
101
Binary Search Tree Dictionary
Dictionary operations
Insert new key-value pair into dictionary
Determine if dictionary is empty
Tell number of entries in dictionary
Return reference to data value for given key
Display all dictionary entries
Delete dictionary entry
Programming and Problem Solving With Java
102
Binary Search Tree Dictionary
Each entry in dictionary is key,value pair
Will use class DictionaryValue to store key,value pairs
class DictionaryValue
{
// Constructor
public DictionaryValue(Object key, Object data)
{
this.key = key;
this.data = data;
}
// Constructor: no data value
public DictionaryValue(Object key)
{
this(key, null);
}
Programming and Problem Solving With Java
103
Binary Search Tree Dictionary
DictionaryValue class (continued)
// getData: Returns the data portion of the dictionary value
public Object getData()
{
return data;
}
// getKey: Returns the key portion of the dictionary value
public Object getKey()
{
return key;
}
// toString: Returns a string representation of the dictionary
//
entry
public String toString()
{
return "(" + key + ": " + data + ")";
}
}
// Instance Variables
Object key, data;
Programming and Problem Solving With Java
104
Binary Search Tree Dictionary
DictionaryValueComparator class
Needs to compare DictionaryValue objects, which are
stored in a binary search tree
Compares key values
To be general, it must also use a comparator
class DictionaryValueComparator extends Comparator
{
// Constructor: Requires a comparator for the key
//
value of the dictionary value
DictionaryValueComparator(Comparator comparator)
{
this.comparator = comparator;
}
// compareTo: Returns the result of comparing the keys
//
of the two values
public int compareTo(Object a, Object b)
{
return (comparator.compareTo(((DictionaryValue) a).getKey(),
((DictionaryValue) b).getKey()));
}
}
private Comparator comparator;
Programming and Problem Solving With Java
105
Binary Search Tree Dictionary
BSTdictionary class
Implement with binary search tree
Each node of binary search tree stores DictionaryValue
object
Each DictionaryValue object stores a key and its
associated value
Instance variables
// Instance variables
BinarySearchTree tree;
Constructor
// Constructor
BSTdictionary(Comparator keyComparator)
{
tree = new BinarySearchTree(
new DictionaryValueComparator(keyComparator));
}
Programming and Problem Solving With Java
106
Binary Search Tree Dictionary
BSTdictionary.insert() method
If key isn’t already in dictionary, puts key, value in
If key is there already, replaces value
// insert: Inserts a new item into the dictionary. If key is
//
already in the dictionary, changes the data value
//
associated with that key. Returns true if the value
//
was already in the tree, false otherwise.
public boolean insert(Object key, Object data)
{
if (tree.find(new DictionaryValue(key)))
{
// Change existing node
tree.put(new DictionaryValue(key, data));
return true;
}
else
{
// Insert new node
tree.insert(new DictionaryValue(key, data));
return false;
}
}
Programming and Problem Solving With Java
107
Binary Search Tree Dictionary
BSTdictionary.find() method
Use find() method from tree (object of BinarySearchTree
class)
// find: Returns true if a dictionary entry exists with the given
//
key. If so, also sets the current dictionary entry to that
//
entry.
public boolean find(Object key)
{
return tree.find(new DictionaryValue(key));
}
Programming and Problem Solving With Java
108
Binary Search Tree Dictionary
BSTDictionary.remove(), get(), empty(), count()
// remove: Removes the current dictionary entry
// Note: There must be a current dictionary entry
public void remove()
{
tree.remove();
}
// get: Returns the value of the current dictionary entry
// Note: There must be a current dictionary entry
public DictionaryValue get()
{
return (DictionaryValue) tree.get();
}
// empty: Returns true if the dictionary is empty
public boolean empty()
{
return tree.empty();
}
// count: Returns the number of entries in the dictionary
public int count()
{
return tree.count();
}
Programming and Problem Solving With Java
109
Binary Search Tree Dictionary
BSTdictionary.toString()
Uses goFirstInorder(), goNextInorder() from BinaryTree
// toString: Returns a string representation of the
//
dictionary
public String toString()
{
String result = "[";
}
tree.savePosition();
tree.goFirstInOrder();
while (tree.isDefined())
{
result = result + tree.get();
tree.goNextInOrder();
if (tree.isDefined())
{
result = result + ", ";
}
}
tree.restorePosition();
return result + "]";
Programming and Problem Solving With Java
110
Binary Search Tree Dictionary
Simple example of BSTdictionary
import BSTdictionary;
import IntegerComparator;
class PartsDatabase
{
public static void main(String[] args)
{
BSTdictionary parts = new BSTdictionary(new
IntegerComparator());
// Put in a few part#, description pairs
parts.insert(new Integer(456), "Screwdriver");
parts.insert(new Integer(123), "Hammer");
parts.insert(new Integer(789), "Saw");
// Display the dictionary
System.out.println("Initial dictionary is " + parts);
// Look up parts by part#
if (parts.find(new Integer(456)))
{
System.out.println("Part 456 is " + parts.get());
}
Programming and Problem Solving With Java
111
Binary Search Tree Dictionary
Simple example of BSTdictionary
// Replace a part description
parts.insert(new Integer(789), "Crosscut saw");
// Display the dictionary
System.out.println("Dictionary after replacement " + parts);
// Remove a part
if (parts.find(new Integer(123)))
{
parts.remove();
}
}
}
// Display the dictionary
System.out.println("Dictionary after removal " + parts);
Programming and Problem Solving With Java
112
Binary Search Tree Dictionary
Example: abbreviation program
+--- Abbreviation Menu --| I) Insert new abbrev
R) Remove abbrev
| L) Look up meaning
S) Show all entries
| Enter selection: i
Enter new abbreviation: CPU
Enter meaning for CPU: Central Processing Unit
+--- Abbreviation Menu --| I) Insert new abbrev
R) Remove abbrev
| L) Look up meaning
S) Show all entries
| Enter selection: i
Enter new abbreviation: RAM
Enter meaning for RAM: Random Access Mem.
+--- Abbreviation Menu --| I) Insert new abbrev
R) Remove abbrev
| L) Look up meaning
S) Show all entries
| Enter selection: l
Enter new abbreviation: CPU
Meaning of CPU is: Central Processing Unit
Programming and Problem Solving With Java
C) Change meaning
Q) Quit
C) Change meaning
Q) Quit
C) Change meaning
Q) Quit
113
Binary Search Tree Dictionary
Example: abbreviation program
+--- Abbreviation Menu --| I) Insert new abbrev
R) Remove abbrev
C) Change meaning
| L) Look up meaning
S) Show all entries
Q) Quit
| Enter selection: c
Enter abbreviation to change: RAM
Existing meaning is: Random Access Mem.
Enter new meaning for RAM: Random Access Memory
+--- Abbreviation Menu --| I) Insert new abbrev
R) Remove abbrev
C) Change meaning
| L) Look up meaning
S) Show all entries
Q) Quit
| Enter selection: s
Entries: [(CPU: Central Processing Unit), (RAM: Random Access
Memory)]
Number of entries: 2
...
Programming and Problem Solving With Java
114
Binary Search Tree Dictionary
Example: abbreviation program
//
//
//
//
//
This program implements an abbreviation dictionary.
The user can enter abbreviations with their meanings, then
look up abbreviations. The user can also change the
meaning of an existing abbreviation to something else.
This program demonstrates use of the Dictionary class.
import
import
import
import
BSTdictionary;
Comparator;
TextMenu;
Keyboard;
public class AbbrevApp extends TextMenu
{
final static int INSERT_ABBREV = 1;
final static int REMOVE_ABBREV = 2;
final static int CHANGE_ABBREV = 3;
final static int LOOK_UP_MEANING = 4;
final static int SHOW_ENTRIES = 5;
// Constructor
public AbbrevApp()
{
super("Abbreviation Menu");
addSelection("Insert new abbrev", 'I', INSERT_ABBREV);
addSelection("Remove abbrev", 'R', REMOVE_ABBREV);
addSelection("Change meaning", 'C', CHANGE_ABBREV);
addSelection("Look up meaning", 'L', LOOK_UP_MEANING);
addSelection("Show all entries", 'S', SHOW_ENTRIES);
addSelection("Quit", 'Q', TextMenu.QUIT);
}
Programming and Problem Solving With Java
115
Binary Search Tree Dictionary
Example: abbreviation program (continued)
// Event dispatcher
public int handleEvent(int event)
throws java.io.IOException
{
switch (event)
{
case INSERT_ABBREV:
insert();
break;
case REMOVE_ABBREV:
remove();
break;
case CHANGE_ABBREV:
change();
break;
case LOOK_UP_MEANING:
lookUp();
break;
case SHOW_ENTRIES:
System.out.println("Entries: " + abbrevDictionary);
System.out.println("Number of entries: "
+ abbrevDictionary.count());
break;
}
return event;
}
Programming and Problem Solving With Java
116
Binary Search Tree Dictionary
Example: abbreviation program (continued)
// insert: Inserts a new abbreviation and meaning, and
//
inserts it, if abbreviation not already in use
//
and there's room in the abbreviation dictionary.
private void insert()
throws java.io.IOException
{
String abbrev, meaning;
abbrev = Keyboard.readString("Enter new abbreviation: ");
if (abbrevDictionary.find(abbrev))
{
System.out.println(abbrev + " is already in use");
return;
}
}
meaning = Keyboard.readString("Enter meaning for "
+ abbrev + ": ");
abbrevDictionary.insert(abbrev, meaning);
Programming and Problem Solving With Java
117
Binary Search Tree Dictionary
Example: abbreviation program (continued)
// remove: Asks the user for an abbreviation to remove,
//
then removes the abbreviation if it exists.
//
If it doesn't exist, then displays an error
//
message.
private void remove()
throws java.io.IOException
{
String abbrev;
abbrev
= Keyboard.readString("Enter abbreviation to remove: ");
}
if (!abbrevDictionary.find(abbrev))
{
System.out.println(abbrev + " not found");
return;
}
abbrevDictionary.remove();
Programming and Problem Solving With Java
118
Binary Search Tree Dictionary
Example: abbreviation program (continued)
// change: Change the meaning of an existing abbreviation
//
to new meaning supplied by the user. Displays
//
message if abbreviation not defined
private void change()
throws java.io.IOException
{
String abbrev, meaning;
abbrev
= Keyboard.readString("Enter abbreviation to change: ");
}
if (abbrevDictionary.find(abbrev))
{
System.out.println("Existing meaning is: "
+ abbrevDictionary.get().getData());
meaning = Keyboard.readString("Enter new meaning for "
+ abbrev + ": ");
abbrevDictionary.remove();
abbrevDictionary.insert(abbrev, meaning);
}
else
{
System.out.println("No entry found for " + abbrev);
}
Programming and Problem Solving With Java
119
Binary Search Tree Dictionary
Example: abbreviation program (continued)
// lookUp: Displays the meaning of an existing
//
abbreviation, or message if not defined
private void lookUp()
throws java.io.IOException
{
String abbrev;
abbrev
= Keyboard.readString("Enter abbreviation to look up: ");
}
if (abbrevDictionary.find(abbrev))
{
System.out.println("Meaning of " + abbrev + " is: "
+ abbrevDictionary.get().getData());
}
else
{
System.out.println("No entry found for " + abbrev);
}
Programming and Problem Solving With Java
120
Binary Search Tree Dictionary
Example: abbreviation program (continued)
// Instance variables
BSTdictionary abbrevDictionary
= new BSTdictionary(new StringComparator());
public static void main(String[] args)
throws java.io.IOException
{
AbbrevApp abbrevApplication = new AbbrevApp();
}
}
abbrevApplication.run();
Programming and Problem Solving With Java
121
Threaded Binary Trees
BinaryTree class uses lots of space for references
Need some left and right child references
Parent reference? (goFirstInorder(), goNextInorder())
BinaryTree
5
Note all the
unused references
NULL
+
NULL
*
NULL
A
NULL
Programming and Problem Solving With Java
NULL
B
C
NULL
NULL
122
Threaded Binary Trees
Can use unused right references
Thread: reference to next node in inorder traversal
Need boolean in each node to tell if reference is thread
BinaryTree
5
+
*
NULL
A
T
Programming and Problem Solving With Java
NULL
F
NULL
F
B
C
NULL F
T
123
Threaded Binary Trees
Traversing a threaded tree
Use goFirstInorder() to get first node (go left as far as
possible)
To get next node
if (right reference of current node is null)
{
stop the traversal
}
else if (right reference of current node is a thread)
{
next node is target of the thread
}
else
{
next node is leftmost node in right subtree
}
Can also have left-pointing threads
Use to traverse nodes in descending order
Programming and Problem Solving With Java
124
General Trees
General tree
No restriction on number of children per node
Usually don’t have distinguished nodes
Many applications
Outlines
Organizational charts
Expression trees for programming languages
File system directories
a
Several ways to store
Simplest technique:
use binary tree
b
e
Programming and Problem Solving With Java
c
f
d
g
h
i
125
General Trees
How to store general tree in binary tree
Treat each left reference as “first child of”
Treat each right reference as “next sibling of”
a
b
a
a
e
b
c
d
b
c
c
d
f
e
f
g
h
i
Programming and Problem Solving With Java
f
g
Convert to
binary tree
h
d
i
STRETCH!
Original
general tree
e
g
h
i
126
General Trees
Can use binary tree traversals to traverse general
tree
a
b
a
e
b
c
c
d
f
e
f
g
h
d
i
g
h
i
General tree traversals
Preorder:
abefcdghi
Postorder: efbcghida
Inorder:
n/a
Programming and Problem Solving With Java
Binary tree traversals
Preorder:
abefcdghi
Postorder: feihgdcba
Inorder:
efbcghida
127