EX4

 

 

  1. Consider the tree above. Tell what is described by each of the following phrases:
    1. The root of the tree
    2. The leaves of the tree
    3. The interior nodes of the tree
    4. The siblings of node 6
    5. The subtree with root 5
    6. The ancestors of node 10
    7. The descendants of node 10
    8. The nodes to the left of node 10
    9. The nodes to the right of node 10
    10. The longest path in the tree
    11. The height of node 3
    12. The depth of node 13
    13. The height of the tree
  2. For each node in the tree above indicate the leftmost child and the right sibling
  3. Represent the tree above using leftmost-child right sibling references (draw boxes with arrows).
  4. Can a leaf in a tree ever have any
    1. Descendants?
    2. Proper descendants?
  5. Suppose we have a graph consisting of four nodes, r, a, b, and c. Node r is an isolated node and has no edges connecting to it. The remaining three nodes form a cycle; that is, we have an edge connecting a and b, and edge connecting b and c, and an edge connecting c and d. Why is this graph not a tree?
  6. Give expression trees for the following expressions.
    1. (x + 1) *(x-y+4)
    2. 1+2+3+4+5+6
    3. 9*8+7*6+5