링크드리스트를 이용한 Binary Tree와 Binary search Tree의 구현(C++)
- 최초 등록일
- 2012.03.08
- 최종 저작일
- 2011.12
- 압축파일
- 가격 1,000원
소개글
링크드리스트를 이용한 Binary Tree와 Binary search Tree의 구현(C++)
컴파일 실행환경
Microsoft Visual Studio 2008 (C++)
본문내용
#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include "LinkedBinaryTree.h"
#include "Exceptions.h"
template
class Entry{
public:
typedef K Key;
typedef V Value;
public:
Entry(const K& k=K(), const V& v=V()) : _key(k), _value(v) {}
const K& key() const{return _key;}
const V& value() const{return _value;}
void setKey(const K& k){_key=k;}
void setValue(const V& v){_value=v;}
public:
K _key;
V _value;
};
template
class SearchTree{
public:
typedef typename T::Key K;
typedef typename T::Value V;
class Iterator;
public:
SearchTree();
int size() const;
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 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);
private:
BinaryTree Tree;
int n;
public:
void sorting();
public:
class Iterator{
private:
TPos v;
public:
Iterator(const TPos& vv): v(vv) {}
const T& operator*() const{return *v;}
T& operator*(){return *v;}
bool operator==(const Iterator& p) const{
return v==p.v;}
Iterator& operator++();
friend class SearchTree;
};
};
template
typename SearchTree::Iterator& SearchTree::Iterator::operator ++(){
TPos w=v.right();
if(!w.isExternal()){
do { v=w; w=w.left();} while {!w.isExternal()};
}
else{
w=v.par();
while(v==w.right()){
v=w;
w=w.par();
}
v=w;
}
return *this;
}
압축파일 내 파일목록
test.cpp
BinarySearchTree.h
Exceptions.h
LinkedBinaryTree.h
NodeList.h
참고 자료
M. T. Goodrich, A. Tamassia, and D. Mount, 2011, 『Data Structures and Algorithms in C (2nd ED)』, Wiley