Unit -IV Trees
1
Topics to be covered
Concept of non-linear data structure,
binary trees-concepts, and terminologies,
Conversion of general tree to binary tree,
binary tree as an ADT,
expression tree,
recursive and non-recursive algorithms for binary
tree traversals,
binary search trees,
threaded binary tree.
Case study: Searching, hierarchical file systems.
2
Non-Linear Data Structure
It is a form of data structure where the data elements
are not arranged linearly or sequentially.
Since the data structure is non-linear, it does not
involve a single level.
So, a user can't traverse all its elements in a single
run.
3
Difference Between Linear and Non-linear Data
Structures
Parameter Linear Data Structure Non-Linear Data Structure
In a linear data structure, the data elements In a non-linear data structure, the data
Arrangement of
Data Element
connect to each other sequentially. A user can elements connect to each other hierarchically.
transverse each element through a single run. Thus, they are present at various levels.
The non-linear data structures are
Complexity of The linear data structures are comparatively comparatively difficult to implement and
Implementation easier to implement. understand as compared to the linear data
structures.
A user can find all the data elements at a single One can find all the data elements at multiple
Levels
level in a linear data structure. levels in a non-linear data structure.
It is not easy to traverse the non-linear data
You can traverse a linear data structure in a
Traversal structures. The users need multiple runs to
single run.
traverse them completely.
It is not very memory-friendly. It means that
Utilization of The data structure is memory-friendly. It
the linear data structures can’t utilize memory
Memory means that it uses memory very efficiently.
very efficiently.
The time complexity of this data structure is
Non-linear data structure’s time complexity
Complexity of directly proportional to its size. It means that
often remains the same with an increase in its
Time the time complexity increases with increasing
input size.
input size.
Linear data structures work well mainly in the Non-linear data structures work mainly well in
Applications
development of application software. image processing and Artificial Intelligence.
Examples List, Array, Stack, Queue. Map, Graph, Tree.
4
What is a Tree
A tree is a finite nonempty
set of elements.
Computers
It is an abstract model of a
hierarchical structure. Sales Manufacturing R&D
Consists of nodes with a
US International Laptops Desktops
parent-child relation.
Applications: Europe Asia Canada
Organization charts
File systems
Programming environments
5
Tree Terminology
Root: node without parent (A)
Subtree: tree consisting of a
Siblings: nodes share the same parent node and its descendants
Internal node: node with at least one child
(A, B, C, F)
External node (leaf ): node without
children (E, I, J, K, G, H, D)
Ancestors of a node: parent, grandparent, A
grand-grandparent, etc.
Descendant of a node: child, grandchild,
grand-grandchild, etc. B C D
Depth of a node: number of ancestors
Height of a tree: maximum depth of any
node (3) E F G H
Degree of a node: the number of its
children
Degree of a tree: the maximum number of I J K
its node. subtree
6
Tree Properties
Property Value
A
Number of nodes
Height
B C
Root Node
Leaves
D E F Interior nodes
Ancestors of H
Descendants of B
G Siblings of E
Right subtree of A
H I Degree of this tree
7
A Tree Representation
A node is represented by
an object storing
Element
Parent node B
Sequence of children
nodes
A D F
B
A D F
C E
C E
10
Left Child, Right Sibling Representation
Data
Left Right
Child Sibling A
B C D
E F G H I
J K L
11
Binary Tree
A binary tree is a tree with the following properties:
• Each internal node has at most two children (degree of two).
• The children of a node are an ordered pair.
We call the children of an internal node left child and right
child.
Alternative recursive definition: a binary tree is either
• a tree consisting of a single node, OR
• a tree whose root has an ordered pair of children, each of which
is a binary tree A
Applications: B C
• arithmetic expressions
• decision processes D E F G
• searching H I
12
Binary Trees
ADT: Binary Tree
The Binary Tree ADT extends the Tree ADT, i.e., it
inherits all the methods of the Tree ADT.
Additional methods:
• position leftChild(p)
• position rightChild(p)
• position sibling(p)
Update methods may be defined by data structures
implementing the Binary Tree ADT.
13
Binary Tree
ADT: Binary Tree
Examples of the Binary Tree
Skewed Binary Tree Complete Binary Tree
A A 1 A
B B 2 B C
C 3 F G
D E
D
4 H I
E 5
14
Differences Between A Tree and A
Binary Tree
The subtrees of a binary tree are ordered; those of a tree
are not ordered.
A A
B B
• Are different when viewed as binary trees.
• Are the same when viewed as trees.
15
Data Structure for Binary
Trees
A node is represented by
an object storing
Element
Parent node
Left child node B
Right child node
B A D
A D
C E
C E
16
General Trees
• A general tree is a tree which each node can have an
unlimited outdegree.
• Binary trees are presented easier then general trees in
programs.
• In general tree, there are two releationships that we can
use:
– Parent to child and,
– Sibling to sibling.
Using these two relationships, we can represent any general
tree as a binary tree.
17
Insertion Into General Trees
Key-sequence insertion; places the new node in key sequence among
the sibling nodes.
20
Converting
General Trees To Binary Trees
21
Tree Traversal
Two main methods:
Preorder
Postorder
Recursive definition
Preorder:
visit the root
traverse in preorder the children (subtrees)
Postorder
traverse in postorder the children (subtrees)
visit the root
22
Binary Tree Traversal
Preorder traversal:
1. root
2. left subtree
3. right subtree
Inorder traversal:
1. left subtree
2. root
3. right subtree
Postorder traversal:
1. left subtree
2. right subtree
3. root
23
Binary Tree Traversals
Preorder = ?
Inorder = ?
Postorder = ?
24
Binary Tree Traversals - Preorder
25
Binary Tree Traversals - Preorder
26
Binary Tree Traversals - Inorder
27
Binary Tree Traversals - Postorder
28
Binary Tree Traversals
Preorder = ABCDEF
Inorder = CBDAEF
Postorder = CDBFEA
29
Binary Tree – Breadth-First Traversals
30
Expression Trees
An expression tree is a binary tree with these properties:
1. Each leaf is an operand.
2. The root and internal nodes are operators.
3. Subtrees are subexpressions with the root being an operator.
31
Binary Tree With Arithmetic
Expression
* E
* D
/ C
A B
34
Tree Traversal
Inorder Traversal: A/B*C*D+E
=> Infix form
Preorder Traversal: +**/ABCDE
=> Prefix form
Postorder Traversal: AB/C*D*E+
=> Postfix form
35
Construction of Expression Tree
Algorithm( Scan Postfix expression from left to right)
E.g: (a+b*c)/d abc*+d/
1. Read a symbol from the string
2. If ( symbol is an operand) then
a) Create a node
b) Push a pointer to it onto stack
3. If (symbol is operator) then
a) T2=POP
T1=POP
b) Here T1 and T2 are pointers to left trees and right subtree
of operator respectively
c) Form a tree whose root is the operator and T1 and T2 are
left and right children respectively
d) Push a pointer to this new subtree onto a stack
4. Repeat steps 1, 2 and 3 till end of expression
5. Pop the pointer to this new subtree onto a stack 36
Expression Tree
+
- e
* /
a b c d
37
+
- e
* /
a b c d
Inorder: a*b-c/d+e
Postorder: ab*cd/-e+
Preorder: +-*ab/cde
38
Binary Tree Traversals
• A binary tree travelsal requires each node of the tree be processed once.
• In the depth-first traversal, all of the descendents of a child are processed before the
next child.
• In the breadth-first traversal, each level is completely processed before the next level
is started.
NLR LNR LRN
39
Preorder Traversal (NLR)
void PreOrder(treePointer ptr)
{
if if (ptr != NULL)
{
printf(“%d\t”, ptr->data); // visit the root
preOrder(ptr->leftChild); // traverse the leftsubtree
preOrder(ptr->rightChild); // traverse the rightsubtree
}// end of if
} // end of preorder traversal
40
Preorder Example (NLR)
b c
a b c
41
Preorder Example (NLR)
b c
f
d e
g h i j
42
Preorder Example (NLR)
b c
f
d e
g h i j
a b d g h e i c f j
43
Preorder Of Expression Tree (NLR)
/
* +
e f
+ -
a b c d
/ * + a b - c d + e f
Gives prefix form of expression!
44
Inorder Traversal (LNR)
void InOrder(treePointer ptr)
{
if if (ptr != NULL)
{
inOrder(ptr->leftChild); // traverse the left subtree
printf(“%d\t”, ptr->data); // visit the root
inOrder(ptr->rightChild); // traverse the right subtree
} // end of if
} // end of Inorder traversal
45
Inorder Example (LNR)
b c
b a c
46
Inorder Example (LNR)
b c
f
d e
g h i j
47
Inorder Example (LNR)
b c
f
d e
g h i j
g d h b e i a f j c
48
Inorder Of Expression Tree (LNR)
/
* +
e f
+ -
a b c d
a + b * c - d / e + f
Gives infix form of expression (sans parentheses)!
49
Postorder Traversal (LRN)
void PostOrder(treePointer ptr)
{
if (ptr != NULL)
{
postOrder(ptr->leftChild); // traverse the left subtree
postOrder(ptr->rightChild); // traverse the right subtree
printf(“%d\t”, ptr->data); // visit the root
} // end of if
} // end of Postorder traversal
50
Postorder Example (LRN)
b c
b c a
51
Postorder Example (LRN)
b c
f
d e
g h i j
52
Postorder Example (LRN)
b c
f
d e
g h i j
g h d i e b j f c a
53
Postorder Of Expression Tree (LRN)
/
* +
e f
+ -
a b c d
a b + c d - * e f + /
Gives postfix form of expression!
54