링크드리스트를 이용한 Binary Tree와 Binary search Tree의 구현(C++)

소개글

링크드리스트를 이용한 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