Data Structures and Agorithm: DS 14 Binary Expression Tree.pptx

Data Structures and Agorithm: DS 14 Binary Expression Tree.pptx

1. Data Structure Lecture No. 14 Binary Expression Tree Engr . Rashid Farid Chishti http://youtube.com/rfchishti http://sites.google.com/site/chishti International Islamic University H-10, Islamabad, Pakistan Video Lecture

2. Expression trees are binary trees for mathematical expression Leaves are operands (a, b, c, …) Other nodes are operators. (+, -, *, /) This is Expression Tree for ( a+b *c )+((d* e+f )*g ) Binary Expression Tree + + * b a c * + g f * d e

3. Preorder traversal : (node, left, right) gives Prefix Expression . + + a * b c * + * d e f g Expression Tree Traversal + + * b a c * + g f * d e

4. Inorder traversal : (left, node, right ) gives Infix Expression . a + b * c + d * e + f * g Expression Tree Traversal + + * b a c * + g f * d e

5. Postorder traversal : (left, right, node) gives Postfix Expression . a b c * + d e * f + g * + Expression Tree Traversal + + * b a c * + g f * d e

6. Read expression one symbol at a time If the symbol is an operand Create a one-node tree Push its pointer to a stack If the symbol is an operator Pop two pointers Form a new tree whose root is the operator In the end, the only element of the stack will be the root of an expression tree. Constructing a Binary Expression Tree from Postfix

7. a b + c d e + * * Constructing Expression Tree from Postfix Stack

8. a b + c d e + * * Constructing Expression Tree from Postfix Stack a

9. a b + c d e + * * Constructing Expression Tree from Postfix Stack a b

10. a b + c d e + * * Constructing Expression Tree from Postfix Stack b + a

11. a b + c d e + * * Constructing Expression Tree from Postfix Stack b + a c

12. a b + c d e + * * Constructing Expression Tree from Postfix Stack b + a c d

13. a b + c d e + * * Constructing Expression Tree from Postfix Stack b + a c d e

14. a b + c d e + * * Constructing Expression Tree from Postfix Stack b + a c e + d

15. a b + c d e + * * Constructing Expression Tree from Postfix Stack b + a * c e + d

16. a b + c d e + * * Constructing Expression Tree from Postfix Stack * * c e + d b * a

17. a b + c d e + * * Constructing Expression Tree from Postfix Stack * * c e + d b * a root

