Lab 7: Trees part 2
Exercise 1 Revising the Animal Guessing Program
Problem statement:
Revise the animal guessing program from Figure 10.9 on page 492 of your text so that the initial knowledge tree is obtained by reading information from a file. Also, when the program ends, the knowledge tree at that point is written to the same file. You must carefully specify the format of the data in this file.
Learning Objectives:
The learner will be able to:
- Modify an existing program to read a file and set the initial tree structure.
- Modify an existing program to write a tree structure to a file, using some kind of traversal.
Exercise 2 Binary Search Trees
Problem statement:
Binary search trees have their best performance when they are balanced, which means that at each node, n, the size of the left subtree of n is within one of the size of the right subtree of n.
Write a function that takes a sorted link list of entries and produces a balanced binary search tree. If useful, you may add extra parameters to the procedure, such as the total number of entries in the list.
Learning Objectives:
The learner will be able to:
Write a function that takes a sorted link list of entries and produces a balanced binary search tree.
Equipment:
Typical Computer Lab setup
Components/Materials:
Microsoft Visual C++
Classroom Configuration:
N/A
Lab Procedures:
Complete the following tasks:Exercise 11.Modify the animal guessing program from Figure 10.9 on page 492 of your text so that the knowledge tree is obtained by reading a file and setting the initial tree structure.
2.Write the knowledge tree back to the file, using some kind of traversal.
Complete the following tasks: Exercise 2
- Build the left subtree of the root.
- Build the right subtree of the root.
- Put the pieces together with the join function from Self-Test Exercise 26 on page 526 of your text.
4.Think recursively!
Validation/Evaluation
Answers to Lab Exercises
Solutions to Lab Exercises can be found at the Curriculum Knowledge Network (CKN) section of the ITT Technical Institute Employee Portal, The solutions are also listed below.
Exercise 1
// FILE: animal.cpp// An animal-guessing program to illustrate the use of the binary tree toolkit.
#include <cstdlib> // Provides EXIT_SUCCESS
#include <iostream> // Provides cout
#include <string> // Provides string class
#include "bintree.h" // Provides the binary tree node functions
#include "useful.h" // Provides eat_line, inquire (from Appendix I)
using namespace std;
using namespace main_savitch_10;
// PROTOTYPES for functions used by this game program:
void ask_and_move(binary_tree_node<string>*& current_ptr);
// Precondition: current_ptr points to a non-leaf node in a binary taxonomy tree.
// Postcondition: The question at the current node has been asked. The current
// pointer has been shifted left (if the user answered yes) or right
// (for a no answer).
binary_tree_node<string>* beginning_tree( );
// Postcondition: The function has created a small taxonomy tree. The return
// value is the root pointer of the new tree.
void instruct( );
// Postcondition: Instructions for playing the game have been printed to the
// screen.
void learn(binary_tree_node<string>*& leaf_ptr);
// Precondition: leaf_ptr is a pointer to a leaf in a taxonomy tree. The leaf
// contains a wrong guess that was just made.
// Postcondition: Information has been elicited from the user, and the tree has
// been improved.
void play(binary_tree_node<string>* current_ptr);
// Precondition: current_ptr points to the root of a binary taxonomy tree with
// at least two leaves.
// Postcondition: One round of the animal game has been played, and maybe the
// tree has been improved.
int main( )
{
binary_tree_node<string> *taxonomy_root_ptr;
instruct( );
taxonomy_root_ptr = beginning_tree( );
do
play(taxonomy_root_ptr);
while (inquire("Shall we play again?"));
cout < "Thank you for teaching me a thing or two." < endl;
return EXIT_SUCCESS;
}
void ask_and_move(binary_tree_node<string>*& current_ptr)
// Library facilities used: bintree.h, string, useful.h
{
cout < current_ptr->data( );
if (inquire(" Please answer:"))
current_ptr = current_ptr->left( );
else
current_ptr = current_ptr->right( );
}
binary_tree_node<string>* beginning_tree( )
// Library facilities used: bintree.h, string
{
binary_tree_node<string> *root_ptr;
binary_tree_node<string> *child_ptr;
const string root_question("Are you a mammal?");
const string left_question("Are you bigger than a cat?");
const string right_question("Do you live underwater?");
const string animal1("Kangaroo");
const string animal2("Mouse");
const string animal3("Trout");
const string animal4("Robin");
// Create the root node with the question “Are you a mammal?”
root_ptr = new binary_tree_node<string>(root_question);
// Create and attach the left subtree.
child_ptr = new binary_tree_node<string>(left_question);
child_ptr->set_left( new binary_tree_node<string>(animal1) );
child_ptr->set_right( new binary_tree_node<string>(animal2) );
root_ptr->set_left(child_ptr);
// Create and attach the right subtree.
child_ptr = new binary_tree_node<string>(right_question);
child_ptr->set_left( new binary_tree_node<string>(animal3) );
child_ptr->set_right( new binary_tree_node<string>(animal4) );
root_ptr->set_right(child_ptr);
return root_ptr;
}
void instruct( )
// Library facilities used: iostream
{
cout < "Let's play!" < endl;
cout < "You pretend to be an animal, and I try to guess what you are.\n";
}
void learn(binary_tree_node<string>*& leaf_ptr)
// Library facilities used: bintree.h, iostream, string, useful.h
{
string guess_animal; // The animal that was just guessed
string correct_animal; // The animal that the user was thinking of
string new_question; // A question to distinguish the two animals
// Set strings for the guessed animal, correct animal and a new question.
guess_animal = leaf_ptr->data( );
cout < "I give up. What are you? " < endl;
getline(cin, correct_animal);
cout < "Please type a yes/no question that will distinguish a" < endl;
cout < correct_animal < " from a " < guess_animal < "." < endl;
cout < "Your question: " < endl;
getline(cin, new_question);
// Put the new question in the current node, and add two new children.
leaf_ptr->set_data(new_question);
cout < "As a " < correct_animal < ", " < new_question < endl;
if (inquire("Please answer"))
{
leaf_ptr->set_left( new binary_tree_node<string> (correct_animal) );
leaf_ptr->set_right( new binary_tree_node<string> (guess_animal) );
}
else
{
leaf_ptr->set_left( new binary_tree_node<string> (guess_animal) );
leaf_ptr->set_right( new binary_tree_node<string> (correct_animal) );
}
}
void play(binary_tree_node<string>* current_ptr)
// Library facilities used: bintree.h, iostream, string, useful.h
{
cout < "Think of an animal, then press the return key.";
eat_line( );
while (!current_ptr->is_leaf( ))
ask_and_move(current_ptr);
cout < ("My guess is " + current_ptr->data( ) + ". ");
if (!inquire("Am I right?"))
learn(current_ptr);
else
cout < "I knew it all along!" < endl;
}
Exercise 2
// FILE: bintree.h (part of the namespace main_savitch_10)// From Chapter 10 of Data Structures and Other Objects (Third Edition)
// ______
//
// This file has been modified to work with Microsoft Visual C++ 6.0,
// as described in
// ______
//
// PROVIDES: A template class for a node in a binary tree and functions for
// manipulating binary trees. The template parameter is the type of data in
// each node.
//
// TYPEDEF for the binary_tree_node<Item> template class:
// Each node of the tree contains a piece of data and pointers to its
// children. The type of the data (binary_tree_node<Item>::value_type) is
// the Item type from the template parameter. The type may be any of the C++
// built-in types (int, char, etc.), or a class with a default constructor,
// and an assignment operator.
//
// CONSTRUCTOR for the binary_tree_node<Item> class:
// binary_tree_node(
// const item& init_data = Item( ),
// binary_tree_node<Item>* init_left = NULL,
// binary_tree_node<Item>* init_right = NULL
// )
// Postcondition: The new node has its data equal to init_data,
// and it's child pointers equal to init_left and init_right.
//
// MEMBER FUNCTIONS for the binary_tree_node<Item> class:
// ------
// NOTE: I have changed the return values from the non-const versions of
// the left() and right() functions so that they return a reference to
// the pointer in the node. This is indicated by the & symbol here:
// binary_tree_node*& left( )
// The use of a "reference" in the return value has two advantages that
// simplify the material of Chapter 10:
// 1. It now allows a direct assignment such as: p->left() = NULL.
// This is not a huge advantage since the same thing can be accomplished
// by using the set_left function.
// 2. The expression p->left() can be passed as the argument
// to a function such as: tree_clear(p->left());
// The parameter of tree_clear is a reference parameter, so that
// any changes that tree_clear makes to p->left() will now affect
// the actual left pointer in the node *p. In this example, the
// tree_clear function does set its parameter to NULL, so that
// the total effect of tree_clear(p->left()) is to clear the left
// subtree of p and to set p's left pointer to NULL.
// In the case of tree_clear, this is not a huge advantage because we
// could have just set p's left pointer to NULL ourselves. But, in
// Section 10.5, there are two functions, bst_remove and bst_remove_max,
// which are easier to write if we can use p->left() and p->right() as
// the parameters of recursive calls. See the partial implementation
// of bag6.template for details:
//
// ------
// const item& data( ) const <----- const version
// and
// Item& data( ) <----- non-const version
// Postcondition: The return value is a reference to the data from
// this binary_tree_node.
//
// const binary_tree_node* left( ) const <----- const version
// and
// binary_tree_node*& left( ) <----- non-const version
// and
// const binary_tree_node* right( ) const <----- const version
// and
// binary_tree_node*& right( ) <----- non-const version
// Postcondition: The return value is a pointer to the left or right child
// (which will be NULL if there is no child).
//
// void set_data(const Item& new_data)
// Postcondition: The binary_tree_node now contains the specified new data.
//
// void set_left(binary_tree_node* new_link)
// and
// void set_right(binary_tree_node* new_link)
// Postcondition: The binary_tree_node now contains the specified new link
// to a child.
//
// bool is_leaf( )
// Postcondition: The return value is true if the node is a leaf;
// otherwise the return value is false.
//
// NON-MEMBER FUNCTIONS to maniplulate binary tree nodes:
// tempate <class Process, class BTNode>
// void inorder(Process f, BTNode* node_ptr)
// Precondition: node_ptr is a pointer to a node in a binary tree (or
// node_ptr may be NULL to indicate the empty tree).
// Postcondition: If node_ptr is non-NULL, then the function f has been
// applied to the contents of *node_ptr and all of its descendants, using
// an in-order traversal.
// Note: BTNode may be a binary_tree_node or a const binary tree node.
// Process is the type of a function f that may be called with a single
// Item argument (using the Item type from the node).
//
// tempate <class Process, class BTNode>
// void postorder(Process f, BTNode* node_ptr)
// Same as the in-order function, except with a post-order traversal.
//
// tempate <class Process, class BTNode>
// void preorder(Process f, BTNode* node_ptr)
// Same as the in-order function, except with a pre-order traversal.
//
// template <class Item, class SizeType>
// void print(const binary_tree_node<Item>* node_ptr, SizeType depth)
// Precondition: node_ptr is a pointer to a node in a binary tree (or
// node_ptr may be NULL to indicate the empty tree). If the pointer is
// not NULL, then depth is the depth of the node pointed to by node_ptr.
// Postcondition: If node_ptr is non-NULL, then the contents of *node_ptr
// and all its descendants have been written to cout with the < operator,
// using a backward in-order traversal. Each node is indented four times
// its depth.
//
// template <class Item>
// void tree_clear(binary_tree_node<Item>*& root_ptr)
// Precondition: root_ptr is the root pointer of a binary tree (which may
// be NULL for the empty tree).
// Postcondition: All nodes at the root or below have been returned to the
// heap, and root_ptr has been set to NULL.
//
// template <class Item>
// binary_tree_node<Item>* tree_copy(const binary_tree_node<Item>* root_ptr)
// Precondition: root_ptr is the root pointer of a binary tree (which may
// be NULL for the empty tree).
// Postcondition: A copy of the binary tree has been made, and the return
// value is a pointer to the root of this copy.
//
// template <class Item>
// size_t tree_size(const binary_tree_node<Item>* node_ptr)
// Precondition: node_ptr is a pointer to a node in a binary tree (or
// node_ptr may be NULL to indicate the empty tree).
// Postcondition: The return value is the number of nodes in the tree.
#ifndef BINTREE_H
#define BINTREE_H
#include <cstdlib> // Provides NULL and size_t
namespace main_savitch_10
{
template <class Item>
class binary_tree_node
{
public:
// TYPEDEF
typedef Item value_type;
// CONSTRUCTOR
binary_tree_node(
const Item& init_data = Item( ),
binary_tree_node* init_left = NULL,
binary_tree_node* init_right = NULL
)
{
data_field = init_data;
left_field = init_left;
right_field = init_right;
}
// MODIFICATION MEMBER FUNCTIONS
Item& data( ) { return data_field; }
binary_tree_node*& left( ) { return left_field; }
binary_tree_node*& right( ) { return right_field; }
void set_data(const Item& new_data) { data_field = new_data; }
void set_left(binary_tree_node* new_left) { left_field = new_left; }
void set_right(binary_tree_node* new_right) { right_field = new_right; }
// CONST MEMBER FUNCTIONS
const Item& data( ) const { return data_field; }
const binary_tree_node* left( ) const { return left_field; }
const binary_tree_node* right( ) const { return right_field; }
bool is_leaf( ) const
{ return (left_field == NULL) & (right_field == NULL); }
private:
Item data_field;
binary_tree_node *left_field;
binary_tree_node *right_field;
};
// NON-MEMBER FUNCTIONS for the binary_tree_node<Item>:
template <class Process, class BTNode>
void inorder(Process f, BTNode* node_ptr);
template <class Process, class BTNode>
void preorder(Process f, BTNode* node_ptr);
template <class Process, class BTNode>
void postorder(Process f, BTNode* node_ptr);
template <class Item, class SizeType>
void print(binary_tree_node<Item>* node_ptr, SizeType depth);
template <class Item>
void tree_clear(binary_tree_node<Item>*& root_ptr);
template <class Item>
binary_tree_node<Item>* tree_copy(const binary_tree_node<Item>* root_ptr);
template <class Item>
size_t tree_size(const binary_tree_node<Item>* node_ptr);
}
#include "bintree.template"
#endif
// FILE: bintree.template
// From Chapter 10 of Data Structures and Other Objects (Third Edition)
// ______
//
// This file has been modified to work with Microsoft Visual C++ 6.0,
// as described in
// ______
//
// IMPLEMENTS: The binary_tree node class (see bintree.h for documentation).
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL, size_t
#include <iomanip> // Provides std::setw
#include <iostream> // Provides std::cout
namespace main_savitch_10
{
template <class Process, class BTNode>
void inorder(Process f, BTNode* node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr != NULL)
{
inorder(f, node_ptr->left( ));
f( node_ptr->data( ) );
inorder(f, node_ptr->right( ));
}
}
template <class Process, class BTNode>
void postorder(Process f, BTNode* node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr != NULL)
{
postorder(f, node_ptr->left( ));
postorder(f, node_ptr->right( ));
f(node_ptr->data( ));
}
}
template <class Process, class BTNode>
void preorder(Process f, BTNode* node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr != NULL)
{
f( node_ptr->data( ) );
preorder(f, node_ptr->left( ));
preorder(f, node_ptr->right( ));
}
}
template <class Item, class SizeType>
void print(binary_tree_node<Item>* node_ptr, SizeType depth)
// Library facilities used: iomanip, iostream, stdlib
{
if (node_ptr != NULL)
{
print(node_ptr->right( ), depth+1);
std::cout < std::setw(4*depth) < ""; // Indent 4*depth spaces.
std::cout < node_ptr->data( ) < std::endl;
print(node_ptr->left( ), depth+1);
}
}
template <class Item>
void tree_clear(binary_tree_node<Item>*& root_ptr)
// Library facilities used: cstdlib
{
if (root_ptr != NULL)
{
tree_clear( root_ptr->left( ) );
tree_clear( root_ptr->right( ) );
delete root_ptr;
root_ptr = NULL;
}
}
template <class Item>
binary_tree_node<Item>* tree_copy(const binary_tree_node<Item>* root_ptr)
// Library facilities used: cstdlib
{
binary_tree_node<Item> *l_ptr;
binary_tree_node<Item> *r_ptr;
if (root_ptr == NULL)
return NULL;
else
{
l_ptr = tree_copy( root_ptr->left( ) );
r_ptr = tree_copy( root_ptr->right( ) );
return
new binary_tree_node<Item>( root_ptr->data( ), l_ptr, r_ptr);
}
}
template <class Item>
size_t tree_size(const binary_tree_node<Item>* node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr == NULL)
return 0;
else
return
1 + tree_size(node_ptr->left( )) + tree_size(node_ptr->right( ));
}
}
1Lab Handout for IT327
Data Structures