Trees and Binary Trees in Computer Science
undefined
Trees and
Binary Trees
UNIT – III
PART - I
By
B VENKATESWARLU,
CSE Dept.
Nature View of a Tree
branches
leaves
root
Computer Scientist’s View
branches
leaves
What is a Tree
•
A tree is a finite nonempty
set of elements.
•
It is an abstract model of a
hierarchical structure.
•
consists of nodes with a
parent-child relation.
•
Applications:
•
Organization charts
•
File systems
•
Programming
environments
subtree
Tree Terminology
•
Root
: node without parent (A)
•
Siblings
: nodes share the same parent
•
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, grand-grandparent, etc.
•
Descendant
of a node: child,
grandchild, grand-grandchild, etc.
•
Depth
of a node: number of ancestors
•
Height
of a tree: maximum depth of
any node (3)
•
Degree
of a node: the number of its
children
•
Degree
of a tree: the maximum number
of its node.
•
Subtree
: tree consisting of a
node and its descendants
Tree Properties
Property
Value
Number of nodes
Height
Root Node
Leaves
Interior nodes
Ancestors of H
Descendants of B
Siblings of E
Right subtree of A
Degree of this tree
Tree ADT
•
We use positions to abstract
nodes
•
Generic methods:
•
integer
size
()
•
boolean
isEmpty
()
•
objectIterator
elements
()
•
positionIterator
positions
()
•
Accessor methods:
•
position
root
()
•
position
parent
(p)
•
positionIterator
children
(p)
•
Query methods:
•
boolean
isInternal
(p)
•
boolean
isExternal
(p)
•
boolean
isRoot
(p)
•
Update methods:
•
swapElements
(p, q)
•
object
replaceElement
(p, o)
•
Additional update methods may
be defined by data structures
implementing the Tree ADT
Intuitive Representation of Tree Node
•
List Representation
•
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
•
The root comes first, followed by a list of links to sub-trees
How many link fields are needed in
such a representation?
Trees
•
Every tree node:
•
object – useful information
•
children – pointers to its children
A Tree Representation
•
A node is represented by
an object storing
•
Element
•
Parent node
•
Sequence of children
nodes
Left Child, Right Sibling Representation
Tree Traversal
•
Two main methods:
•
Pre
order
•
Post
order
•
Recursive definition
•
Pre
order:
•
visit the root
•
traverse in preorder the children (subtrees)
•
Post
order
•
traverse in postorder the children (subtrees)
•
visit the root
Preorder Traversal
•
A traversal visits the nodes of a tree
in a systematic manner
•
In a preorder traversal, a node is
visited before its descendants
•
Application: print a structured
document
Algorithm
preOrder
(
v
)
visit
(
v
)
for
each
child
w
of
v
preorder
(
w
)
Postorder Traversal
•
In a postorder traversal, a node is
visited after its descendants
•
Application: compute space used
by files in a directory and its
subdirectories
Algorithm
postOrder
(
v
)
for
each
child
w
of
v
postOrder
(
w
)
visit
(
v
)
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
•
Applications:
•
arithmetic expressions
•
decision processes
•
searching
A
B
C
F
G
D
E
H
I
BinaryTree ADT
•
The BinaryTree 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
BinaryTree ADT
Examples of the Binary Tree
Differences Between A Tree and A Binary
Tree
•
The subtrees of a binary tree are ordered; those of a tree
are not ordered.
•
Are different when viewed as binary trees.
•
Are the same when viewed as trees.
Data Structure for Binary Trees
•
A node is represented by
an object storing
•
Element
•
Parent node
•
Left child node
•
Right child node
Arithmetic Expression Tree
•
Binary tree associated with an arithmetic expression
•
internal nodes: operators
•
external nodes: operands
•
Example: arithmetic expression tree for the expression (2
(
a
1)
(3
b))
Decision Tree
•
Binary tree associated with a decision process
•
internal nodes: questions with yes/no answer
•
external nodes: decisions
•
Example: dining decision
Want a fast meal?
How about coffee?
On expense account?
Starbucks
Spike’s
Al Forno
Café Paragon
Yes
No
Yes
No
Yes
No
Maximum Number of Nodes in a
Binary Tree
•
The maximum number of nodes on depth
i
of a
binary tree is
2
i
, i>=0.
•
The maximum nubmer of nodes in a binary tree of
height
k
is
2
k+1
-1
, k>=0.
Prove by induction.
Relations between Number of
Leaf Nodes and Nodes of Degree 2
For any nonempty binary tree, T, if
n
0
is the
number of leaf nodes and
n
2
the number of nodes
of degree 2, then
n
0
=n
2
+1
PROOF
:
Let
n
and
B
denote the total number of nodes and branches in
T
.
Let
n
0
,
n
1
,
n
2
represent the nodes with no children, single child, and
two children respectively.
B
+1=
n
B
=
n
1
+2
n
2
n
=
n
0
+
n
1
+
n
2
n
1
+2
n
2
+1=
n
n
0=
n
2+1
Full Binary Tree
•
A full binary tree of a given height
k
has
2
k+1
–1
nodes.
Labeling Nodes In A Full Binary Tree
•
Label the nodes
1
through
2
k+1
– 1
.
•
Label by levels from top to bottom.
•
Within a level, label from left to right.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node Number Properties
•
Parent of node
i
is node
i / 2
, unless
i = 1
.
•
Node
1
is the root and has no parent.
Node Number Properties
•
Left child of node
i
is node
2i
, unless
2i > n
, where
n
is the
number of nodes.
•
If
2i > n
, node
i
has no left child.
Node Number Properties
•
Right child of node
i
is node
2i+1
, unless
2i+1 > n
, where
n
is the number of nodes.
•
If
2i+1 > n
, node
i
has no right child.
Complete Binary Trees
•
A labeled binary tree containing the labels 1 to n with root 1, branches
leading to nodes labeled 2 and 3, branches from these leading to 4, 5 and
6, 7, respectively, and so on.
•
A binary tree with
n
nodes and level
k
is complete
iff
its nodes
correspond to the nodes numbered from 1 to
n
in the full binary tree of
level
k
.
Binary Tree Traversals
•
Let l, R, and r stand for moving left, visiting
the node, and moving right.
•
There are six possible combinations of traversal
•
lRr, lrR, Rlr, Rrl, rRl, rlR
•
Adopt convention that we traverse left before
right, only 3 traversals remain
•
lRr, lrR, Rlr
•
inorder, postorder, preorder
Inorder Traversal
•
In an inorder traversal a node
is visited after its left subtree
and before its right subtree
Algorithm
inOrder
(
v
)
if
isInternal
(
v
)
inOrder
(
leftChild
(
v
))
visit
(
v
)
if
isInternal
(
v
)
inOrder
(
rightChild
(
v
))
Print Arithmetic Expressions
•
Specialization of an inorder
traversal
•
print operand or operator when
visiting node
•
print “(“ before traversing left
subtree
•
print “)“ after traversing right
subtree
Algorithm
inOrder
(
v
)
if
isInternal
(
v
){(
“
(
’’
)
inOrder
(
leftChild
(
v
))}
(
v.element
())
if
isInternal
(
v
){inOrder
(
rightChild
(
v
))
(
“
)
’’
)}
((2
(
a
1))
(3
b))
Evaluate Arithmetic Expressions
•
recursive method returning
the value of a subtree
•
when visiting an internal
node, combine the values of
the subtrees
Algorithm
evalExpr
(
v
)
if
isExternal
(
v
)
return
v.element
()
else
x
evalExpr
(
leftChild
(
v
))
y
evalExpr
(
rightChild
(
v
))
operator stored at
v
return
x
y
Creativity:
pathLength(
tree
) =
depth(
v
)
v
tree
Algorithm
pathLength
(
v, n
)
Input: a tree node
v
and an initial value
n
Output: the pathLength of the tree with root
v
Usage: pl = pathLength(root, 0);
if
isExternal
(
v
)
return
n
return
(pathLength(leftChild (v)
,
n + 1) +
pathLength(rightChild (v), n + 1) + n)
Euler Tour Traversal
•
Generic traversal of a binary tree
•
Includes a special cases the preorder, postorder and inorder traversals
•
Walk around the tree and visit each node three times:
•
on the left (preorder)
•
from below (inorder)
•
on the right (postorder)
Euler Tour Traversal
eulerTour(node v) {perform action for visiting node on the left;
if v is internal then
eulerTour(v->left);
perform action for visiting node from below;
if v is internal then
eulerTour(v->right);
perform action for visiting node on the right;
}
Trees are a fundamental data structure in computer science, modeling hierarchical relationships between elements. This content covers tree terminology, properties, and abstract data type, providing insights into their representation and usage in various applications like organization charts, file systems, and programming environments.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
UNIT III PART - I Trees and Binary Trees By B VENKATESWARLU, CSE Dept.
Nature View of a Tree leaves branches root
Computer Scientists View root leaves branches nodes
What is a Tree A tree is a finite nonempty set of elements. It is an abstract model of a hierarchical structure. consists of nodes with a parent-child relation. Applications: Organization charts File systems Programming environments Computers R Us Sales Manufacturing R&D US International Laptops Desktops Europe Asia Canada
Tree Terminology Subtree: tree consisting of a node and its descendants Root: node without parent (A) Siblings: nodes share the same parent 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, grand-grandparent, etc. Descendant of a node: child, grandchild, grand-grandchild, etc. Depth of a node: number of ancestors Height of a tree: maximum depth of any node (3) Degree of a node: the number of its children Degree of a tree: the maximum number of its node. A D B C E F G H I J K subtree
Tree Properties Property Number of nodes Height Root Node Leaves Interior nodes Ancestors of H Descendants of B Siblings of E Right subtree of A Degree of this tree Value A C B D E F G H I
Tree ADT We use positions to abstract nodes Generic methods: integer size() boolean isEmpty() objectIterator elements() positionIterator positions() Accessor methods: position root() position parent(p) positionIterator children(p) Query methods: boolean isInternal(p) boolean isExternal(p) boolean isRoot(p) Update methods: swapElements(p, q) object replaceElement(p, o) Additional update methods may be defined by data structures implementing the Tree ADT
Intuitive Representation of Tree Node List Representation ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) The root comes first, followed by a list of links to sub-trees How many link fields are needed in such a representation? Data Link 1 Link 2 Link n
Trees Every tree node: object useful information children pointers to its children Data Data Data Data Data Data Data
A Tree Representation A node is represented by an object storing Element Parent node Sequence of children nodes B A D F B D A F C E C E
Left Child, Right Sibling Representation Data Left Child Right Sibling A B C D E F G H I J K L
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
Preorder Traversal A traversal visits the nodes of a tree in a systematic manner In a preorder traversal, a node is visited before its descendants Application: print a structured document AlgorithmpreOrder(v) visit(v) foreach child w of v preorder (w) 1 Become Rich 2 5 9 1. Motivations 2. Methods 3. Success Stories 3 6 7 8 4 1.1 Enjoy Life 2.2 Start a Web Site 2.3 Acquired by Google 1.2 Help Poor Friends 2.1 Get a CS PhD
Postorder Traversal In a postorder traversal, a node is visited after its descendants Application: compute space used by files in a directory and its subdirectories AlgorithmpostOrder(v) foreach child w of v postOrder (w) visit(v) 9 cs16/ 8 3 7 todo.txt 1K homeworks/ programs/ 4 5 6 1 2 Robot.java 20K h1c.doc 3K h1nc.doc 2K DDR.java 10K Stocks.java 25K
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 Applications: arithmetic expressions decision processes searching A 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 B C D E F G H I
BinaryTree ADT The BinaryTree 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 BinaryTree ADT
Examples of the Binary Tree Complete Binary Tree Skewed Binary Tree 1 A A A B 2 B B C C 3 F G D E D H 4 I E 5
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.
Data Structure for Binary Trees A node is represented by an object storing Element Parent node Left child node Right child node B B A D A D C E C E
Arithmetic Expression Tree Binary tree associated with an arithmetic expression internal nodes: operators external nodes: operands Example: arithmetic expression tree for the expression (2 (a 1) + (3 b)) + 2 3 b a 1
Decision Tree Binary tree associated with a decision process internal nodes: questions with yes/no answer external nodes: decisions Example: dining decision Want a fast meal? No Yes How about coffee? On expense account? Yes No Yes No Starbucks Spike s Al Forno Caf Paragon
Maximum Number of Nodes in a Binary Tree The maximum number of nodes on depth i of a binary tree is 2i, i>=0. The maximum nubmer of nodes in a binary tree of height k is 2k+1-1, k>=0. Prove by induction. k = i + = 1 i k 2 2 1 0
Full Binary Tree A full binary tree of a given height k has 2k+1 1 nodes. Height 3 full binary tree.
Labeling Nodes In A Full Binary Tree Label the nodes 1 through 2k+1 1. Label by levels from top to bottom. Within a level, label from left to right. 1 2 3 4 6 5 7 8 9 10 11 12 13 14 15
Node Number Properties 1 2 3 4 6 5 7 8 9 10 11 12 13 14 15 Parent of node i is node i / 2, unless i = 1. Node 1 is the root and has no parent.
Node Number Properties 1 2 3 4 6 5 7 8 9 10 11 12 13 14 15 Left child of node i is node 2i, unless 2i > n, where n is the number of nodes. If 2i > n, node i has no left child.
Node Number Properties 1 2 3 4 6 5 7 8 9 10 11 12 13 14 15 Right child of node i is node 2i+1, unless 2i+1 > n, where n is the number of nodes. If 2i+1 > n, node i has no right child.
Complete Binary Trees A labeled binary tree containing the labels 1 to n with root 1, branches leading to nodes labeled 2 and 3, branches from these leading to 4, 5 and 6, 7, respectively, and so on. A binary tree with n nodes and level k is complete iff its nodes correspond to the nodes numbered from 1 to n in the full binary tree of level k. 1 1 2 3 2 3 6 7 5 4 7 4 6 5 14 15 13 12 10 9 11 8 8 9 Complete binary tree Full binary tree of depth 3
Binary Tree Traversals Let l, R, and r stand for moving left, visiting the node, and moving right. There are six possible combinations of traversal lRr, lrR, Rlr, Rrl, rRl, rlR Adopt convention that we traverse left before right, only 3 traversals remain lRr, lrR, Rlr inorder, postorder, preorder
Inorder Traversal AlgorithminOrder(v) ifisInternal (v) inOrder (leftChild (v)) visit(v) ifisInternal (v) inOrder (rightChild (v)) In an inorder traversal a node is visited after its left subtree and before its right subtree 6 2 8 1 4 7 9 3 5
Print Arithmetic Expressions AlgorithminOrder (v) ifisInternal (v){ print( ( ) inOrder (leftChild (v))} print(v.element ()) ifisInternal (v){ inOrder (rightChild (v)) print ( ) )} Specialization of an inorder traversal print operand or operator when visiting node print ( before traversing left subtree print ) after traversing right subtree + 2 3 b ((2 (a 1)) + (3 b)) a 1
Evaluate Arithmetic Expressions recursive method returning the value of a subtree when visiting an internal node, combine the values of the subtrees AlgorithmevalExpr(v) ifisExternal (v) returnv.element () else x evalExpr(leftChild (v)) y evalExpr(rightChild (v)) operator stored at v returnx y + 2 3 2 5 1
Creativity: pathLength(tree) = depth(v) v tree AlgorithmpathLength(v, n) Input: a tree node v and an initial value n Output: the pathLength of the tree with root v Usage: pl = pathLength(root, 0); ifisExternal (v) return n return (pathLength(leftChild (v), n + 1) + pathLength(rightChild (v), n + 1) + n)
Euler Tour Traversal Generic traversal of a binary tree Includes a special cases the preorder, postorder and inorder traversals Walk around the tree and visit each node three times: on the left (preorder) from below (inorder) on the right (postorder) + L R B 2 3 2 5 1
Euler Tour Traversal eulerTour(node v) { perform action for visiting node on the left; if v is internal then eulerTour(v->left); perform action for visiting node from below; if v is internal then eulerTour(v->right); perform action for visiting node on the right; }
