1. Answer the following queations about the rooted tree below: a) Which vertex i
ID: 3148835 • Letter: 1
Question
1. Answer the following queations about the rooted tree below: a) Which vertex in the root? b) Which vertices are internal? c) Which vertices are leaves? d) Which vertices are children of vertex f e) Which vertices are parents of vertex f? f) Which vertices are siblings of vertex f? g) Which vertices are ancestors of vertex f? 9 h) Which vertices are descendants of vertex f? Tn T. i) What is the level of vertex f? j) Is the tree a full binary tree? Explain. 2. a) Build a binary search tree for the words Delaware, Indiana, Ohio, Virginia, Colorado, yoming, Alabama, Texas, Oregon using alphabetical order. b) Construct the binary tree with prefix codes representing the coding scheme a:00, e:01, n:101, r:100, s: 110, t:111 3. Use Huffman coding to encode the following symbols with the frequencies listed: A: 0.10, B: 0.12, C: 0.18 D: 0.20, E 0.25, F 0.15. What is the average number of bits used to encode a character? (over)Explanation / Answer
Hi,
It is against chegg policy to post multiple questions as one, please post other questions as separate questions,answering the first one as per policy
1.
a. Root is the top most element from which every element is derived, so it is a in the given tree
b. Internal vertices are the ones that have children, so in the given tree internal vertices would be - a,b,c,f,g,h,k
c. leaf nodes are the ones that DO NOT have children, so in the given tree internal vertices would be - d,e,l,m,n,i,j
d. children vertices are the ones that are directly one level down to the parent therefore children of f would be h,i
e. parents of a vertex are the direct nodes above one level on the same path, therefore parents of f would be c
f. siblings of a vertex is the vertex, which shares the same parent, that means sibling of f would be the ones with same parent as f which is c therefore siblings would be g
g.ancestor vertices are the parents that lead all the way to the root, therefore ancestors of f would be c,a
h.descendant vertices are the vertices that are either the child or or is (recursively) the descendant of any of the children of the given vertex therefore descendants of f would be h,i,l,m
i. level of a vertex is desgined as starting with 0 at root and incrementing 1 at each subsequent children, therefore level of f would be 2
j.A full binary tree is the one in which every node other than the leaves has two children. here the vertex k has only one children, there fore its not a full binary tree
Thumbs up if this was helpful, otherwise let me know in comments
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.