Solve the following problems: 1. (Carrano, 2012) Chapter 15 Solve Questions 1-8 p. 428. 2. (Rossen)...

Transcribed Image Text:

Solve the following problems: 1. (Carrano, 2012) Chapter 15 Solve Questions 1-8 p. 428. 2. (Rossen) Problem 16, 17,18,19. p. 784 16. a) Represent the expression (y-(3+x)) -5 using a binary tree. Write this expression in b) prefix notation. c) postfix notation. d) infix notation. 17. a) Represent the expressions (x + xy) + (x/y) and x + ((xy + x)/y) using binary trees. Write these expressions in b) prefix notation. c) postfix notation. d) infix notation. ((x+2) 3) * 18. a) Represent the compound propositions (p ^ q) (pv-g) and (p^ (gp)) Vg using or- dered rooted trees. Write these expressions in b) prefix notation. c) postfix notation. d) infix notation. 19. a) Represent (AB)-(AU (B-A)) using an or- dered rooted tree. Write this expression in b) prefix notation. c) postfix notation. d) infix notation. a. Represent the arithmetic expression with a Binary Tree. b. Apply the preorder, inorder, and postorder transversals at each binary tree obtained. It would help if you got the infix, prefix, and postfix expressions. c. Verify each prefix and postfix expression (b) with the grammar defined in your textbook 1.5.2.2 Prefi x Expressions 166 11.5.2.3 Postfix Expressions 170 3. Design a binary tree in code C++ for each arithmetic expression. Show preorder, inorder, and postorder traversals only for problems 16 and 17 (2). 4. The solution must contain the following: a. C ++ Code. b. Code execution. c. The problems must show the Question, Binary tree diagram, and Answer. 5.2.2 Prefix Expressions A grammar that defines the language of all prefix expressions is = | = + |-|* |/ = a b...z 5.2.3 Postfix Expressions A grammar that defines the language of all postfix expressions is = | = + |-|*|/ = a b... z EXERCISES 1. Consider the tree in Figure 15-18. What node or nodes are a. The tree's root? b. Parents? c. Children of the parents in part b? d. Siblings? e. Ancestors of 50? f. Descendants of 20? g. Leaves? 2. What is the height of the tree in Figure 15-18? 3. Write preconditions and postconditions for the ADT binary search tree operations. FIGURE 15-18 A tree for Exercises 1, 2, 6, 7, 11, and 23 (10 (30) (50) 4. What are the preorder, inorder, and postorder traversals of the binary tree in Figure 15-19? 5. Consider a method is Leaf that returns true if a binary tree is a one-node tree that is, if it consists of only a leaf and returns false otherwise. a. Specify the method is Leaf. b. If isLeaf were not a method of a class of binary trees, would a client of the class be able to implement isLeaf? Explain. 6. Starting with an empty binary search tree, in what order should you insert items to get the binary search tree in Figure 15-18? 7. Using the binary search tree in Figure 15-18, trace the search algorithm when it searches for a. 30 b. 15 In each case, list the nodes in the order in which the search visits them. 8. Is the tree in Figure 15-19 a binary search tree? Explain. Solve the following problems: 1. (Carrano, 2012) Chapter 15 Solve Questions 1-8 p. 428. 2. (Rossen) Problem 16, 17,18,19. p. 784 16. a) Represent the expression (y-(3+x)) -5 using a binary tree. Write this expression in b) prefix notation. c) postfix notation. d) infix notation. 17. a) Represent the expressions (x + xy) + (x/y) and x + ((xy + x)/y) using binary trees. Write these expressions in b) prefix notation. c) postfix notation. d) infix notation. ((x+2) 3) * 18. a) Represent the compound propositions (p ^ q) (pv-g) and (p^ (gp)) Vg using or- dered rooted trees. Write these expressions in b) prefix notation. c) postfix notation. d) infix notation. 19. a) Represent (AB)-(AU (B-A)) using an or- dered rooted tree. Write this expression in b) prefix notation. c) postfix notation. d) infix notation. a. Represent the arithmetic expression with a Binary Tree. b. Apply the preorder, inorder, and postorder transversals at each binary tree obtained. It would help if you got the infix, prefix, and postfix expressions. c. Verify each prefix and postfix expression (b) with the grammar defined in your textbook 1.5.2.2 Prefi x Expressions 166 11.5.2.3 Postfix Expressions 170 3. Design a binary tree in code C++ for each arithmetic expression. Show preorder, inorder, and postorder traversals only for problems 16 and 17 (2). 4. The solution must contain the following: a. C ++ Code. b. Code execution. c. The problems must show the Question, Binary tree diagram, and Answer. 5.2.2 Prefix Expressions A grammar that defines the language of all prefix expressions is = | = + |-|* |/ = a b...z 5.2.3 Postfix Expressions A grammar that defines the language of all postfix expressions is = | = + |-|*|/ = a b... z EXERCISES 1. Consider the tree in Figure 15-18. What node or nodes are a. The tree's root? b. Parents? c. Children of the parents in part b? d. Siblings? e. Ancestors of 50? f. Descendants of 20? g. Leaves? 2. What is the height of the tree in Figure 15-18? 3. Write preconditions and postconditions for the ADT binary search tree operations. FIGURE 15-18 A tree for Exercises 1, 2, 6, 7, 11, and 23 (10 (30) (50) 4. What are the preorder, inorder, and postorder traversals of the binary tree in Figure 15-19? 5. Consider a method is Leaf that returns true if a binary tree is a one-node tree that is, if it consists of only a leaf and returns false otherwise. a. Specify the method is Leaf. b. If isLeaf were not a method of a class of binary trees, would a client of the class be able to implement isLeaf? Explain. 6. Starting with an empty binary search tree, in what order should you insert items to get the binary search tree in Figure 15-18? 7. Using the binary search tree in Figure 15-18, trace the search algorithm when it searches for a. 30 b. 15 In each case, list the nodes in the order in which the search visits them. 8. Is the tree in Figure 15-19 a binary search tree? Explain.