// Entry.h
#include <iostream>
using namespace std;
template <typename K, typename V>
class Entry {
public:
typedef K Key;
typedef V Value;
public:
Entry(const K& k= K(), const V& v=V())
:_key(k), _value(v) {}
K& key() { return _key; }
V& value() { return _value; }
void setKey(const K& k) { _key = k; }
void setValue(const V& v) { _value = v; }
private:
K _key;
V _value;
};
//LinkedBinaryTree.h
#include <list>
#include "Entry.h"
typedef int Elem;
class LinkedBinaryTree {
public:
struct Node {
Entry<Elem, Elem> E;
Node* par;
Node* left;
Node* right;
Node() : par(NULL), left(NULL), right(NULL) {}
};
public:
class Position {
private:
Node* v;
public:
Position(Node* _v=NULL) : v(_v) {}
Elem& operator*() { return v->E.value(); }
Position left() const { return Position(v->left); }
Position right() const { return Position(v->right); }
Position parent() const { return Position(v->par); }
bool isRoot() const { return v->par == NULL; }
bool isExternal() const { return v->left == NULL && v->right == NULL; }
bool isInternal() const { return v->left != NULL || v->right != NULL; } //추가
friend class LinkedBinaryTree;
};
typedef std::list<Position> PositionList;
public:
LinkedBinaryTree();
int size() const;
bool empty() const;
Position root() const;
PositionList positions() const;
void addRoot();
void expandExternal(const Position& p);
Position removeAboveExternal(const Position& p);
protected:
void preorder(Node* v, PositionList& pl) const;
private:
Node* _root;
int n;
};
//SearchTree.h
#include "LinkedBinaryTree.h"
template <typename E>
class SearchTree {
public:
typedef typename E::Key K;
typedef typename E::Value V;
class Iterator;
public:
SearchTree();
int size();
bool empty() const;
Iterator find(const K& k);
Iterator insert(const K& k, const V& x);
void erase(const K& k);
void erase(const Iterator& p);
Iterator begin();
Iterator end();
protected:
//typedef LinkedBinaryTree<E> BinaryTree;
typedef typename LinkedBinaryTree::Position TPos;
TPos root() const;
TPos finder(const K& k, const TPos& v);
TPos inserter(const K& k, const V& x);
TPos eraser(TPos& v);
//TPos restructe(const TPos& v);
private:
LinkedBinaryTree T;
int n;
public:
class Iterator {
private:
TPos v;
public:
Iterator(const TPos& vv) : v(vv) {}
const E& operator*() const { return *v; }
const E& operator*() { return *v; }
bool operator==(const Iterator& p) const { return v == p.v; }
Iterator& operator++();
friend class SearchTree;
};
};
