Explain how many vertices would need to be added to each

Question

Part 1: Refer to Figure HW 7for problems 1-5.

1) List all of the following:

a) Level-2 vertices
b) Leaves
c) Siblings of v6
d) Descendants of v6

2) Is this an n-tree? If so, for what integer n?

3) Explain how many vertices would need to be added to each existing vertex to create a complete 3-tree. For example, writing "v0: 2" would mean that two vertices need to be added to the existing v0 vertex. Writing "v0: 0" would mean that no vertices need to be added to the existing v0 vertex.

v₀:                    v₁:                    v₂:                    v₃:

v₄:                    v₅:                    v₆:                    v₇:

v₈:                    v₉:                    v₁₀:                  v₁₁:

4) Compute the tree T(v3).

5) Give the height of each tree:

a) (T, v0)
b) T(v3)

Part 2:

1) Construct the tree of the algebraic expression:

((x-2)+3)/((2-(3+y))x(w-8))

Refer to the following Huffman code tree for problems 2 and 3:

2) Decode the message: 000110000101

3) Find the string that represents the word SEAT.

Part 3:

Here, to visit a node means to print the contents of the node. Refer to the tree that you constructed in section 7.2 homework problem 1 (above) to complete problems 1-3 below.

1) Show the results of performing a preorder search.

2) Show the results of performing an inorder search.
3) Show the results of performing a postorder search.

4) Draw the digraph of the binary positional tree that corresponds to Figure HW 7 from section 7.1 of this homework assignment.Below are images you can use to create the diagraph. You may copy/paste the arrow and alter the directions and length as needed.

Part 4:

Refer to this figure for problems 1 and 2.

1) Use vertex A as the initial vertex and use Prim's algorithm to find a minimal spanning tree. You do not need to draw the tree, but do list the edges (as an ordered pair) in the order in which they are chosen.

2) Use Kruskal's algorithm to find a minimal spanning tree. You do not need to draw the tree, but do list the edges (as an ordered pair) in the order in which they are chosen.