الجامعة السعودية االلكترونية
الجامعة السعودية االلكترونية
26/12/2021
1
College of Computing and
Informatics
Data Structure
2
Data Structure
Module 6
Tree – Part 1
3
1. Fundamental / Structure of the Trees
2. Tree Traversals with an Application
3. Implementation Binary Trees
4. Binary Search Tree
5. Tree Traversal (Revisited, detailed example)
Contents
4
1. Understand Search Tree Abstract Data Type
2. Implement Binary Search Tree
3. Recognize some applications adopt Binary Search Tree
Weekly
Learning
Outcomes
5
Required Reading
1. Chapter 4 (Data structures and algorithm
analysis in Java by Mark Allen Weiss)
Recommended Reading
1. Chapter 12 (al, Cormen Thomas H et. Introduction to
Algorithms. Cambridge, MA: MIT Press, 2009)
2. Binary Tree, Introduction:
[Link]
6
• Fundamental / Structure of the Trees
7
Fundamental / Structure of the Trees
• Extension of Linked List structure:
• Each node connects to multiple nodes
• Just like Linked Lists, Trees are collections of nodes
• Conceptualize trees upside down (like family trees)
• the top node is the root
• nodes are connected by edges
• edges define parent and child nodes
• nodes with no children are called leaves
8
Fundamental / Structure of the Trees
• Nodes that share the same parent are siblings
• A path is a sequence of nodes such that the next node in the
sequence is a child of the previous
9
Fundamental / Structure of the Trees
• A nodeʼs depth is the length of the path from root
• The height of a tree is the maximum depth
• if a path exists between two nodes, one is an ancestor and the other is a
descendant
10
Fundamental / Structure of the Trees
• Since the number of children per node can vary so greatly and is not
known in advance,
• it might be infeasible to make the children direct links in the data structure,
• because there would be too much wasted space.
• The solution is simple: Keep the children of each node in a linked list of tree
nodes.
11
• Tree Traversals with an Application
12
Tree Traversals with an Application
• A typical directory in the UNIX file system is shown on the figure.
• The root of this directory is /usr.
• The filename /usr/mark/book/ch1.r is obtained by following the
leftmost child three times.
13
Tree Traversals with an Application
• Suppose we would like to list the names of all
of the files in the directory .
• Preorder - read the parent before its children
14
Tree Traversals with an Application
• This traversal strategy is known as a preorder traversal.
• In a preorder traversal, work at a node is performed before (pre) its children
are processed.
• Thus, the total amount of work is constant per node. If there are N file names
to be output, then the running time is O(N).
15
Tree Traversals with an Application
• The postorder traversal.
• In a postorder traversal, the work at a node is performed after (post) its
children are evaluated.
• Postorder - read the parent after its children
16
Tree Traversals with an Application
• The postorder traversal.
17
• Implementation Binary Trees
18
Implementation Binary Trees
• No node can have more than two children
• A binary tree is full if each node has 2 or 0 children
• A binary tree is perfect if it is full and each leaf is at the same depth
• That depth is O(log N)
19
Implementation Binary Trees
• Expression Trees Example
(a + (b * c)) + (((d * e) + f) * g)
• Traverse Stratgies:
• inorder traversal: (left, node, right)
• postorder traversal: (left, right, node)
• Preorder traversal: (node, left, right)
20
Implementation Binary Trees
• Constructing an Expression Tree
• convert a postfix expression into an expression tree
• The input is: ab+cde+**
(1)
(2) 21
Implementation Binary Trees
• Constructing an Expression Tree
• The input is: ab+cde+**
(3)
(4) 22
Implementation Binary Trees
• Constructing an Expression Tree
• The input is: ab+cde+**
(5)
(6) 23
Thank
You
24