이원탐색트리 구현

#ifndef BST_H
#define BST_H
#include <iostream>
#include <queue>
using namespace std;
 
 
template<class K,class E>
struct Node{
        Node(K ky,E el,Node<K,E> *left=0,Node<K,E> *right=0,int size=1)
                :key(ky),element(el),leftChild(left),rightChild(right),leftSize(size){}
        Node<K,E> *leftChild;
        K key;
        E element;
        Node<K,E> *rightChild;
        int leftSize;
};
template<class K,class E>
class BST{
public:
        BST(){root=0;}
        void Insert(K &newkey,E &el){Insert(root,newkey,el);}
        void Inorder(){Inorder(root);}
        void Postorder(){Postorder(root);}
        bool Get(const K&,E&);
        bool Print();
        bool Rankget(int r,K& k,E& e);
        void Delete(K &oldkey) {Delete(root,oldkey);}
        void ThreeWayJoin(BST<K,E>& small,K midkey,E midel,
                          BST<K,E>& big);
        void TwoWayJoin(BST<K,E>& small,BST<K,E>& big);
private:
        void Visit(Node<K,E> *);
        void Insert(Node<K,E>* &,K &,E &);
        void Preorder(Node<K,E> *);
        void Inorder(Node<K,E> *);
        void Postorder(Node<K,E> *);
        void Delete(Node<K,E> * &,K &);
        Node<K,E> *root;
};
template<class K,class E>
void BST<K,E>::Visit(Node<K,E> *ptr){cout<<ptr->key<<":"<<ptr->element<<" ";}
 
template<class K,class E>
void BST<K,E>::Insert(Node<K,E>* &ptr,K &newkey,E &el){
        if(ptr==0) ptr=new Node<K,E>(newkey,el);
        else if(newkey<ptr->key){
                ptr->leftSize+=1;
                Insert(ptr->leftChild,newkey,el);
        }
        else if(newkey>ptr->key) Insert(ptr->rightChild,newkey,el);
        else ptr->element=el;
}
 
template<class K,class E>
void BST<K,E>::Inorder(Node<K,E> *currentNode){
        if(currentNode){
                Inorder(currentNode->leftChild);
                Visit(currentNode);
                Inorder(currentNode->rightChild);
        }
}
template<class K,class E>
void BST<K,E>::Postorder(Node<K,E> *currentNode){
        if(currentNode){
                Postorder(currentNode->leftChild);
                Postorder(currentNode->rightChild);
                Visit(currentNode);
       }
}
template<class K,class E>
bool BST<K, E>::Get(const K& k,E& e){
        Node<K,E> *ptr=root;
        while(ptr)
                if(k<ptr->key) ptr=ptr->leftChild;
                else if(k> ptr->key) ptr=ptr->rightChild;
                else{ e=ptr->element; return true;}
        return false;
}
template <class K,class E>
bool BST<K,E>::Rankget(int r,K& k,E& e){
        Node<K,E> *currentNode=root;
        while(currentNode)
                if(r<currentNode->leftSize) currentNode=currentNode->leftChild;
                else if(r>currentNode->leftSize){
                        r-=currentNode->leftSize;
                        currentNode=currentNode->rightChild;
                }
                else{
                        k=currentNode->key;
                        e=currentNode->element;
                        return true;
                }
        return false;
}
template<class K,class E>
void BST<K,E>::Delete(Node<K,E>* &ptr,K &oldkey){
        Node<K,E> *tmpptr; Node<K,E> *tmpdaddyptr;
        if(ptr==0)return;
        if(oldkey<ptr->key)
                Delete(ptr->leftChild,oldkey);
        else if(oldkey>ptr->key)
                Delete(ptr->rightChild,oldkey);
        else{
                if(!ptr->leftChild && !ptr->rightChild)
                        { delete ptr; ptr=0; return;}
                else if(ptr->leftChild &&!ptr->rightChild)
                        { tmpptr=ptr; ptr=ptr->leftChild;
                           delete tmpptr; return;}
                else if(!ptr->leftChild&&ptr->rightChild)
                        { tmpptr=ptr; ptr=ptr->rightChild;
                          delete tmpptr; return;}
                else{
                        Node<K,E> *rc=ptr->rightChild;
                        if(!rc->leftChild){
                                ptr->key=rc->key;
                                ptr->element=rc->element;
                                ptr->rightChild=rc->rightChild;
                                delete rc;}
                        else{
                                while(rc->leftChild){
                                        tmpdaddyptr=rc;
                                        rc=rc->leftChild;}
                                ptr->key=rc->key;
                                ptr->element=rc->element;
                                tmpdaddyptr->leftChild=rc->rightChild;
                                delete rc;
                        }
                }
        }
}
template<class K,class E>
bool BST<K,E>::Print() {
        cout<<endl<<"inorder traversal : "; Inorder();
        cout<<endl<<"Postorder raversal : "; Postorder();
        cout<<endl;
}
template<class K,class E>
void BST<K,E>::ThreeWayJoin(BST<K,E>& small,K midkey,E midel,BST<K,E>& big){
        root=new Node<K,E>(midkey,midel,small.root,big.root);
        small.root=big.root=0;
}
template<class K,class E>
void BST<K,E>::TwoWayJoin(BST<K,E>& small,BST<K,E>& big){
        if(!small.root) {root=big.root; big.root=0;return;}
        if(!big.root) {root=small.root; small.root=0; return;}
        BST small2=small;
        Node<K,E> *rc=small.root;
        while(rc->rightChild){
                rc=rc->rightChild;
        }
        K midkey=rc->key;
        E midele=rc->element;
        small.Delete(midkey);
        ThreeWayJoin(small,midkey,midele,big);
        small.root=0; big.root=0;
}
#endif
 

