Transcript Slide 1

CS212: DATA STRUCTURES
Computer Science
Department
Lecture 7: Tree_Part1
Trees
2
Linked lists usually are more flexible than arrays,
but it is difficult to use them to organize a hierarchical
representation of objects.
 Stacks and queues reflect some hierarchy but are
limited to only one dimension.
 For these reasons, create a new data type tree that
consists of nodes and arcs/edges and has the root at
the top and the leaves (terminal nodes) at the bottom.

20-Jul-15
Computer Science Department
Tree Definitions and Properties
A tree is an abstract data type that stores elements
hierarchically.
 With the exception of the top element, each element in a tree
has a parent element and zero or more children elements.

Formally, we define a tree T as a set of nodes storing elements such that
the nodes have a parent-child relationship, that satisfies the following
properties:

If T is nonempty, it has a special node, called the root of T, that has no
parent.

Each node v of T different from the root has a unique parent node w;
every node with parent w is a child of w.
Tree Terminology / concepts
4

Empty tree: meaning that it doesn't have any nodes.

Parent : Any node (except the root) has exactly one edge running
upward to another node or
 A node is a parent if it has successor nodes; that is, if it has
outdegree greater than zero.

Child : Any node can have one or more lines running downward to
other nodes.
 It has a predecessor node

Siblings :Two or more nodes with the same parent.

A node v is external if v has no children. External nodes are also
known as leaves.

A node v is internal if it has one or more children.
20-Jul-15
Computer Science Department
Example
5
20-Jul-15
Computer Science Department
Tree Terminology / concepts con..
6





Ancestor : Any node in the path from the root to the node
Descendent :
 Any node in the path below the parent node
 All nodes in the paths from a given node to a leaf node
Subtree : any node can be considered to be the root of a
subtree, which consists of its children, and its children's
children, and so on.
An edge of tree T is a pair of nodes (u, v) such that u is the
parent of v, or vice versa.
A path of T is a sequence of nodes such that any two
consecutive nodes in the sequence form an edge.
20-Jul-15
Computer Science Department
Tree Terminology / concepts con..
7

Level of the node :
The length of the path from the root to the node.
Level of a node is its distance from the root.

Length : the number of arcs in a path.

Visiting : a node is visited when program control arrives at the node,
usually for the purpose of carrying out some operation on the node.

Traversing : to visit all the nodes in some specified order.

Key : a value that is used to search for the item or perform other
operations on it.
Tree representing a portion of a file system.
8
cs252/ is an ancestor of papers/, and pr3 is a descendent of cs016/.
The subtree rooted at cs016/ consists of the nodes cs016/, grades, homeworks/,
programs/, hw1, hw2, hw3, pr1, pr2, and pr3.
the tree contains the path (cs252/, projects/, demos/, market).
20-Jul-15
Computer Science Department
Ordered Trees
9

A tree is ordered if there is a linear ordering defined for the
children of each node. that is, we can identify the children of a node
as being the first, second, third, and so on.
20-Jul-15
Computer Science Department
The Tree Abstract Data Type
10


The tree ADT stores elements at positions, which,
as with positions in a list, are defined relative to
neighboring positions.
The positions in a tree are its nodes, and
neighboring positions satisfy the parent-child
relationships that define a valid tree.
20-Jul-15
Computer Science Department
The Tree Abstract Data Type con..
11
a position object for a tree supports the method :
element():
return the object stored at this position.
root():
return the tree's root; an error occurs if the tree is
empty.
parent (v):
return the parent of v; an error occurs if v is the root.
20-Jul-15
Computer Science Department
The Tree Abstract Data Type con..
12
children(v):
return an iterable collection containing the children
of node v.
If a tree T is ordered, then the iterable collection,
children(v), stores the children of v in order. If v is an
external node, then children(v) is empty.
20-Jul-15
Computer Science Department
The Tree Abstract Data Type con..
13
Query methods:
isInternal(v):
Test whether node v is internal.
isExternal(v):
Test whether node v is external.
isRoot(v):
Test whether node v is the root.
20-Jul-15
Computer Science Department
The Tree Abstract Data Type con..
14
Generic methods:
size():
return the number of nodes in the tree.
isEmpty():
Test whether the tree has any nodes or not.
iterator():
return an iterator of all the elements stored at nodes of the tree.
positions():
return an iterable collection of all the nodes of the tree.
replace(v,e):
Replace with e and return the element stored at Computer
node v.
20-Jul-15
Science Department
Implementing a Tree
15
20-Jul-15
Computer Science Department