#include
#include
using namespace std;
//A generic binary sorted tree.
template class gen_tree; //forward decl
template
class bnode {
private:
friend class gen_tree;
bnode* left;
bnode* right;
T data;
int count;
bnode(T d, bnode* l, bnode* r) :
data(d), left(l), right(r), count(1) { }
void print() const
{ cout << data << " : " << count << '\t'; }
};
template
class gen_tree {
public:
gen_tree() { root = 0; }
void insert(T d);
T find(T d) const { return (find(root, d)); }
void print() const { print(root); }
private:
bnode* root;
T find(bnode* r, T d) const;
void print(bnode* r) const;
};
template
void gen_tree::insert(T d)
{
bnode* temp = root;
bnode* old;
if (root == 0) {
root = new bnode(d, 0, 0);
return;
}
while (temp != 0) {
old = temp;
if (comp(temp -> data, d) == 0) {
(temp -> count)++;
return;
}
if (comp(temp -> data, d) > 0)
temp = temp -> left;
else
temp = temp -> right;
}
if (comp(old -> data, d) > 0)
old -> left = new bnode(d, 0, 0);
else
old -> right = new bnode(d, 0, 0);
}
template
T gen_tree::find(bnode* r, T d) const
{
if (r == 0)
return 0;
else if (comp(r -> data, d) == 0)
return (r -> data);
else if (comp(r -> data, d) > 0)
return (find( r -> left, d));
else
return (find( r -> right, d));
}
template
void gen_tree::print(bnode *r) const
{
if (r != 0) {
print( r -> left);
r -> bnode::print();
print ( r -> right);
}
}
template //general case
int comp(T i, T j)
{
if (i == j) //assumes == < defined for T
return 0;
else
return ( (i < j) ? -1 : 1 );
}
//specialization for const char*
int comp(const char* i, const char* j){
return (strcmp(i, j));
}
int main()
{
char dat[256];
gen_tree t;
char* p;
while (cin>>dat){
p = new char[strlen(dat) + 1];
strcpy(p, dat);
t.insert(p);
}
t.print();
cout << "EOF" << endl << endl;
gen_tree i_tree;
for (int i = 15; i > -5; --i)
i_tree.insert(i);
i_tree.print();
}