Read an introductory reading assignment (Litvin pp.400-404).
- Vocabulary. Use the diagram of the hierarchical tree shown
on page 401 for the following:
- Which node is the root of the tree?
- How many leaves on this tree?
- How many nodes on level 2?
- What is the height(or depth) of the tree?
- How many children does "President" have?
- Is this a binary tree?
- Is the tree with root "VP Sales/Market" a binary tree?
- "Dir. Software" is the parent of what node?
- Name the ancestors of "Product Mgr".
Shape. Draw a binary tree with 4 levels so that each node (except the
last level) has two children.
- How many nodes does the tree contain?
- What is the smallest number of levels required to store 10,000 nodes in a binary tree?
- What advantage is there to organizing data in shallow trees such as these?
- What is the smallest and the largest possible number of leaves in a binary tree containing exactly six non-leaf nodes?
- Recursion. Why is a tree an inherently recursive structure?
- What does it mean to traverse a tree?
- If you follow the Traverse pseudocode on page 404, in what
order might you list the names in this tree?
- Applications. Trees are often used for representing
branching structures or processes such as
Continue to: Unit 8 / Prev / Next