Pertemuan ke-4 - Binary tree and expression - 2101640795 - Michael Kesta


Binary Tree

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set.[1] Some authors allow the binary tree to be the empty set as well.
Types of binary tree
·         A rooted
·         A full binary tree
·         A perfect binary tree
·         In a complete binary tree every level
·         In the infinite complete binary tree
·         A balanced binary tree
·         A degenerate (or pathological) tree
https://upload.wikimedia.org/wikipedia/commons/thumb/b/b0/Full_binary.svg/220px-Full_binary.svg.pngFull binary tree

https://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Complete_binary.svg/220px-Complete_binary.svg.pngComplete binary tree





Binary Expression tree

A binary expression tree is a specific kind of a binary tree used to represent expressions. Two common types of expressions that a binary expression tree can represent are algebraic[1] and boolean. These trees can represent expressions that contain both unary and binary operators.

Traversal

An algebraic expression can be produced from a binary expression tree by recursively producing a parenthesized left expression, then printing out the operator at the root, and finally recursively producing a parenthesized right expression. This general strategy (left, node, right) is known as an in-order traversal. An alternate traversal strategy is to recursively print out the left subtree, the right subtree, and then the operator. This traversal strategy is generally known as post-order traversal. A third strategy is to print out the operator first and then recursively print out the left and right subtree known as pre-order traversal.

Infix traversal

When an infix expression is printed, an opening and closing parenthesis must be added at the beginning and ending of each expression. As every subtree represents a subexpression, an opening parenthesis is printed at its start and the closing parenthesis is printed after processing all of its children.
Pseudocode:
Algorithm infix (tree)
/*Print the infix expression for an expression tree.
 Pre : tree is a pointer to an expression tree
 Post: the infix expression has been printed*/
 if (tree not empty)
    if (tree token is operator)
       print (open parenthesis)
    end if
    infix (tree left subtree)
    print (tree token)
    infix (tree right subtree)
    if (tree token is operator)
       print (close parenthesis)
    end if
 end if
end infix

Postfix traversal

The postfix expression is formed by the basic postorder traversal of any binary tree. It does not require parentheses.
Pseudocode:
Algorithm postfix (tree)
/*Print the postfix expression for an expression tree.
 Pre : tree is a pointer to an expression tree
 Post: the postfix expression has been printed*/
 if (tree not empty)
    postfix (tree left subtree)
    postfix (tree right subtree)
    print (tree token)
 end if
end postfix

Prefix traversal

The prefix expression formed by prefix traversal uses the standard pre-order tree traversal. No parentheses are necessary.
Pseudocode:
Algorithm prefix (tree)
/*Print the prefix expression for an expression tree.
 Pre : tree is a pointer to an expression tree
 Post: the prefix expression has been printed*/
 if (tree not empty)
    print (tree token)
    prefix (tree left subtree)
    prefix (tree right subtree)
 end if
end prefix




Komentar

Posting Komentar

Postingan populer dari blog ini

pertemuan ke-2 - Single Link List - 2101640795 - Michael Kesta

Gambar
Single Linked List Single linked list is a sequence of elements in which every element has link to its next element in the sequence . In any single linked list, the individual element is called as  "Node" . Every  "Node"  contains two fields,  data  and  next . The  data  field is used to store actual value of that node and next field is used to store the address of the next node in the sequence. Example: Operation In a single linked list we perform the following operations... Insertion Deletion Display Before we implement actual operations, first we need to setup empty list. First perform the following steps before implementing actual operations. Step 1:  Include all the  header files  which are used in the program. Step 2:  Declare all the  user defined  functions. Step 3:  Define a  Node  structure with two members  data  and  next Step 4:  Define a Node pointer ' head ' and set it to  NULL . Step 4:  Implemen
Baca selengkapnya

Pertemuan ke-3 - Link List Implementation - 2101640795 - Michael Kesta

Infix, Postfix and Prefix Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions. It is easiest to demonstrate the differences by looking at examples of operators that take two operands. Infix notation: X + Y Operators are written in-between their operands. This is the usual way we write expressions. An expression such as  A * ( B + C ) / D  is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer." Postfix notation (also known as "Reverse Polish notation"): X Y + Operators are written after their operands. The infix expression given above is equivalent to  A B C + * D / The order of evaluation of operators is always left-to-right, and brackets cannot be used to change this order. Because the "+" is to the left of the "*" in the example above, the addition must be performed before the multiplication.
Baca selengkapnya