Transcript Trees

CSCI 3333 Data Structures
Trees
by
Dr. Bun Yue
Professor of Computer Science
[email protected]
http://sce.uhcl.edu/yue/
2013
Acknowledgement




Mr. Charles Moen
Dr. Wei Ding
Ms. Krishani Abeysekera
Dr. Michael Goodrich
What is a Tree


In computer
Computers”R”Us
science, a tree is
an abstract
model of a
Sales
Manufacturing
R&D
hierarchical
structure
A tree consists US International Laptops Desktops
of nodes with a
parent-child
Europe
Asia
Canada
relation
Trees

Each node in the tree has





0 or 1 parent node.
0 or more child nodes.
Only the root node has no parent.
A tree can be considered as a special case
of a directed (acyclic) graph.
Example: a family tree may not
necessarily be a tree in the computing
sense.
Trees
British Royal Family Tree
Queen Victoria
King Edward VII
Albert Victor
Alice
King George V
King Edward VIII
King George VI
Queen Elizabeth II
Charles
William
Henry
Ann
Peter
Andrew
Zara
Beatrice
Eugenie
Edward
5
Some Tree Applications

Applications:




Organization charts
File Folders
Email Repository
Programming environments: e.g.
drop down menus.
Recursive Definition of Trees


An empty tree is a tree.
A tree contains a root node
connected to 0 or more child subtrees.
Trees
Are these trees?
1
3
2
4
8
Tree Terminology







Root: node without parent (A)

Internal node: node with at least
one child (A, B, C, F)
External node (a.k.a. leaf ):
node without children (E, I, J, K,
G, H, D)
Ancestors of a node: parent,
grandparent, grandgrandparent, etc.
Depth of a node: number of
E
ancestors
Height of a tree: maximum
depth of any node (3)
Descendant of a node: child,
I
grandchild, grand-grandchild,
etc.
Subtree: tree consisting
of a node and its
descendants
A
B
C
F
J
G
K
D
H
subtree
Tree ADT (§ 6.1.2)


We use positions to
abstract nodes
Generic methods:





integer size()
boolean isEmpty()
Iterator elements()
Iterator positions()
Accessor methods:



position root()
position parent(p)
positionIterator
children(p)

Query methods:




Update method:


boolean isInternal(p)
boolean isExternal(p)
boolean isRoot(p)
object replace (p, o)
Additional update
methods may be defined
by data structures
implementing the Tree
ADT
Interface TreeNode in Java







Enumeration children(): Returns the children of
the receiver as an Enumeration.
boolean getAllowsChildren(): Returns true if the
receiver allows children.
TreeNode getChildAt(int childIndex): Returns the
child TreeNode at index childIndex.
int getChildCount(): Returns the number of
children TreeNodes the receiver contains.
int getIndex(TreeNode node): Returns the index
of node in the receivers children.
TreeNode getParent(): Returns the parent
TreeNode of the receiver.
Boolean isLeaf(): Returns true if the receiver is a
leaf.
Interface MutatableTreeNode


Sub-interface of TreeNode
Methods:






void insert(MutableTreeNode child, int index):
Adds child to the receiver at index.
void remove(int index): Removes the child at
index from the receiver.
void remove(MutableTreeNode node):
Removes node from the receiver.
void removeFromParent(): Removes the
receiver from its parent.
void setParent(MutableTreeNode newParent):
Sets the parent of the receiver to newParent.
void setUserObject(Object object): Resets the
user object of the receiver to object.
Size of a tree


Size = number of nodes in the tree.
Recursion analysis:


Base case: empty root => return 0;
Recursive case: non-empty root
=> return 1 + sum of size of all
child sub-trees.
Size of a tree
Algorithm size(TreeNode root)
Input TreeNode root
Output: size of the tree
if (root = null)
return 0;
else
return 1 + Sum of sizes of all children of
root
end if
Implementation in Java
public static int size(TreeNode root) {
if (root == null) return 0;
Enumeration enum = root.children();
int result = 1; // count the root.
while (enum.hasMoreElement()) {
result += size((TreeNode)
enum.nextElement());
}
return result;
}
Trees in languages

There are no general tree classes in the
standard libraries in many languages:
e.g. C++ STL, Ruby, Python, etc.


No single interface tree design satisfies all
users.
There may be specialized trees, especially
for GUI design. E.g.


JTree in Java
FXTreeList in Ruby
Tree Traversal


Traversing is the systematic way of
accessing, or ‘visiting’ all the nodes
in a tree.
Consider the three operations on a
binary tree:



V: Visit a node
L: (Recursively) traverse the left
subtree of a node
R: (Recursively) traverse the right
subtree of a node
Tree Traversing

We can traverse a tree in six
different orders:
LVR
VLR
LRV
VRL
RVL
RLV
Preorder Traversal



A traversal visits the nodes of
a tree in a systematic manner
In a preorder traversal, a
node is visited before its
descendants
Application: print a structured
document
1
Algorithm preOrder(v)
visit(v)
for each child w of v
preorder (w)
Make Money Fast!
2
5
1. Motivations
9
2. Methods
3
4
1.1 Greed
1.2 Avidity
6
2.1 Stock
Fraud
7
2.2 Ponzi
Scheme
References
8
2.3 Bank
Robbery
Java Implementation
public static void preorder(TreeNode root) {
if (root != null) {
visit(root); // assume declared.
Enumernation enum = root.children();
while (enum.hasMoreElement()) {
preorder((TreeNode)
enum.nextElement());
}
}
Postorder Traversal


In a postorder traversal, a
node is visited after its
descendants
Application: compute space
used by files in a directory
and its subdirectories
9
Algorithm postOrder(v)
for each child w of v
postOrder (w)
visit(v)
cs16/
3
8
7
homeworks/
todo.txt
1K
programs/
1
2
h1c.doc
3K
h1nc.doc
2K
4
DDR.java
10K
5
Stocks.java
25K
6
Robot.java
20K
Inorder Traversal

For binary tree, inorder traversal
can also be defined: L V R.
Java Implementation
public static void inorder(TreeNode
root) {
if (root != null) {
inorder(root.getChildAt(0));
visit(root); // assume declared.
inorder(root.getChildAt(1));
}
Expression Notation

There are three common notations
for expressions:



Prefix: operator come before operands.
Postfix: operator come after operands.
Infix:
Binary operator come between operands.
 Unary operator come before the operand.

Examples

Infix: (a+b)*(c-d/f/(g+h))


Prefix: *+ab-c//df+gh



Used by human being.
E.g. functional language such as Lisp:
Lisp: (* (+ a b) (- c (/ d (/ f (+ g h)))))
Postfix: ab+cdf/gh+/-*

E.g. Postfix calculator
Expression Trees

An expression tree can be used to
represent an expression.



Operator: root
Operands: child sub-trees
Variable and constants: leaf nodes.
Traversals of Expression Trees



Preorder traversal => prefix
notation.
Postorder traversal => postfix
notation.
Inorder traversal with parenthesis
added => infix notation.
Linked Structure for Trees

A node is represented
by an object storing




Element
Parent node
Sequence of children
nodes

B
Node objects implement
the Position ADT
D
C

A
B
A

D
F
F

E
C

E
Tree Classes in Ruby


FXTreeItem: a tree node for GUI
application.
Some methods:



Tree related: childOf?, parentOf?,
numChildren, parent, etc.
Traversal of child nodes: first, next,
last, etc.
GUI related: selected?, selected=,
hasFocus?, etc.
Tree Classes in Ruby 2


FXTreeList: a list of FXTreeItem.
Include methods for list
manipulation, such as appendItem,
clearItems, etc.
Questions and Comments?