A tree is an object made up of nodes linked together to form a nonlinear structure.
A tree consists of nodes, or vertices, and a finite set of directed arc that connect pairs of nodes.
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.
inorder traversal : LVR
L Traverse the left subtree
V Visit the root
R Traverse the right subtree
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.
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:
Draw the binary search tree that is constructed when the numbersare inserted in the order given.
Perform inorder, preorder, and postorder traversals of the tree, and show the sequence of numbersthat results in each case.
7, 3, 6, 4 ,5
3, 9, 4, 8, 6
2, 8, 6, 4, 5, 7, 3, 9
Part IV: A Balanced Binary Tree
Why is a balanced binary tree important?
Find the correct order to add integer nodes 1 through 15 to create a perfectly balanced binary tree. Identify this order.
Draw the binary tree produced by exercise 1.
Show the order of visiting the vertices inorder , preorder, and postorder.