Binary Search Tree: Output

Yellowhottub (23)
I am unable to get this to compile do to a symbol referencing error. As far as I know it is a problem with the outputting print functions.

Header File:
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
 
#ifndef BST_H
#define	BST_H

#include <iostream>
#include <cstdlib>

const int MAX = 8;
typedef char Word[MAX+1];	

class BST
{
	//friend function
	friend std::ostream& operator << (std::ostream& out_s, const BST &t);

	private:
	    struct Node
	    {
		Word data;
		int count;
		Node *left;
		Node *right;
	    };
		Node *root;

	    //helper functions
	    void destroy(Node *r);
	    int find_length(Node *r);
	    void help_remove(Node *&t, Word target);
	    void remove_node(Node *&t);
	    int find_count(Node *&t, Word target);
	    void help_print(std::ostream &out_s, Node *r);

	public:
	    //constructor
	    BST();
	    //destructor
	    ~BST();
	    //modification member functions
	    int length();
	    void insert(Word entry, int count);
	    void remove(Word target);	
	    void print(std::ostream &out_s);
};

#endif


Implementation File:
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
 
#include "BST.h"
#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;


BST:: BST()
{
	root = NULL;
}

BST:: ~BST()
{
	destroy(root);
}

void BST:: destroy(Node *r)
{
	if(r != NULL)
	{
	    destroy(r -> left);
	    destroy(r -> right);
	    delete r;
	}

}

int BST:: find_length(Node* r)
{
	if(r != NULL)
	    return 0;
	else
	    return find_length(r -> left) + 1 + find_length(r -> right);
}

void BST:: help_remove(Node *&t, Word target)
{
	if(t -> data == target)
	    remove_node(t);
	else if(strcmp(t -> data, target) > 0)
	    help_remove(t -> left, target);
	else
	    help_remove(t -> right, target);
}

void BST:: remove_node(Node *&t)
{
	Node *back, *ptr;
	
	if(t -> left == NULL && t -> right == NULL)
	{
	    delete t;
	    t = NULL;
	}
	else if(t -> left == NULL)
	{
	    ptr = t;
	    t = t -> right;
	    delete ptr;
	}
	else if(t -> right == NULL)
	{
	    ptr = t;
	    t = t -> left;
	    delete ptr;
	}
	else
	{
	    back = t;
	    ptr = t -> right;
	    while(ptr -> left != NULL)
	    {
		back = ptr;
		ptr = ptr -> left;
	    }

	    strcpy(t -> data, ptr -> data);
	    
	    if(back == t)
		remove_node(back -> right);
	    else
		remove_node(back -> left);
	}
}

int BST:: find_count(Node *&t, Word target)
{
	if(t -> data == target)
	    return t -> count;
	else if(strcmp(t -> data, target) > 0)
	    find_count(t -> left, target);
	else
	    find_count(t -> right, target);
}

void BST:: help_print(ostream &out_s, Node *r)
{
	if(r != NULL)
	{
	    help_print(out_s, r -> left);
	    cout << r -> data << "                " << r -> count << endl;
	    help_print(out_s, r -> right);
	}
}

int BST:: length()
{
	return find_length(root);
}

void BST:: remove(Word target)
{
	help_remove(root, target);
}

void BST:: insert(Word entry, int count)
{
	Node *back, *ptr, *temp;

	ptr = root;
	back = NULL;

	while(ptr != NULL)
	{
	    back = ptr;
	    if(strcmp(ptr -> data, entry) > 0)
		ptr = ptr -> left;
	    else
		ptr = ptr -> right;
	}
	
	temp = new Node;
	strcpy(temp -> data, entry);
	temp -> left = NULL;
	temp -> right = NULL;
	
	if(back == NULL)
	    root = temp;
	else if(strcmp(back -> data, entry) > 0)
	    back -> left = temp;
	else
	    back -> right = temp;
}

void BST:: print(ostream& out_s)
{
	help_print(out_s, root);
}

ostream& operator << (ostream &out_s, BST &t)
{
	t.print(out_s);
	return out_s;
}


Client Program:
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
 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <cctype>
#include "BST.h"
using namespace std;

void read_word(ifstream& in_file, Word& word);
void build_list(ifstream& in_file, Word& word);

int main()
{
	char file_name[100];
	ifstream in_file;
	char array[MAX+1];

	cout << "Enter a file name: "; cin >> file_name;
	
	in_file.open(file_name);

	build_list(in_file, array);

	in_file.close();

	return EXIT_SUCCESS;
}

void read_word(ifstream& in_file, Word& word)
{
	char ch;
	int i = 0;
	in_file.get(ch);
 	
	while(isalpha(ch))
	{
		if(i >= MAX)
		{
		    in_file.get(ch);
		    word[MAX] = '\0';
		    break;
		}
		else
		{
		    ch = toupper(ch);
		    word[i] = ch;
		    i++;
		}

	    in_file.get(ch);

	}
}
	
void build_list(ifstream& in_file, Word& word)
{
	BST t;
	int count = 0;
	int test;

	for(int i = 0; i < MAX+1; i++)
	    word[i] = '\0';

	while(!in_file.eof())
	{
	    read_word(in_file, word);
	    if(isalpha(word[0]))
	        t.insert(word, count);
	    for(int i = 0; i < MAX; i++)
		word[i] = '\0';
	}

	cout << "Word" << "          " << "Count" << endl;
	cout << "--------------------" << endl;
	cout << t;
	cout << "--------------------" << endl;

}
ne555 (10692)
Post the compile message
Yellowhottub (23)
Undefined First referenced
Symbol in file
operator<<(std::basic_ostream<char, std::_traits<char> >&, BST &const) /var/tmp/ /cc6IG3ty.o
ld: fatal: symbol referencing errors. No output written to a.out
collect2: ld returned 1 exit status
ne555 (10692)
Try to respect the prototype
ostream& operator << (ostream &out_s, const BST &t)
Topic archived. No new replies allowed.