CS111 Lab 14




BSTPowerPoint.ppt


Binary Trees


NOTES:
  1. A tree is an object made up of nodes linked together to form a nonlinear structure.
  2. A tree consists of nodes, or vertices, and a finite set of directed arc that connect pairs of nodes.
  3. Binary trees are trees in which each node has at most two children.

Part I: Intro to Binary Trees: Basic Construction and Traversals
Examine the Binary Tree in the figure below. Identify the errors and redraw the correct tree.





Part II: Binary Trees Traversals
NOTES:
      Binary Traversals determine the order in which the vertices of a binary tree will be visited.
      There are three types of traversals: inorder, preorder, and postorder.
      All three traversal algorithms are recursive and use the notation VLR: Visit root, Left subtree traversed, and Right subtree traversed.

      1. inorder traversal : LVR
        • L Traverse the left subtree
        • V Visit the root
        • R Traverse the right subtree
      2. preorder traversal algorithm: VLR
        • V Visit the root.
        • L if the left subtree is nonempty, do a preorder traversal of it.
        • R if the right subtree is nonempty, do a preorder traversal on it.
          Note that the preorder traversal of a binary tree can be obtained by circumnavigating the tree beginning at the root and visiting each node the first time it is encountered on the left.
      3. postorder traversal algorithm: LRV
        • L If the left subtree is nonempty, do a postorder traversal on it.
        • R If the right subtree is nonempty, do a postorder traversal on it.
        • V visit the root.
          Note that the preorder traversal visits the root first and the postorder traversal visits the root last.



Exercise: Determine the pre-order, in-order, and post-order traversals of the correct binary tree from Part I.




Part III: Binary Search Trees

For each of the following lists of numbers:
  1. 7, 3, 6, 4 ,5
  2. 3, 9, 4, 8, 6
  3. 2, 8, 6, 4, 5, 7, 3, 9




Part IV: A Balanced Binary Tree
  1. Why is a balanced binary tree important?
  2. Find the correct order to add integer nodes 1 through 15 to create a perfectly balanced binary tree. Identify this order.
  3. Draw the binary tree produced by exercise 1.
  4. Show the order of visiting the vertices inorder , preorder, and postorder.