Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

Struktur Diskret : Penelusuran Pohon, dan Ekspresi Infix, Prefix, dan Postfix

Tree Traversal

Ordered trees are often used to restore data/info. Tree traversal is a procedure for systematically visiting each vertex of an ordered rooted tree to access data.

If the tree is label by Universal Address System we can totally order the vertices using lexicographic ordering 

Example : 

0 < 1 < 1.1 < 1.2 < 1.2.1 < 1.3 < 2 < 3 < 3.1 < 3.1.1 < 3.1.2 < 3.1.2.1 < 3.1.2.2 < 4 < 4.1

Tree traversal algorithm :

• Preorder
• Inorder
• Postorder traversal

Preorder Traversal

Let T be an ordered rooted tree with root r. If T consists only of r, then r is the preorder traversal of T. If T1, T2, …, Tn are subtrees at r from left to right in T, then the preorder traversal begins by visiting r, continues by traversing T1 in preorder, then T2 in preorder, and so on until Tn is traversed in preorder. 

TIPS :Visit root, visit subtrees left to right

Inorder Traversal

Let T be an ordered rooted tree with root r. If T consists only of r, then r is the inorder traversal of T. If T1, T2, …, Tn are subtrees at r from left to right in T, then the inorder traversal begins by traversing T1 in inorder, then visiting r, continues by traversing T2 in inorder, and so on until Tn is traversed in inorder.

TIPS : Visit leftmost subtree, Visit root, Visit other subtrees left to right.

Postorder Traversal

Let T be an ordered rooted tree with root r. If T consists only of r, then r is the postorder traversal of T. If T1, T2, …, Tn are subtrees at r from left to right in T, then the preorder traversal begins by traversing T1 in postorder, then T2 in postorder, and so on until Tn is traversed in postorder and ends by visiting r.

TIPS : Visit subtrees left to right, Visit root.

Exercise

Determine the order in which a preorder, inorder, and postorder traversal visits the vertices of the following rooted tree.

Represent Expression by Rooted Tree

We can represent complicated expression (propositions, sets, arithmetic) using ordered rooted trees.

Example: A binary tree representing ((x+y)↑2)+((x-4)/3)

Infix, Prefix & Postfix Notation

We obtain the Infix form of an expression when we traverse its rooted tree in Inorder. The infix form for expression ((x+y)↑2)+((x-4)/3) is x + y ↑2 + x – 4 / 3 or ((x+y)↑2)+((x-4)/3) 

We obtain the Prefix form of an expression when we traverse its rooted tree in Preorder. The prefix form for expression ((x+y)↑2)+((x-4)/3) is + ↑ + x y 2 / - x 4 3

We obtain the Postfix form of an expression when we traverse its rooted tree in Postorder. The postfix form for expression ((x+y)↑2)+((x-4)/3) is x y + 2 ↑ x 4 – 3 / + 

Evaluating Prefix Expression

Working right to left and performing operations using the operands on the right. Example: The value of the prefix expression + - * 2 3 5 / ↑ 2 3 4 is 3

Evaluating Postfix Expression

Working left to right and performing operations using the operands on the left. Example: The value of the postfix expression 7 2 3 * - 4 ↑ 9 3 / + is 4.

Exercise

1. Represent the following expression using binary trees. Then write these expression in infix, prefix and postfix notations. 

• ((x+2)↑3) * (y – (3+x)) – 5 
• (A ∩ B)  –  (A ∪ (B – A)) 

2. What is the value of these expression in prefix expression? 

• + – ↑3 2 ↑ 2 3 / 6 – 4 2 
• * + 3 + 3 ↑ 3 + 3 3 3 

3. What is the value of these expression in postfix expression? 

• 3 2 * 2 ↑ 5 3 – 8 4 / * – 
• 9 3 / 5 + 7 2 – *

Sumber

Slide StrukDis : Penelusuran Pohon