Transcript Trees

Lecture Objectives
1




To learn how to use a tree to represent a
hierarchical organization of information
To learn how to use recursion to process trees
To understand the different ways of traversing a
tree
To understand the difference between binary trees,
binary search trees, and heaps
CS340
Trees - Introduction
2

Data organizations
 Linear:
one predecessor or successor
 Nonlinear: multiple predecessors, successors


Accessing all elements in a linear sequence is O(n)
Trees are nonlinear and hierarchical
 Tree
nodes can have multiple successors (but only one
predecessor)
CS340
Trees - Introduction (cont.)
3

Trees can represent :
 class
hierarchy
 disk directory and subdirectories
 family tree


Trees are recursive data structures
Many methods to process trees are written
recursively
CS340
Binary trees
4



Each element has two successors
Binary trees can be represented by arrays and
linked data structures
Searching in a binary search tree generally more
efficient than searching in an ordered list
CS340
Tree Terminology and Applications
CS340
Tree Terminology
6
A tree consists of a collection of elements or nodes,
with each node linked to its successors
wikipedia
science
mathematics
CS340
arts
Tree Terminology (cont.)
7
A tree consists of a collection of elements or nodes,
with each node linked to its successors
The node at the top of
a tree is called its root
wikipedia
science
mathematics
CS340
arts
Tree Terminology (cont.)
8
A tree consists of a collection of elements or nodes,
with each node linked to its successors
The links from a node
to its successors are
called branches
wikipedia
science
mathematics
CS340
arts
Tree Terminology (cont.)
9
A tree consists of a collection of elements or nodes,
with each node linked to its successors
The successors of a
node are called its
children
wikipedia
science
mathematics
CS340
arts
Tree Terminology (cont.)
10
A tree consists of a collection of elements or nodes,
with each node linked to its successors
Each node in a tree has
exactly one parent
except for the root node,
which has no parent
wikipedia
science
mathematics
CS340
arts
The predecessor of a
node is called its
parent
Tree Terminology (cont.)
11
A tree consists of a collection of elements or nodes,
with each node linked to its successors
Nodes that have the
same parent are
siblings
wikipedia
science
mathematics
CS340
arts
Tree Terminology (cont.)
12
A tree consists of a collection of elements or nodes,
with each node linked to its successors
A node that has no
children is called a
leaf node
wikipedia
science
mathematics
CS340
arts
Leaf nodes also are
known as
external nodes,
and nonleaf nodes
are known as
internal nodes
Tree Terminology (cont.)
13
A tree consists of a collection of elements or nodes,
with each node linked to its successors
wikipedia
science
mathematics
CS340
arts
A generalization of the parent-child
relationship is the
ancestor-descendant relationship
Tree Terminology (cont.)
14
A tree consists of a collection of elements or nodes,
with each node linked to its successors
wikipedia
science
mathematics
CS340
arts
A subtree of a node is
a tree whose root is a
child of that node
Tree Terminology (cont.)
15
A tree consists of a collection of elements or nodes,
with each node linked to its successors
Level 1
Level 2
Level 3
CS340
science
mathematics
wikipedia
arts
The level of a node is
a measure of its
distance from the root
plus 1
Tree Terminology (cont.)
16
A tree consists of a collection of elements or nodes,
with each node linked to its successors
Level 1
Level 2
Level 3
wikipedia
science
arts
The level of a node is
defined recursively
mathematics
• If node n is the root of tree T, its level is 1
• If node n is not the root of tree T, its level is
1 + the level of its parent
CS340
Tree Terminology (cont.)
17
A tree consists of a collection of elements or nodes,
with each node linked to its successors
The height of a tree
is the number of
nodes in the longest
path from the root
node to a leaf node
wikipedia
science
mathematics
CS340
arts
The height of this
tree is 3
Binary Trees
18


In a binary tree, each node has two subtrees
A set of nodes T is a binary tree if either of the
following is true
T
is empty
 Its root node has two subtrees, TL and TR, such that TL
and TR are binary trees
(TL = left subtree; TR = right subtree)
CS340
Expression Tree
19
Each node contains an
operator or an operand
 Operands are stored in
leaf nodes
 Tree structure dictates the
order of operand evaluation
 No parenthesis needed

CS340
(x + y) * ((a + b) / c)
Binary Search Tree
20

Binary search trees

All elements in the left subtree
precede those in the right subtree
encyclopedia
arts
science
mathematics
A formal definition:
A set of nodes T is a binary
search tree if either of the following is true:
 T is empty
 If T is not empty, its root node has two subtrees, TL and
TR, such that



