자료구조 프로그래밍 과목을 배우면서 c++로 작성한 이진탐색트리입니다.
bst.inbst.h
#ifndef BST_H
#define BST_H
#include <iostream>
#include <string>
#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) :key(ky), element(el), leftChild(left), rightChild(right)
{
}
Node<K, E> *leftChild;
K key;
E element;
Node<K, E> *rightChild;
};
template <class K, class E>
class BST
{
private:
void Visit(Node<K, E> *);
void Insert(Node<K, E>*&, K &, E &);
void Delete(Node<K, E>*&, K &);
void Preorder(Node<K, E> *);
void Inorder(Node<K, E> *);
void Postorder(Node<K, E> *);
Node<K, E> *root;
public:
BST()
{
root = 0;
}
void Insert(K &newkey, E &el)
{
Insert(root, newkey, el);
}
void Delete(K &oldkey)
{
Delete(root, oldkey);
}
bool Find(const K &, E &);
void Preorder()
{
Preorder(root);
}
void Inorder()
{
Inorder(root);
}
void Postorder()
{
Postorder(root);
}
void Levelorder();
};
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)
Insert(ptr->leftChild, newkey, el);
else if (newkey>ptr->key)
Insert(ptr->rightChild, newkey, el);
else
ptr->element = el;
}
template <class K, class E>
bool BST<K, E>::Find(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>
void BST<K, E>::Delete(Node<K, E> *&ptr, K &oldkey)
{
//ptr를 루트로 하는 트리에서 oldkey를 키로 하는 노드를 지우시오
Node<K, E> *tmpptr;
Node<K, E> *tmpdaddyptr;
if (ptr == 0)
return; //그런 노드가 없으므로, 그냥 return
if (oldkey < ptr->key) //좌측자식을 루트로 하는 트리에서 지우시오
Delete(ptr->leftChild, oldkey);
else if (oldkey > ptr->key) //우측자식을 루틀 하는 트리에서 지우시오
Delete(ptr->rightChild, oldkey);
else //ptr노드가 바로 지울 노드인 경우
{
if (!ptr->leftChild && !ptr->rightChild) //자식이 없다면
{
delete ptr;
ptr = 0;
return;
}
else if (ptr->leftChild && !ptr->rightChild) //왼쪽자식만 있다면
{
//그 자식을 ptr가 가리키게하고 현재 ptr가 가리키는 노드 지움
tmpptr = ptr;
ptr = ptr->leftChild;
delete tmpptr;
return;
}
else if (!ptr->leftChild && ptr->rightChild) //오른쪽자식만 있다면
{
tmpptr = ptr;
ptr = ptr->rightChild;
delete tmpptr;
return;
}
else
{
//두 자식 있음: 루트가 rc인 우측트리에서 '제일작은 노드' 찾자
Node<K, E> *rc = ptr->rightChild; //rc가 루트인 subtree
if (!rc->leftChild) //rc가 왼쪽자식이 없으면 rc가 그 노드!
{
ptr->key = rc->key;
ptr->element = rc->element;
ptr->rightChild = rc->rightChild;
delete rc;
return;
}
//rc의 왼쪽 자식이 있는 경우, rc의 왼쪽자식의 왼쪽자식의 식으로 왼쪽 자식을 끝까지 쫓아가, 가장 작은 키 갖는 노드를 찾는다
//그 노드의 key/element를 ptr노드로 옮기고 그 노드의 rightChild는 그 노드의 부모의 leftChild에 저장한 다음 그 노드를 지움
else
{
while (1)
{
if (rc->leftChild)
{
tmpdaddyptr = rc;
rc = rc->leftChild;
}
else
break;
}
ptr->key = rc->key;
ptr->element = rc->element;
tmpdaddyptr->leftChild = rc->rightChild;
delete rc;
return;
}
}
}
}
template <class K, class E>
void BST<K, E>::Preorder(Node<K, E> *currentNode)
{
if (currentNode)
{
Visit(currentNode);
Preorder(currentNode->leftChild);
Preorder(currentNode->rightChild);
}
}
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>
void BST<K, E>::Levelorder()
{
queue<Node<K, E>*> q;
Node<K, E> *currentNode = root;
while (currentNode)
{
Visit(currentNode);
if (currentNode->leftChild)
q.push(currentNode->leftChild);
if (currentNode->rightChild)
q.push(currentNode->rightChild);
if (q.empty())
return;
currentNode = q.front();
q.pop();
}
}
#endif
hw9.cpp
#include "bst.h"
int main(void)
{
BST<string, double> tree;
string command, str;
double dval;
while (cin >> command)
{
if (command == "insert")
{
cin >> str >> dval;
tree.Insert(str, dval);
}
else if (command == "delete")
{
cin >> str;
tree.Delete(str);
}
else if (command == "print")
{
cout << endl << "Inorder traversal: ";
tree.Inorder();
cout << endl << "Postorder traversal: ";
tree.Postorder();
cout << endl;
}
else if (command == "find")
{
cin >> str;
if (tree.Find(str, dval))
cout << "The value of " << str << " is " << dval << endl;
else
cout << "No such key: " << str << endl;
}
else
cout << "Invalid command: " << command << endl;
}
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'학교 과제' 카테고리의 다른 글
| c++로 작성한 최대 힙 (1) | 2018.01.06 |
|---|---|
| c++로 작성한 AVL 트리 (0) | 2018.01.05 |
| c++로 작성한 트리 순회 (0) | 2018.01.02 |
| c++로 작성한 링크드 리스트 (4) | 2018.01.02 |
| c++로 작성한 후위연산 계산기 (0) | 2017.12.29 |