BinSrchTree_Dictionary.h : 사전 클래스를 위한 이진 탐색 트리 클래스 #오류가 있음

#ifndef ___BinSrchTree_Dictionary

#define ___BinSrchTree_Dictionary

//BinSrchTree_Dictionary.h : 사전 클래스를 위한 이진 탐색 트리 클래스

#include "BinaryTree_Dictionary.h"

class BinSrchTree : public BinaryTree {

public:

BinSrchTree(void) {}

~BinSrchTree(void) {}

//이진 탐색 트리의 탐색 연산

BinaryNode* search(const char* key) { return searchRecur(root, key); }

//키 값으로 노드를 탐색하는 함수 (순환적인 방법)

//n을 루트로 갖는 서브트리에서 key를 키값으로 갖는 노드 탐색 함수

BinaryNode* searchRecur(BinaryNode *n,const char* key) {

if (n == NULL)return NULL; //n이 NULL

if (n->compare(key) == 0) //key == 현재노드의 data

return n;

else if (n->compare(key) < 0) //key < 현재노드의 data

return searchRecur(n->getLeft(), key);

else

return searchRecur(n->getRight(), key); //key > 현재노드의 data

}

//이진 탐색 트리의 삽입 연산

void insert(BinaryNode* n) {

if (n == NULL) return;

if (isEmpty()) root = n;

else insertRecur(root, n);

}

//일반 함수로 구현(순환적인 방법)

//r을  루트로 갖는 서브트리에 새로운 노드 n을 삽입하는 함수

void insertRecur(BinaryNode* r, BinaryNode* n) {

if (n->compare(r) == 0)

return;

else if (n->compare(n) > 0) {

if (r->getLeft() == NULL)

r->setLeft(n);

else

insertRecur(r->getLeft(), n);

}

else {

if (r->getRight() == NULL)

r->setRight(n);

else

insertRecur(r->getRight(), n);

}

}

//이진 탐색 트리의 삭제 연산

void remove(char* data) {

if (isEmpty()) return; //빈 트리이면 return

//없앨 노드와 그 노드의 부모 노드를 찾는다.

BinaryNode* parent = NULL; //없앨 노드의 부모

BinaryNode* node = root; //없앨 노드

while (node != NULL && node->compare(data)!=0) {

parent = node;

node = (node->compare(data) < 0)

? node->getLeft() : node->getRight();

}

//없앨 노드가 트리에 없음

if (node == NULL) {

printf(" Error : key is not in the tree!\n");

}

//없앨 노드가 트리에 있음

else remove(parent, node);

}

//parent를 부모로 갖는 노드 node를 이진 탐색 트리에서 삭제하는 함수

void remove(BinaryNode* parent, BinaryNode* node) {

//case 1: 삭제하려는 노드가 단말 노드일 경우

if (node->isLeaf()) {

if (parent == NULL) // node == root인 경우 => 공백상태가 됨

root = NULL;

else {

if (parent->getLeft() == node)

parent->setLeft(NULL);

else parent->setRight(NULL);

}

}

//case 2: 삭제하려는 노드가 왼쪽이나 오른쪽 자식만 갖는 경우

else if (node->getLeft() == NULL || node->getRight() == NULL) {

//삭제할 노드의 유일한 자식 노드 =>child

BinaryNode* child = (node->getLeft() != NULL)

? node->getLeft() : node->getRight();

//삭제할 노드가 루트이면 ==> child가 새로운 root가 됨

if (node == root) root = child;

//아니면 ==> 부모 노드의 자식 노드 child를 직접 연결

else {

if (parent->getLeft() == node)

parent->setLeft(child);

else

parent->setRight(child);

}

}

//case 3: 삭제하려는 노드가 두개의 자식이 모두 있는 경우

else {

//삭제하려는 노드의 오른쪽 서브트리에서 가장 작은 노드를 탐색

//succ => 후계 노드: 오른쪽 서브트리에서 가장 key가 작은 노드

//succp => 후계 노드의 부모 노드

BinaryNode* succp = node;

BinaryNode* succ = node->getRight();

while (succ->getLeft() != NULL) { //후계 노드 탐색

succp = succ; //후계 노드의 부모 노드

succ = succ->getLeft(); //후계 노드

}

//후계 노드의 부모와 후계 노드의 오른쪽 자식을 직접 연결

if (succp->getLeft() == succ)

succp->setLeft(succ->getRight());

else                                //후계 노드가 삭제할 노드의 바로 오른쪽 자식인 경우

succp->setRight(succ->getLeft());

//후계 노드 정보를 삭제할 노드에 복사

node->copy(succ);

//삭제할 노드를 후계 노드로 변경 : 실제로는 후계 노드가 제거됨

node = succ;

}

delete node; //메모리 동적 해제

}

};

#endif // !___BinSrchTree