TL and TR are binary search trees
the values in the root node of T is greater than all values in
TL and is less than all values in TR
Binary Search Tree (cont.)

Does not need to be sorted
 Why?


When new elements are inserted (or removed)
properly, the binary search tree maintains its order
Compare to an array
CS340
Binary Search Tree (cont.)


Searching a BST can be O(log n)
What is the worst case?
CS340
Recursive Algorithm for Searching a
Binary Tree
1.
if the tree is empty
return null (target is not found)
2.
else if the target matches the root node's data
return the data stored at the root node
3.
else if the target is less than the root node's data
return the result of searching the left subtree of the root
4.
else
return the result of searching the right subtree of the root
5.
CS340
Full, Perfect, and Complete Binary
Trees
24

Full binary tree: all
nodes have either 2
children or 0 children
(the leaf nodes)
7
1
0
1
0
3
2
CS340
1
1
5
4
1
2
9
6
1
3
Full, Perfect, and Complete Binary
Trees (cont.)
25


Perfect binary tree is a
full binary tree of height
n with exactly
2n – 1 nodes
Find n in this example
CS340
3
1
0
5
2
4
6
Full, Perfect, and Complete Binary
Trees (cont.)
26

Complete binary tree is a
perfect binary tree
through level n - 1 with
some extra leaf nodes at
level n (the tree height),
all toward the left
CS340
3
1
0
5
2
4
General Trees
27

Nodes of a general tree can have any number of
subtrees
CS340
General Trees (cont.)
28

A general tree can be
represented using a binary
tree
CS340
Tree Traversals
CS340
Tree Traversals
30


Walking through the tree in a prescribed order and
visiting the nodes as they are encountered
Three common kinds of tree traversal
 Inorder
 Preorder
 Postorder
CS340
Tree Traversals (cont.)
31



Preorder: visit root node, traverse TL, traverse TR
Inorder: traverse TL, visit root node, traverse TR
Postorder: traverse TL, traverse TR, visit root node
CS340
Visualizing Tree Traversals
32

If we keep following the
tree to the left, it will trace
a route known as the Euler
tour
CS340
Visualizing Tree Traversals (cont.)
33


A Euler tour (blue path) is a
preorder traversal
The sequence in this
example is
abdgehcfij
CS340
Visualizing Tree Traversals (cont.)
34
If we record a node as we
return from traversing its left
subtree we get an
inorder traversal
 The sequence is
dgbheaifjc

CS340
Visualizing Tree Traversals (cont.)
35


If we record each node as
we last encounter it, we get
a postorder traversal
The sequence is
gdhebijfca
CS340
Traversals of Binary Search Trees
and Expression Trees
36

With inorder traversal nodes
are visited in sequence
Peter
Helen
Bob
Bob, Helen, Peter, Stacy
CS340
Stacy
Traversals of Binary Search Trees and
Expression Trees (cont.)
37


An inorder traversal of an
expression tree results in the
sequence
x+y*a+b/c
Or with parentheses
(x + y) * ((a + b)) / c)
CS340
*
+
x
/
y
+
a
c
b
Traversals of Binary Search Trees and
Expression Trees (cont.)
38



