Transcript Trees

Trees
CS 105
Definition

The Tree Data Structure




stores objects (nodes) hierarchically
nodes have parent-child relationships
operations include accessing the parent or
children of a given node
A tree T is a set of nodes such that


there is a distinguished node r
(called the root) of T that has no parent
each node v of T except r has a parent
node
L9: Trees
Slide 2
Visualizing a Tree
Root
R
Child
T
P
O
I
A
N
M
G
L9: Trees
Slide 3
Sample Uses








A company’s organizational structure
Family tree
The Java class hierarchy
O/S directory structure
Book (parts, chapters, sections)
Arithmetic expressions
Web page links
Priority queues and search trees
L9: Trees
Slide 4
Tree Terminology

Root


Leaf (External node)


node that has no children
Internal node


the only node that has no parent
node that has at least one child
Siblings

nodes that have a common parent
L9: Trees
Slide 5
More Tree Terminology

Ancestor



Descendant


recursive definition: ancestors of a node v
are v itself and the ancestors of its parent
proper ancestors: ancestors excluding itself
v is a descendant of u if u is an ancestor of v
Subtree of T rooted at v

set of all descendants of v
L9: Trees
Slide 6
Even More Terminology

Ordered Tree


Binary Tree


children of a node have a strict linear order
an ordered tree where nodes have at most
two children (left and right)
Depth and Height of a node


depth: distance from node to root
height: from node to its farthest descendant
L9: Trees
Slide 7
Tree Implementations

Array-based implementation



elements (or references to them) are stored
in an array
parent-child relationships derived from
indices
Linked implementation


elements stored in nodes
nodes contain pointers to parent and children
L9: Trees
Slide 8
Tree Operations








Get the root node of the tree
Go to parent or children from a given node
Add a root to an empty tree
Add a child to a node
Remove a node (can impose that the node be a
leaf, for simplicity)
Get the element associated to a node
Replace the element associated to a node
Others …
L9: Trees
Slide 9
Binary Tree operations



For a binary tree, a node has at most two
children and are ordered
Could distinguish between the left and
right child of a node
Implementations are simpler for binary
trees but many concepts apply to general
trees
L9: Trees
Slide 10
Implementing trees

Array implementation


Array indices are used to navigate from
parent to children or from children to parent
Node implementation

Node contains data and references to
children and parent
L9: Trees
Slide 11
Data structures that use trees

Priority queues


Heap: tree structure (usually array-based)
where the hierarchy imply the priorities of
the elements
Dictionary

Binary Search Tree: tree structure (usually
node-based) that facilitates “binary search”
of the nodes
L9: Trees
Slide 12