8.3 Lab: BT – Traversals (in-, post-, and pre-Order)

This program builds a Binary Tree of random integers and displays the tree in inorder.

Note The insert() function is specific to this exercise

The main goal of this example is build a binary tree that could be used to test the binary tree traversals and other binary tree functions.

Implement the postorder and preorder traversals.

Note: For each traversal there are two functions:

• a recursive private function that traverses the binary tree: because it needs the root as a parameter, it cannot be called outside of the class, therefore it has to be declared private
• a public function (the wrapper) that calls the private traversal

Naming conventions: usually private member functions’ names begin with ‘_’

inOrder()   calls _inOrder()postOrder() calls _postOrder()preOrder()  calls _preOrder(

8.4 Lab: BT – Traversals (in-, post-, and pre-Order) – Version 2

This program builds a Binary Tree of random integers and displays the tree in inorder.

Our final goal is to write binary tree and binary search tree ADTs. We’ve seen one way to deal with traversal in the Doubly-Linked-List ADT assignment: overload the stream insertion operator. This gives us only one way of formatting the output. The approach that we will use with trees is a more flexible approach that gives us more formatting options, but requires the use of function pointers.

This assignment gives you an example of how function pointers can be used to write ADTs. You will learn more about this topic in an Advanced C/C++ class.

The inorder traversal functions have been changed from:

void inOrder() const;void _inOrder(Node *root) const;

to:

void inOrder( void visit(const Data &) ) const;void _inOrder(Node *root, void visit(const Data &) ) const;

The parameter that has been added to both function:

void visit(const Data &)

looks like a function’s prototype declaration, but it represents a function parameter (or a function pointer). The name of a function represents an address (pointer constant), and this is a value that we can pass to other functions.

Review the inorder traversal and implement the postorder and preorder traversals using function pointers.

8.13 Lab: BT <— BST (Traversals)

Review Inheritance (A search tree is a binary tree)

In this assignment we will rewrite the Binary Tree class as a parent class for the Binary Search Tree class. The tree node is also a class.

The assignment consists of the following classes/files:

• BinaryNode.h (template, given)
• BinaryTree.h (template, incomplete)
• BinarySearchTree.h(template, incomplete)
• main.cpp (incomplete)

The program creates a BST of random integers. The insert and inorder traversal are given.

Write the following functions:

• postorder traversal
• preorder traversal

8.14 Lab: BT <— BST (Smallest/Largest)

The assignment consists of the following classes/files:

• BinaryNode.h (template, given)
• BinaryTree.h (template, incomplete)
• BinarySearchTree.h(template, incomplete)
• main.cpp (incomplete)

Write the following functions:

• findSmallest (recursive)
• findLargest (recursive)

8.15 Lab: BT <— BST (Indented Tree)

Review Inheritance (A search tree is a binary tree)

In this assignment we will rewrite the Binary Tree class as a parent class for the Binary Search Tree class. The tree node is also a class.

The assignment consists of the following classes/files:

• BinaryNode.h (template, given)
• BinaryTree.h (template, incomplete)
• BinarySearchTree.h(template, incomplete)
• main.cpp (incomplete)

The program creates a BST of random integers. The insert and inorder traversal are given.

Write a variation of one of the Depth-First Traversal Functions named printTree that displays the indented tree, including the level numbers.

If the three has 3 nodes: 27, 25, and 30:

   27 /    25     30

the indented tree will be displayed as shown below:

1). 27..2). 30 

..2). 25

8.16 Lab: BT <— BST (Search)

In this assignment we will rewrite the Binary Tree class as a parent class for the Binary Search Tree class. The tree node is also a class.

The assignment consists of the following classes/files:

• BinaryNode.h (template, given)
• BinaryTree.h (template, incomplete)
• BinarySearchTree.h(template, incomplete)
• main.cpp (incomplete)

The program creates a BST of random integers. The insert and inorder traversal are given.

Implement the pair of search functions for searching the BST:

• _search – recursive (private function)
• search – wrapper for _search (public function)