18. (1+2) * ((3*(4+5)) Evaluation of a Binary Expression Tree * * 3 5 + 4 2 + 1 root 3 9 27 81

19. #include < iostream > #include <string> #include < math.h > using namespace std ; struct Data{ char opr ; double num ; }; struct Tree_Node { Tree_Node * left ; Data data ; Tree_Node * right ; }; typedef Tree_Node * SType ; 19 Implementation of Binary Expression Tree struct Node{ SType info ; Node *next ; }; class Stack{ private : Node * head; public : Stack ( ); bool Is_Empty (); SType Top(); void Push ( SType Data ); SType Pop ( ); ~ Stack( ) ; }; Stack ::Stack( ){ head = NULL; } 1 2

20. bool Stack:: Is_Empty () { return head == NULL; } SType Stack::Top() { if ( ! Is_Empty () ) return head->info; return NULL; } void Stack :: Push ( SType Data ) { Node * newNode ; newNode = new Node ; if ( newNode == NULL ){ cout << endl << "Stack is full" ; return ; } newNode -> info = Data ; newNode -> next = head ; head = newNode ; } 20 Implementation of Binary Expression Tree SType Stack :: Pop( ) { if ( Is_Empty () ){ cout << "Stack is empty " ; return NULL ; } Node *current ; SType Data ; current = head ; Data = current -> info ; head = head -> next ; delete current ; return Data ; } Stack :: ~Stack( ){ Node *current ; while ( head != NULL ){ current = head ; head = head -> next ; delete head ; } } 3 4

21. class Binary_Expression_Tree { private : Stack St; Tree_Node * root; Tree_Node * t,*t1,*t2; void Pre_Order ( Tree_Node * ); void In_Order ( Tree_Node * ); void Post_Order ( Tree_Node * ); bool Is_Operator ( char c); Tree_Node * New_Tree_Node (Data d); double Evaluate ( Tree_Node * node); public : Binary_Expression_Tree (){root = NULL;}; Binary_Expression_Tree ( char Postfix[]); double Evaluate( ); void Pre_Order ( ); void In_Order ( ); void Post_Order ( ); }; 21 Implementation of Binary Expression Tree Tree_Node * Binary_Expression_Tree :: New_Tree_Node (Data d){ Tree_Node * temp = new Tree_Node ; temp- >left = NULL; temp- >right = NULL; temp- >data = d; return temp; }; bool Binary_Expression_Tree :: Is_Operator ( char c){ switch (c ){ case '+' : return true ; case '-' : return true ; case '*' : return true ; case '/' : return true ; case '^' : return true ; default : return false ; } return false ; } 5 6

22. Binary_Expression_Tree :: Binary_Expression_Tree ( char Postfix[]){ // Traverse through every character of // input expression for ( int i=0; Postfix[i]; i ++) { // ignore space and tab if ( Postfix[ i ] == ' ' || Postfix[ i ] == '\t' ) continue ; // If operand, simply push into stack if (! Is_Operator (Postfix[ i ])) { Data d; d.num = Postfix[ i ] - 0x30; d.opr = 0; t = New_Tree_Node (d); St.Push (t ); } 22 Implementation of Binary Expression Tree else { // operator Data d; d.num = 0; d.opr = Postfix[ i ]; t = New_Tree_Node (d); // Pop two top nodes t1 = St.Pop (); // Remove top t2 = St.Pop (); // make them children t- >right = t1; t- >left = t2; // Add this subexpression to stack St.Push (t ); } } // connect it with root pointer root = St.Pop (); } 7 8

23. double Binary_Expression_Tree :: Evaluate ( ) { return Evaluate(root); } double Binary_Expression_Tree :: Evaluate ( Tree_Node * node) { // empty tree if (node == NULL) return 0; // leaf node i.e, an integer if (node-> left == NULL && node- > right== NULL ) { return node-> data.num ; } 23 Implementation of Binary Expression Tree // Evaluate left subtree double l_val = Evaluate(node->left); // Evaluate right subtree double r_val = Evaluate(node->right); // Check which operator to apply if (node-> data.opr == '+' ) return l_val + r_val ; if (node-> data.opr == '-' ) return l_val-r_val ; if (node-> data.opr == '*' ) return l_val * r_val ; if (node-> data.opr == '/' ) return l_val / r_val ; if (node-> data.opr == '^' ) return pow( l_val,r_val ); return 0; } 9 10

24. void Binary_Expression_Tree :: Pre_Order (){ Pre_Order (root); } void Binary_Expression_Tree :: Pre_Order ( Tree_Node *node){ if (node != NULL){ if (node-> data.opr == 0) cout << node-> data.num << " " ; else cout << node-> data.opr << " " ; Pre_Order (node- >left); Pre_Order (node- >right); } } 24 Implementation of Binary Expression Tree void Binary_Expression_Tree :: In_Order ( ){ In_Order (root); } void Binary_Expression_Tree :: In_Order ( Tree_Node *node){ if (node != NULL){ In_Order (node- >left); if (node-> data.opr == 0) cout << node-> data.num << " " ; else cout << node-> data.opr << " " ; In_Order (node- >right); } } 11 12

25. void Binary_Expression_Tree :: Post_Order (){ Post_Order (root); } void Binary_Expression_Tree :: Post_Order ( Tree_Node *node){ if (node != NULL){ Post_Order (node- >left); Post_Order (node- >right); if (node-> data.opr == 0) cout << node-> data.num << " " ; else cout << node-> data.opr << " " ; } } 25 Implementation of Binary Expression Tree int main(){ Binary_Expression_Tree BET ( "1 2 + 3 4 5 + * *" ); cout << " -: Pre_Order Traversal:-\n" ; BET.Pre_Order (); cout << "\n\n -:In_Order Traversal:-\n" ; BET.In_Order (); cout << endl ; cout << "\n\n-:Post_Order Traversal:-\n" ; BET.Post_Order (); cout << endl ; cout << "Answer = " << BET.Evaluate (); cout << endl ; system ( "PAUSE " ); return 0; } 13 14

26. Program Output