Discrete Mathematics
Lecture - 16
Syeda Tamanna Alam Monisha
Lecturer, CSE, Leading University
E-mail: monisha_cse@[Link]
Discrete
Mathematics
TREES and Its
Applications by
Rosen
11.1 7th Edition
INTRODUCTION
TO TREES
Tree
Tree
Contains not
Tree Tree simple connected
circuit
Rooted Trees
• Parent: If v is a vertex in T other than the root, the parent of v is the unique vertex u such that
there is a directed edge from u to v. When u is the parent of v, v is called a child of u.
• Siblings: Vertices with the same parent.
• Ancestors: The ancestors of a vertex other than the root are the vertices in the path from the
root to this vertex, excluding the vertex itself and including the root (that is, its parent, its
parent’s parent, and so on, until the root is reached).
• Descendants: The descendants of a vertex v are those vertices that have v as an ancestor.
• Leaf: A vertex of a rooted tree is called a leaf if it has no children.
• Internal vertices: Vertices that have children.
• The root is an internal vertex unless it is the only vertex in the graph, in which case it is a leaf.
Rooted Trees
• For the tree T in figure-5
• root : a
• parent of c : b
• children g : h, i and j
• siblings of h: i and j
• ancestors of e : c, b and a
• descendants of b : c, d and e
• leaves : d, e, f, k, i, l, m
• internal vertices : a, b, c, g, h and j
m-ary tree
full binary tree full 3-ary tree full 5-ary tree not a full m-ary
tree
Ordered Rooted Trees
• An ordered rooted tree is a rooted tree where the children of each internal
vertex are ordered.
• Ordered rooted trees are drawn so that the children of each internal vertex are
shown in order from left to right.
• In an ordered binary tree (usually called just a binary tree), if an internal vertex
has two children, the first child is called the left child and the second child is
called the right child.
Ordered Rooted Trees
Discrete
Mathematics
TREES and Its
Applications by
Rosen
7th Edition
11.3 TREE
TRAVERSAL
Tree Traversal
• Ordered rooted trees are often used to store information.
• We need procedures for visiting each vertex of an ordered rooted tree to access
data.
• We will describe several important algorithms for visiting all the vertices of an
ordered rooted tree.
• Ordered rooted trees can also be used to represent various types of expressions,
such as arithmetic expressions involving numbers, variables, and operations.
• The different listings of the vertices of ordered rooted trees used to represent
expressions are useful in the evaluation of these expressions.
Traversal Algorithms
• Procedures for systematically visiting every vertex of an ordered rooted
tree are called traversal algorithms.
• We will describe three of the most commonly used such algorithms,
preorder traversal, inorder traversal, and postorder traversal.
Preorder Traversal
Preorder Traversal
Preorder Traversal
Inorder Traversal
Inorder Traversal
Postorder Traversal
Postorder Traversal
Infix, Prefix, and Postfix Notation
• We can represent complicated expressions, such as compound propositions,
combinations of sets, and arithmetic expressions using ordered rooted trees.
• For instance, consider the representation of an arithmetic expression involving
the operators + (addition), − (subtraction), ∗ (multiplication), / (division), and ↑
(exponentiation).
• We will use parentheses to indicate the order of the operations.
• An ordered rooted tree can be used to represent such expressions, where the
internal vertices represent operations, and the leaves represent the variables or
numbers.
Infix, Prefix, and Postfix Notation
• Infix: X+Y
—We obtain the infix form of an expression when we traverse its
rooted tree in inorder.
—Operators are written in-between their operands.
+
• Prefix: +XY
—We obtain the prefix form of an expression when we traverse its
rooted tree in preorder. X Y
—Operators are written before their operands.
Figure: A binary tree T
• Postfix: XY+
—We obtain the prefix form of an expression when we traverse its
rooted tree in postorder.
—Operators are written after their operands.
Infix, Prefix, and Postfix Notation
Infix, Prefix, and Postfix Notation
Evaluating Infix, Prefix, and Postfix Notation
Evaluating Infix, Prefix, and Postfix Notation