My Notes

TREE ================================================================================ A  Tree  is a  non-linear data structure  and a hierarchy consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”). A tree consists of a root, and zero or more subtrees T 1 , T 2 , … , T k  such that there is an edge from the root of the tree to the root of each subtree. Basic Terminologies:   Parent Node:  The node which is a predecessor of a node is called the parent node of that node.  {B}  is the parent node of  {D, E} . Child Node:  The node which is the immediate successor of a node is called the child node of that node. Examples:  {D, E}  are the child nodes of  {B}. Root Node:  The topmost node of a tree or the node which does not have any parent node is called the root node. {A }  is the root node of the tree. A non-empty tree must contain exactly one root node and exactly one path from the root to all other no

    Prefix to Postfix conversion ================================================================================ Prefix expression:  The expression of the form operator a b (+ab). When an operator is prefix by every pair of operands. Postfix expression:  The expression of the form a b operator (ab+). When an operator is followed by every pair of operands. Algorithm: first we group the tokens from right to left all operators move at the end of the group eg. - + / A ^ B C * D E * A C Solution: - + / A ^ B C * D E * A C - + / A B C ^ D E * A C * - + A B C ^ / D E * A C * - A B C ^ / D E * + A C * A B C ^ / D E * + A C * -

  Prefix to Infix conversion ================================================================================ Infix expression:  The expression of the form a operator b (a + b). When an operator is in-between every pair of operands. Prefix expression:  The expression of the form operator a b (+ab). When an operator is prefix by every pair of operands. Algorithm :  first we group the tokens from right to left all operators move in between two operands eg. - + / A ^ B C * D E * A C Solution:  - + / A ^ B C * D E * A C - + / A B ^ C D * E A * C - + A / B ^ C D * E A * C - A / B ^ C + D * E A * C A / B ^ C + D * E - A * C

  Postfix to Infix conversion ================================================================================ Infix expression:  The expression of the form a operator b (a + b). When an operator is in-between every pair of operands. Postfix expression:  The expression of the form a b operator (ab+). When an operator is followed by every pair of operands. Algorithm: first we group the token from left to right all operators move  in between two operands eg. A B + C D - * E / Solution:  A B + C D - * E / A + B C - D * E / A + B * C - D E / A + B * C - D / E

      Postfix to Prefix conversion ================================================================================ Postfix expression:  The expression of the form a b operator (ab+). When an operator is followed by every pair of operands. Prefix expression:  The expression of the form operator a b (+ab). When an operator is prefix by every pair of operands. Algorithm: first we group the tokens from left to right all operators move at the beginning of group eg . A B C ^ / D E * + A C * - Solution:  A B C ^  / D E * + A C * - A ^ B C / * D E + * A C - / A ^ B C * D E + * A C - + / A ^ B C * D E * A C - - + A ^ B C * D E * A C

    Infix to Postfix conversion ================================================================================ Infix expression:  The expression of the form a operator b (a + b). When an operator is in-between every pair of operands. Postfix expression:  The expression of the form a b operator (ab+). When an operator is followed by every pair of operands. Algorithm: begin x = read  first  symbol from infix if ( x is '(' or ')' ) if (x is '(' ) push (x) end if if (x is ')' ) pop() everything from stack and send to output till we get first '('  parenthesis  but '(' not send to output end if end if if (x is operator) if (operator[TOP] < current (x) operator) push (x) i.e. push current operator on stack end if if ( operator[TOP] > current (x) operator) pop(TOP operator) and send to output and push (current x) operator on the stack end if if (TOP == -1) push(x) end if end if x = read next symbol go to step 3 print output string end eg.

  Infix to Prefix conversion ================================================================================ Infix expression:  The expression of the form a operator b (a + b). When an operator is in-between every pair of operands. Prefix expression:  The expression of the form operator a b (+ab). When an operator is prefix by every pair of operands. Algorithm: begin first reverse the infix expression replace the parenthesis  as every "(" as ")" and every ")" as "(" convert the modified expression to postfix by using infix to postfix algorithm reverse the final postfix string to get the resulted prefix expression eg. (A + B ^ C) * D + E ^ S Solution: S ^ E + D * ) C ^ B + A ( S ^ E + D * ( C ^ B + A ) Input Stack Output S S ^ S E S E + S E ^ D S E ^ D *