A postorder traversal
xy+ab+c/*
Postfix form of the expression
Operators follow operands
*
+
x
/
y
+
a
CS340
c
b
Traversals of Binary Search Trees and
Expression Trees (cont.)
39
A preorder traversal
*+xy/+abc
 Prefix form of the expression
 Operators precede operands

*
+
x
/
y
+
a
CS340
c
b
Implementing a BinaryTree Class
CS340
Node<E> Class
41


The data part is a reference to
type E
A binary tree node must have
links to both its left and right
subtrees
CS340
Node<E> Class (cont.)
42
protected static class Node<E>
implements Serializable {
protected E data;
protected Node<E> left;
protected Node<E> right;
public Node(E data) {
this.data = data;
left = null;
right = null;
}
public String toString() {
return data.toString();
}
}
CS340
Node<E> is declared as an
inner class within
BinaryTree<E>
Node<E> Class (cont.)
43
protected static class Node<E>
implements Serializable {
protected E data;
protected Node<E> left;
protected Node<E> right;
public Node(E data) {
this.data = data;
left = null;
right = null;
}
public String toString() {
return data.toString();
}
}
CS340
Node<E> is declared
protected. This way we can
use it as a superclass.
BinaryTree<E> Class (cont.)
44
BinaryTree<E> Class (cont.)
45
Assuming the tree is
referenced by variable bT
(type BinaryTree) then . . .
CS340
BinaryTree<E> Class (cont.)
46
bT.root.data references
the Character object storing
' *'
CS340
BinaryTree<E> Class (cont.)
47
bT.root.left references
the left subtree of the root
CS340
BinaryTree<E> Class (cont.)
48
bT.root.right references
the right subtree of the root
CS340
BinaryTree<E> Class (cont.)
49
bT.root.right.data
references the Character
object storing '/'
CS340
BinaryTree<E> Class (cont.)
50
BinaryTree<E> Class (cont.)

Class heading and data field declarations:
import java.io.*;
public class BinaryTree<E> implements Serializable {
// Insert inner class Node<E> here
protected Node<E> root;
. . .
}
CS340
BinaryTree<E> Class (cont.)


The Serializable interface defines no methods
It provides a marker for
 ObjectOutputStream:
classes can be written to a
binary file
 ObjectInputStream: classes can be read from a
binary file
CS340
Constructors

The no-parameter constructor:
public BinaryTree() {
root = null;
}

The constructor that creates a tree with a given node at
the root:
protected BinaryTree(Node<E> root) {
this.root = root;
}
CS340
Constructors (cont.)

The constructor that builds a tree from a data value and two trees:
public BinaryTree(E data, BinaryTree<E> leftTree,
BinaryTree<E> rightTree) {
root = new Node<E>(data);
if (leftTree != null) {
root.left = leftTree.root;
} else {
root.left = null;
}
if (rightTree != null) {
root.right = rightTree.root;
} else {
root.right = null;
}
}
getLeftSubtree and
getRightSubtree Methods
public BinaryTree<E> getLeftSubtree() {
if (root != null && root.left != null) {
return new BinaryTree<E>(root.left);
}
else {
return null
}
}

getRightSubtree method is symmetric
CS340
isLeaf Method
public boolean isLeaf() {
return (root.left == null && root.right == null);
}
CS340
toString Method

Generates a string representing a preorder
traversal
public String toString() {
StringBuilder sb = new StringBuilder();
preOrderTraverse(root, 1, sb);
return sb.toString();
}
CS340
preOrderTraverse Method
private void preOrderTraverse(Node<E> node, int depth,
StringBuilder sb) {
for (int i = 1; i < depth; i++) {
sb.append(" ");
}
if (node == null) {
sb.append("null\n");
} else {
sb.append(node.toString());
sb.append("\n");
preOrderTraverse(node.left, depth + 1, sb);
preOrderTraverse(node.right, depth + 1, sb);
}
}
preOrderTraverse Method (cont.)
*
+
x
*
null
null
+
y
null
null
x
/
y
a
/
(x + y) * (a / b)
a
null
null
b
null
null
CS340
b
Reading a Binary Tree

If we use a Scanner to read the individual lines created by the
toString and preOrderTraverse methods, we can
reconstruct the tree
2.
Read a line that represents information at the root
Remove the leading and trailing spaces using String.trim
3.
if it is "null"
1.
4.
return null
else
5.
recursively read the left child
6.
recursively read the right child
7.
return a tree consisting of the root and the two children
Reading a Binary Tree (cont.)
public static BinaryTree<String>
readBinaryTree(Scanner scan) {
String data = scan.next();
if (data.equals("null")) {
return null;
} else {
BinaryTree<String> leftTree = readBinaryTree(scan);
BinaryTree<String> rightTree = readBinaryTree(scan);
return new BinaryTree<String>(data, leftTree,
rightTree);
}
}
CS340
Using ObjectOutputStream and
ObjectInputStream


The Java API includes the class
ObjectOutputStream that will write to an
external file any object that is declared to be
Serializable
To declare an object Serializable, add
implements Serializable
to the class declaration
CS340
Using ObjectOutputStream and
ObjectInputStream (cont.)

To write a Serializable object to a file:
try {
ObjectOutputStream out =
new ObjectOutputStream(new
FileOutputStream(filename));
out.writeObject(nameOfObject);
} catch (Exception ex) {
ex.printStackTrace();
System.exit(1);
}

A deep copy of all the nodes of the binary tree will be
written to the file
CS340
Using ObjectOutputStream and
ObjectInputStream (cont.)

To read a Serializable object from a file:
try {
ObjectInputStream in =
new ObjectInputStream(new
FileInputStream(filename));
objectName = (objectClass)in.readObject();
} catch (Exception ex) {
ex.printStackTrace();
System.exit(1);
}
CS340
Using ObjectOutputStream and
ObjectInputStream (cont.)



Do not recompile the Java source file for a class
after an object of that class has been serialized
Even if you didn't make any changes to the class,
the resulting .class file associated with the
serialized object will have a different class
signature
When you attempt to read the object, the class
signatures will not match, and you will get an
exception
CS340