Chapter 12 Outcomes
Trees

After completing this chapter and participating in class, you should be able to accomplish each of the following outcomes.

Knowledge Outcomes

  1. Define each of the key terms listed in the chart below.

    2. binary tree node left & right subtrees
    root ordered binary tree binary search tree
    balanced tree search space leaf node
    heap child node parent node
    inorder traversal preorder traversal depth of a binary
    search tree
    height of a node    

  2. Describe the structure of a binary tree. Include relevant terms such as node, left and right subtree, and root (12.1).

  3. State the definition of an ordered binary tree (or a binary search tree) (12.1).

  4. Explain how a binary tree is searched (12.1).

  5. Describe how the RecursiveDisplay procedure accomplishes its task (12.2).

  6. State the relationship of the parent and child nodes in a heap (12.3).

  7. Describe the arithmetic relationship between children and parent nodes in a heap that is implemented as an array (12.3).

  8. Explain how the removeLargest procedure removes the next largest element from the heap and then restores the heap property (12.3).

  9. Describe how final storage of the sorted numbers is combined with the heap array to produce a sorted array (12.3).

  10. Discuss the efficiency of the heap sort algorithm in big O notation (12.1 - 12.3).

Skills Outcomes

  1. Trace the Enter procedure in the "treescl.tu" class and explain how this algorithm inserts new items into their correctly ordered position (use diagrams where necessary) (12.2).

  2. Using an array, rearrange a list of unordered numbers (or words) into its correct order by tracing through the insertHeap procedure (12.3).