1. Give the sequence of letters from these traversals of the tree q / | \\ e f r
ID: 3672477 • Letter: 1
Question
1. Give the sequence of letters from these traversals of the tree
q
/ |
e f r
/ | /| |
d n g h j s t
a.) a preorder traversal
b.) a postorder traversal
2. Use the stack-based algorithm for converting a postfix expression into an expression tree for the postfix expression: abc*+ghk+m*/* Illustrate each step.
3. Use your expression tree to find the expression in prefix notation.
4. Draw an AVL tree for the following values inserted in this order. Illustrate each rotation that occurs: 83 12 62 55 32 68 74
5. Draw an AVL tree for the following values inserted in this order. Illustrate each rotation that occurs: 50 26 65 13 16 28 11 20 52 35 30
6. For the splay tree shown below, show how an access of node 55 is performed. Illustrate each operation that occurs:
10
20
/
15 30
/
25 40
/
35 50
60
/
55
7. For the splay tree shown below, show how an access of node 40 is performed. Illustrate each operation that occurs:
90
/
30 95
/
20 70
/ /
10 60 80
/
45
/
40 50
8. For the B+-tree where M=3 and L=5 shown below, show how an insert of value 80 is handled.
| | 12 | | 50 | |
/ |
/ |
2 12 50
5 18 65
7 20 70
9 21 72
10 24 78
9. For the B+-tree where M=3 and L=5 shown below, show how an insert of value 77 is handled. Use the method of splitting the node rather than redistributing between siblings.
| | 24 | | 75 | |
/ |
/ |
/ |
| | 10 | | 16 | | | | 41 | | 50 | | | | 84 | | 90 | |
| / / | |
/ | | | | | | |
2 10 16 24 41 50 75 84 90
5 11 18 26 42 65 78 86 92
7 14 20 30 45 70 79 87 93
9 47 72 80
81
Explanation / Answer
1
From above figure the preorder and post order as follows:
The preorder traversal : the root of T followed by the nodes of T1 in preorder, the nodes of T2 in preorder traversal., and so on followed by Td in preorder
The post order traversal : the nodes of T1 in post order, followed by T2,….Td in post order, followed by the root.
a) Pre order: qednfgnjrst
1b) Post order: dnegnjfstrq
2. postfix expression: abc*+ghk+m*/*
Steps
3. Expression tree is shown below
The leaves of an expression tree are operands, such as constants or variables names, and the other nodes contain operators. This particular tree happens to be binary, because all of the operations are binary, and although thus is the simplest case, it is possible for nodes to have more than two children.
Prefix notation for the above expression tree is + + p * q r * + * s t u v
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.