Part 1: HTML

Web pages are written in a language called HTML (hyper-text markup language), which models documents as trees. Nodes contain things like paragraphs, lists, titles, tables, images, etc.

HTML uses "tags" to show where nodes begin and end. A node starts with an opening tag: , and continues until it's closing tag: . Any tags within that opening/closing pair are children of that node.

Consider the following html document from page 236 of the textbook:

  
The Little Boat
  
 The storm tossed the little boat like a cheap sneaker in an old washing machine. The three drunken fishermen were used to such treatment, of course, but not the tree salesman, who even as a stowaway now felt that he had overpaid for the voyage. 
 
 
 Will the salesman die?
 
 What color is the boat? 
 
 And how about Naomi? 
 
 

Draw the tree specified by the HTML elements in this sample web page

Write the depth next to each node in your tree

Give 2 examples of sibling nodes

How many grandchildren does the "body" node have?

What is the height of the tree?

Part 2: Counting Nodes

Recall that some trees have a fixed, maximum branching factor. In this part of the assignment, you'll investigate the number of nodes in full trees of various heights and branching factors.

For branching factors 2, 3, and 4, draw a full tree of heights 0, 1, and 2. Count the number of nodes in each. Try to come up with a formula for the number of nodes in a full tree of height h, and branching factor, d.