Wyo Data Structures - Ch. 6 Notes

Objective #1: Be able to write recursive functions that are used with binary trees.

• You must be able to write recursive functions that can be used with binary trees since Btrees are recursive data structures.
  
  
• Examples:
  

  int treeSum(node * tree)
  // returns the number of internal nodes in the Btree that has tree as its root

  bool isLeaf(node * myNode)
  // non-recursive function that returns true if myNode is a leaf, false otherwise

  int treeDepth(node * tree)
  // returns the depth of the tree which has tree as its root

  int internalPathLength(node * tree)
  // returns the internal path length of the tree which has tree as its root

  int externalPathLength(node * tree)
  // returns the external path length of the tree which has tree as its root