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
|
#include <iostream>
#include <string>
using std::string;
using std::cin;
using std::cout;
using std::istream;
using std::ostream;
class Event {
public:
int year; // this is the key
string name; // name of the event
// constructor
Event(int y=0, const string &n = "") :
year(y), name(n)
{}
// Less than operator lets you compare two events with
// event1 < event2. The tree uses this to establish the order
bool operator<(const Event &rhs) const {
return year < rhs.year;
}
};
// Print the event to the output stream
ostream & operator << (ostream &os, const Event &e) {
return os << e.year << ' ' << e.name;
}
// Read the event from the input stream
istream &operator >> (istream &is, Event &e) {
is >> e.year;
getline(is, e.name);
return is;
}
// A Node is an event and left & right pointers.
// It would be better to make this a class inside the Tree class,
// but this is the beginners forum.
class Node
{
public:
Node (const Event &e) :
event(e), left(NULL), right(NULL)
{}
Event event;
Node *left, *right;
};
// A tree has all the member functions and a pointer to the root node.
class Tree
{
public:
Tree() :
root(NULL)
{}
void add (const Event &);
const Event *find(const Event &e) {
Node *pos = findPosition(root, e);
return (pos ? &pos->event : NULL);
}
void preorder(ostream &os) {
preorder(os, root, 0);
}
void preorder(ostream &, Node *, int indent);
void inorder(ostream &os) {
inorder(os, root, 0);
}
void inorder(ostream &, Node *, int indent);
// This does most of the work for find and add. It returns a reference
// to the pointer (root, or a nodes right or left pointer) where the
// event is located, or should be located if you insert it.
Node * &findPosition(Node *&, const Event &);
private:
Node *root;
};
// pre-order print the node os at the indent level
void Tree::preorder(ostream &os, Node *node, int indent)
{
if (node) {
os << std::string(2*indent, ' ') << "+--- " << node->event << '\n';
preorder(os, node->left, indent+1);
preorder(os, node->right, indent+1);
}
}
// in-order print the node os at the indent level
void Tree::inorder(ostream &os, Node *node, int indent)
{
if (node) {
inorder(os, node->left, indent+1);
os << std::string(2*indent, ' ') << "+--- " << node->event << '\n';
inorder(os, node->right, indent+1);
}
}
Node * &
Tree::findPosition(Node *&node, const Event &e)
{
if (node == NULL) return node;
if (e < node->event) {
return findPosition(node->left, e);
} else if (node->event < e) {
return findPosition(node->right, e);
} else {
return node;
}
}
void
Tree::add (const Event &e)
{
Node * &pos = findPosition(root, e);
if (pos) {
pos->left = new Node(e); // duplicate entry. Add to left
} else {
pos = new Node(e);
}
}
int main()
{
Tree tree;
string str; // use a string instead array of chars
Event e;
// Skip the first line
getline(cin, str);
while (cin >> e) {
tree.add(e);
}
cout << "IN ORDER:\n";
tree.inorder(cout);
cout << "\n\nPRE ORDER:\n";
tree.preorder(cout);
}
|