Example: Expression Trees Figure 4.14 Expression tree for (a+b*c)+(d*e+f)* Leaves are operands (constants or variables) The internal nodes contain operators Will not be a binary tree if some operators are not binary
16 Example: Expression Trees Leaves are operands (constants or variables) The internal nodes contain operators Will not be a binary tree if some operators are not binary
Preorder postorder and inorder Preorder traversal node, left, right prefix expression D++a bc*+*defg Figure 4.14 Expression tree for(a +b*c)+((d*e+ f )*g)
17 Preorder, Postorder and Inorder Preorder traversal node, left, right prefix expression ++a*bc*+*defg
Preorder postorder and inorder Postorder traversal Inorder traversal left, right, node left, node, right postfix expression InfIX expression Cabc*+de°+g*+ a+b*c+de+fg C Figure 4.14 Expression tree for(a+b*c)+((d*e+ f)*g)
18 Preorder, Postorder and Inorder Postorder traversal left, right, node postfix expression abc*+de*f+g*+ Inorder traversal left, node, right infix expression a+b*c+d*e+f*g
Preorder postorder and inorder Pseudo code Algorithm Preorder(r) Algorithm Inorder Algorithm Postorder(a) Input: r is the root of a subtree Input: a is the root of a subtree. Input: a is the root of a subtree ULL 1.irx≠NULL 1.ic≠NULL 234 then output key(x then Inorder (left(a)); then Postorder (left(D); Preorder(left()); 3 output key (r); Postorder(right() Preorder(right(c)) Inorder (right(a)); output key(a);
19 Preorder, Postorder and Inorder Pseudo Code
Binary tree insertion and deletion
20 Binary tree insertion and deletion …