Judul : Struktur Diskret : Penelusuran Pohon, dan Ekspresi Infix, Prefix, dan Postfix
link : Struktur Diskret : Penelusuran Pohon, dan Ekspresi Infix, Prefix, dan Postfix
Struktur Diskret : Penelusuran Pohon, dan Ekspresi Infix, Prefix, dan Postfix
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
Demikianlah Artikel Struktur Diskret : Penelusuran Pohon, dan Ekspresi Infix, Prefix, dan Postfix
Sekianlah artikel Struktur Diskret : Penelusuran Pohon, dan Ekspresi Infix, Prefix, dan Postfix kali ini, mudah-mudahan bisa memberi manfaat untuk anda semua. baiklah, sampai jumpa di postingan artikel lainnya.
Anda sekarang membaca artikel Struktur Diskret : Penelusuran Pohon, dan Ekspresi Infix, Prefix, dan Postfix dengan alamat link https://duniaschools.blogspot.com/2019/10/struktur-diskret-penelusuran-pohon-dan.html
0 Response to "Struktur Diskret : Penelusuran Pohon, dan Ekspresi Infix, Prefix, dan Postfix "
Post a Comment