bst.h 

Rankget 함수와 관련된 leftsize는 문제가 있으므로 추후 수정하겠음.

#include<fstream>
#include "bst.h"
 
void File2Tree(istream &fin,BST<string,int>& tree){
        string command,key; int elt; int r;
 
        while(fin>> command)
                if(command =="print") tree.Print();
                else if(command=="insert")
                        { fin>>key>>elt; tree.Insert(key,elt);}
                else if(command=="get"){
                        fin>>key;
                        if(tree.Get(key,elt))
                                cout<<"The value of "<<key<<" is "
                                    <<elt<<endl;
                        else cout<<"No such key: " <<key<<endl;
                }
                else if(command=="rankget"){
                        fin>>r;
                        if(tree.Rankget(r,key,elt))
                                cout<<"The "<<r<<"-th element is "
                                    <<key<<":"<<elt<<endl;
                        else cout<<"No such ranking: "<<r<<endl;
                }
                else if(command =="delete")
                        {fin>>key; tree.Delete(key);}
                else
                        cout<<"Invalid command : " <<command<<endl;
}
 
int main(int argc,char *argv[]){
        if(argc<2)
                {cerr<<"Usage: "<<argv[0]<<"infile\n"; return 1;}
        ifstream fin(argv[1]);
        if(!fin){ cerr<<argv[1]<<" open failed\n";
                        return 1;}
        BST<string, int> tree;
        File2Tree(fin,tree);
        fin.close();
}
 

#include<fstream>
#include "bst.h"
 
void File2Tree(istream &fin,BST<string,int>& tree){
        string command,key; int elt; int r;
 
        while(fin>> command)
                if(command =="print") tree.Print();
                else if(command=="insert")
                        { fin>>key>>elt; tree.Insert(key,elt);}
                else if(command=="get"){
                        fin>>key;
                        if(tree.Get(key,elt))
                                cout<<"The value of "<<key<<" is "
                                    <<elt<<endl;
                        else cout<<"No such key: " <<key<<endl;
                }
                else if(command=="rankget"){
                        fin>>r;
                        if(tree.Rankget(r,key,elt))
                                cout<<"The "<<r<<"-th element is "
                                    <<key<<":"<<elt<<endl;
                        else cout<<"No such ranking: "<<r<<endl;
                }
                else if(command =="delete")
                        {fin>>key; tree.Delete(key);}
                else
                        cout<<"Invalid command : " <<command<<endl;
}
 
int main(int argc,char *argv[]){
        if(argc<2)
                {cerr<<"Usage: "<<argv[0]<<"infile[infile2]\n"; return 1;}
        ifstream fin(argv[1]);
        if(!fin){ cerr<<argv[1]<<" open failed\n";
                        return 1;}
        BST<string, int> small;
        File2Tree(fin,small);
        fin.close();
        if(argc==2) return 0;
        ifstream fin2(argv[2]);
        if(!fin2){cerr<<argv[2]<<" open failed\n";return 1;}
 
        BST<string,int> big;
        cout<<"\n2nd tree follows\n";
        File2Tree(fin2,big); fin2.close();
 
        BST<string,int> finaltree;
        finaltree.TwoWayJoin(small,big);
        cout<<"\n<two way joined tree final print>";
        finaltree.Print();
}
 
 

insert boy 23
insert emerald 70
insert cola 30
insert dog 40
insert ace 10
insert bug 27
insert boy 90
print
get boy
get emerald
get dog
get hohoho
 
 
 
 
 
insert xboy 23
insert xemerald 70
insert xcola 30
insert xdog 40
insert xace 10
insert xboy 90
print
rankget 4
delete xcola
delete xemerald
print
get xboy
get xemerald
get xdog
get xhohoho
 

입력data 2개

환경:linux