 |
| Tree Structures |
Introduction
In many situation, an efficient way to represent data structures is to use trees. A
tree can be defined recursively as an object containing some data and references
to a certain number of subtrees. This definition leads to a hierarchical structure,
in which trees with no sub-trees are called leaves. The other ones are called
internal nodes.
More mathematically, a tree is a graph with no cycles.
Those data structures are very useful to store and organize informations associ-
ated to comparable values. Here we give an example of an associative memory
int -> string.
A simple implementation
class Tree {
// The key
int key;
// The associated string
string str;
// The two subtrees
Tree *left, *right;
public:
Tree(int *k, string *s, int n);
~Tree();
int size();
int depth();
int nbLeaves();
string get(int k);
};
int main(int argc, char **argv) {
string s[] = { "six", "four", "three", "seven",
"two", "one", "nine", "five", "eight", "ten" };
int k[] = { 6, 4, 3, 7, 2, 1, 9, 5, 8, 10 };
Tree t(k, s, 10);
cout << t.get(3) << "\n";
}
Tree::Tree(int *k, string *s, int n) {
for(int i = 0; i<n; i++) cout << k[i] << ":" << s[i]<< " ";
cout << "\n";
key = k[0];
str = s[0];
int *ktmp = new int[n-1];
string *stmp = new string[n-1];
int a = 0, b = n-2;
for(int i = 1; i<n; i++) if(k[i] < key) {
ktmp[a] = k[i]; stmp[a] = s[i]; a++;
} else {
ktmp[b] = k[i]; stmp[b] = s[i]; b--;
}
if(a > 0) left = new Tree(ktmp, stmp, a);
else left = 0;
if(b < n-2) right = new Tree(ktmp+a, stmp+a, n-2-b);
else right = 0;
}
Tree::~Tree() {
if(left) delete left;
if(right) delete right;
}
int Tree::size() {
int n = 1;
if(left) n += left->size();
if(right) n += right->size();
return n;
}
int Tree::depth() {
int dl, dr;
if(left) dl = left->depth(); else dl = 0;
if(right) dr = right->depth(); else dr = 0;
if(dl > dr) return dl+1; else return dr+1;
}
string Tree::get(int k) {
if(key == k) return str;
else if(k < key) {
if(left) return left->get(k);
else abort();
} else {
if(right) return right->get(k);
else abort();
}
}
template<class T>
class Stack {
int size, maxSize;
T *data;
public:
Stack(int m) : size(0), max Size(m), data(new T[m]) {}
~Stack() { delete[] data; }
T pop() { if(size == 0) abort(); else return data[--size]; }
void push(T x) { if(size == maxSize) abort(); else data[size++] = x; }
void print(ostream &o) {
for(int i = size-1; i >= 0; i--) o << data[i] << ’\n’;
}
};
class String Mapping {
public:
virtual string apply(string s) const = 0;
};
void Tree::stacks Elements(Stack<string> &stack) {
stack.push(str);
if(left) left->stacks Elements(stack);
if(right) right->stacks Elements(stack);
}
void Tree::apply Mapping(const String Mapping &map) {
str = map.apply(str);
if(left) left->apply Mapping(map);
if(right) right->apply Mapping(map);
}
class Add Something: public String Mapping {
string stuff;
public:
Add Something(string s) { stuff = s; }
string apply(string s) const { return s + stuff; }
};
int main(int argc, char **argv) {
string s[] = { "six", "four", "three", "seven",
"two", "one", "nine", "five", "eight", "ten" };
int k[] = { 6, 4, 3, 7, 2, 1, 9, 5, 8, 10 };
Tree t(k, s, 10);
cout << t.get(3) << "\n";
Stack<string> stack(100);
t.applyMapping(AddSomething(" excellent!!!"));
t.stacksElements(stack);
stack.print(cout);
}
6:six 4:four 3:three 7:seven 2:two 1:one 9:nine 5:five 8:eight 10:ten
4:four 3:three 2:two 1:one 5:five
3:three 2:two 1:one
2:two 1:one
1:one
5:five
10:ten 8:eight 9:nine 7:seven
8:eight 9:nine 7:seven
7:seven
9:nine
three
nine excellent!!!
seven excellent!!!
eight excellent!!!
ten excellent!!!
five excellent!!!
one excellent!!!
two excellent!!!
three excellent!!!
four excellent!!!
six excellent!!!