C++

Forum

 
Trees

OLittleO (54)
So our teacher gave us a game of 20 questions basically as sample code however the sample code does not run and I have tried to fix it. I have gotten it down to 14 errors however I do not know what to do from here. Here is the code. I have a total of 5 files. Other files in comment below this one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
 
// FILE: animal.cxx
// 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;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
// FILE: bintree.cpp
// IMPLEMENTS: The binary_tree node class (see bintree.h for documentation).
#include <cassert>    // Provides assert
#include <cstdlib>   // Provides NULL, std::size_t
#include <iomanip>    // Provides std::setw
#include <iostream>   // Provides std::cout
#include "bintree.h"

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( ));
    }
}

OLittleO (54)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
 
// FILE: bintree.h (part of the namespace main_savitch_10)
// 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:
//   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>
    std::size_t tree_size(const binary_tree_node<Item>* node_ptr);
}

#include "bintree.cpp"
#endif
OLittleO (54)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
// FILE: useful.cxx
// IMPLEMENTS: A toolkit of functions (See useful.h for documentation.)

#include <cassert>    // Provides assert
#include <cctype>     // Provides toupper
#include <cstdlib>    // Provides rand, RAND_MAX
#include <iostream.h> // Provides cout, cin, get
#include "useful.h"

void display(double x)
// Library facilities used: iostream.h, stdlib.h
{
    const char STAR = '*';
    const char BLANK = ' ';
    const char VERTICAL_BAR = '|';
    const int  LIMIT = 39;
    int i;

    if (x < -LIMIT)
        x = -LIMIT;
    else if (x > LIMIT) 
        x = LIMIT;

    for (i = -LIMIT; i < 0; i++)
    {
        if (i >= x)
            cout << STAR;
        else
            cout << BLANK;
    }
    cout << VERTICAL_BAR;
    for (i = 1; i <= LIMIT; i++)
    {
        if (i <= x)
            cout << STAR;
        else
            cout << BLANK;
    }
    cout << endl;
}

double random_fraction( )
// Library facilities used: stdlib.h
{
    return rand( ) / double(RAND_MAX);
}

double random_real(double low, double high)
// Library facilities used: assert.h
{
    assert(low <= high);
    return low + random_fraction( ) * (high - low);
}

void eat_line( )
// Library facilities used: iostream.h
// 
{
    char next;

    do
        cin.get(next);
    while (next != '\n');
}

bool inquire(const char query[ ])
// Library facilities used: ctype.h, iostream.h
{
    char answer;
    do
    {
        cout << query << " [Yes or No]" << endl;
        cin >> answer;
        answer = toupper(answer);
        eat_line( );
    }
    while ((answer != 'Y') && (answer != 'N'));
    return (answer == 'Y');
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
// FILE: useful.h
// PROVIDES: A toolkit of useful functions for random numbers and displays.
// Note that these are in the global namespace.
//
// FUNCTIONS in the toolkit:
//   double random_fraction( )
//     Postcondition: The return value is a random real number in the closed
//     interval [0..1] (including the endpoints).
//
//   double random_real(double low, double high)
//     Precondition: low <= high.
//     Postcondition: The return value is a random real number in the closed
//     interval [low..high] (including the endpoints).
//
//   void display(double x)
//     Postcondition: The function has written one line of output to the
//     standard ouput, with a vertical bar in the middle. If x is positive,
//     then approximately x stars are printed to the right of the vertical
//     bar. If x is negative, then approximately -x stars are printed to the
//     left of the vertical bar. If the absolute value of x is more than
//     39, then only 39 stars are printed.
//     Examples:
//     display(8) prints:                          |********
//     display(-4) prints:                     ****|
//
//   void eat_line( )
//     Postcondition: Up to next newline has been read and discarded from cin.
//
//   bool inquire(const char query[ ])
//     Precondition: query is a null-terminated string of characters.
//     Postcondition: query has been printed, and a one-line response read 
//     from the user. The function returns true if the user's response begins 
//     with 'Y' or 'y', and returns false if the user's response begins with 
//     'N' or 'n'. (If the response begins with some other letter, then the
//     query is repeated.)

#ifndef USEFUL_H  // Prevent duplicate definition
#define USEFUL_H

    double random_fraction( );
    double random_real(double low, double high);
    void display(double x);
    void eat_line( );
    bool inquire(const char query[ ]);

#endif
OLittleO (54)
and here are the errors.
Project 4.1\bintree.cpp|12|error: redefinition of 'template<class Process, class BTNode> void main_savitch_10::inorder(Process, BTNode*)'|
Project 4.1\bintree.cpp|12|error: 'template<class Process, class BTNode> void main_savitch_10::inorder(Process, BTNode*)' previously declared here|
Project 4.1\bintree.cpp|24|error: redefinition of 'template<class Process, class BTNode> void main_savitch_10::postorder(Process, BTNode*)'|
Project 4.1\bintree.cpp|24|error: 'template<class Process, class BTNode> void main_savitch_10::postorder(Process, BTNode*)' previously declared here|
Project 4.1\bintree.cpp|36|error: redefinition of 'template<class Process, class BTNode> void main_savitch_10::preorder(Process, BTNode*)'|
Project 4.1\bintree.cpp|36|error: 'template<class Process, class BTNode> void main_savitch_10::preorder(Process, BTNode*)' previously declared here|
Project 4.1\bintree.cpp|48|error: redefinition of 'template<class Item, class SizeType> void main_savitch_10::print(main_savitch_10::binary_tree_node<Item>*, SizeType)'|
Project 4.1\bintree.cpp|48|error: 'template<class Item, class SizeType> void main_savitch_10::print(main_savitch_10::binary_tree_node<Item>*, SizeType)' previously declared here|
Project 4.1\bintree.cpp|61|error: redefinition of 'template<class Item> void main_savitch_10::tree_clear(main_savitch_10::binary_tree_node<Item>*&)'|
Project 4.1\bintree.cpp|61|error: 'template<class Item> void main_savitch_10::tree_clear(main_savitch_10::binary_tree_node<Item>*&)' previously declared here|
Project 4.1\bintree.cpp|74|error: redefinition of 'template<class Item> main_savitch_10::binary_tree_node<Item>* main_savitch_10::tree_copy(const main_savitch_10::binary_tree_node<Item>*)'|
Project 4.1\bintree.cpp|74|error: 'template<class Item> main_savitch_10::binary_tree_node<Item>* main_savitch_10::tree_copy(const main_savitch_10::binary_tree_node<Item>*)' previously declared here|
Project 4.1\bintree.cpp|92|error: redefinition of 'template<class Item> size_t main_savitch_10::tree_size(const main_savitch_10::binary_tree_node<Item>*)'|
Project 4.1\bintree.cpp|92|error: 'template<class Item> std::size_t main_savitch_10::tree_size(const main_savitch_10::binary_tree_node<Item>*)' previously declared here|
||=== Build finished: 14 errors, 0 warnings (0 minutes, 1 seconds) ===|
booradley60 (896)
At the bottom of bintree.h you say 
 
 
#include "bintree.cpp"
Don't do that.
Topic archived. No new replies allowed.