Transcript Slide 1

Trees
What is a Tree?
7/16/2015
2
What is a Tree?
• Trees are an important data structure
• They organize data hierarchically
• They are used to
– model hierarchical data in the real world
– store and retrieve data
7/16/2015
3
Computers”R”Us
Sales
Local
Manufacturing
International
Europe
Asia
Laptops
R&D
Desktops
Africa
A hierarchical organization of a hypothetical company
7/16/2015
4
Tree Terminology
• Node
a
– Data stored in the tree
• Child
– A node descended from
another node
• Parent
b
c
a is the parent of both
b&c
b & c are children of a
– The node from which another
node descended
7/16/2015
5
Tree Terminology
Root
The node from which all
others descend
Branch
Joins nodes
Leaf (External node )
A node without children
Degree=3
Maximum # of children
Siblings
Children of a common parent
7/16/2015
6
Tree Terminology
• Ancestors of a node
– Any node from which a node descended
(parent, grandparent, grand-grandparent, etc).
• Descendant of a node
– Any child, grandchild, grand-grandchild, etc.
• Depth of a node
– Number of ancestors
7/16/2015
7
Tree Terminology
• Height of a tree
– Maximum depth of any node
• Subtree
– Tree consisting of a node and its descendants
• Path
– The set of branches connecting an ancestor
to a descendant
7/16/2015
8
Tree Terminology
Depth = 0
Depth = 2
Depth = 3
Subtree
7/16/2015
9
Trees vs. Graphs
• A tree
– Cannot contain cycles
– Each node has 1 parent or it is
at the root
• Any structure which does not
meet these criteria is a graph
• The structures to the right are
graphs
7/16/2015
10
Review: Recursive definition of list
Empty list (0 nodes)
OR
Head node and 0 or 1 non-empty sublist
7/16/2015
11
Recursive definition of Tree
• Empty tree (0
nodes)
OR
• Root node and 0
or more nonempty subtrees
(child node and
its descendents)
7/16/2015
12
Tree Traversal
• To traverse any data structure means to
visit every node in turn in a systematic
manner
7/16/2015
13
Review: List Traversal
• List – process sequentially by
1.iteration
2. recursion
7/16/2015
14
Tree Traversal
• Pre-order
• In-order
• Post-order
7/16/2015
15
Pre-order Traversal
1
• Recursive definition:
Visit root before
children
Algorithm preOrder(v)
visit(v)
for each child w of v
preOrder (w)
2
4
3
5
6
7
8
11
10
9
7/16/2015
16
Post-order Traversal
11
• Recursive definition:
Visit root after
children
Algorithm postOrder(v)
for each child w of v
postOrder (w)
visit(v)
2
3
1
10
4
8
6
9
7
5
7/16/2015
17
Traversal example
Pre-order: 7 4 3 5 12 9
7
4
3
7/16/2015
12
5
Post-order: 3 5 4 9 12 7
9
18
Implementing trees
• List
– Node: data & reference
• Tree
– Node: data & references
7/16/2015
class ListNode
{int data;
ListNode next;
}
class TreeNode
{int data;
TreeNode
child1,
child2,
child3;
}
19
Implementing trees
• Problem of
representing a node:
How many edges to
allow for? e.g.,
Class TreeNode
{
int data;
TreeNode
child1,
child2,
child3;
}
7/16/2015
20
Implementing trees
• Problem of
representing a node:
Three solutions:
1. allow lots of child edge
references
2. restrict tree structure to
two child edges (binary
tree)
3. use first child/next sibling
representation
7/16/2015
21
First child/next sibling
Class TreeNode
{
int data;
TreeNode
child,
sibling;
}
Problem:
Makes path to most nodes
longer
7/16/2015
22