[자료구조]스레드 적용한 이진탐색트리

09학년도 항공대 컴공과 2학년 자료구조 수업에 제출된 자료입니다   

  ▷ 헤더부

(BSTnode.h)

 

#ifndef _NODE_H_

#define _NODE_H_

#include "thredBST.h"

 

class thrededBST; // 전방선언

 

class BSTnode{

friend thrededBST; // 참조클래스

public:

BSTnode(); // 생성자

 

private:

BSTnode *LeftChild; // 왼쪽링크

int data; // 데이터링크

BSTnode *RightChild; // 오른쪽링크

};

#endif

(thredBST.h)

 

#ifndef _THRED_H_

#define _THRED_H_

 

#include "BSTnode.h"

 

class thrededBST{

private:

BSTnode *root;

int buff[20][20]; // 트리를그리기위한배열

 

public:

thrededBST(); // 생성자

void inorder();

void Inorder(BSTnode *); // 중위순회정렬

bool Insert(const int &); // data 입력

bool Delete(const int &); // data 삭제

void Search(const int &); // data 검색

void display();

void Display(BSTnode *); // data 출력

int DrawBST(int, int , int , BSTnode *);

// 트리를배열에그리는함수

};

 

#endif

 

 

▷ 구현부

#include <iostream>

#include "thredBST.h"

using namespace std;

 

BSTnode::BSTnode(){ // 생성자

data = 0; //

LeftChild = NULL;

RightChild = NULL;

}

 

thrededBST::thrededBST(){

for(int i = 0; i < 20; i++){

for(int j = 0; j < 20; j++){

buff[i][j] = 0;

}

}

root = NULL;

}

 

void thrededBST::inorder(){

Inorder(root);

}

 

void thrededBST::Inorder(BSTnode *CurrentNode){ //중위순회

 

if(CurrentNode){ // 트리의값이널이아닐때트리의값을을중위순회하여출력

Inorder(CurrentNode->LeftChild);

cout << CurrentNode->data << " "

Inorder(CurrentNode->RightChild);

}

}

 

bool thrededBST::Insert(const int &x){ // 입력

BSTnode *p = root; // p를q의부모로

BSTnode *q = 0;

 

while(p){

q=p;

 

if(x == p->data){ // 이미존재하는값이면false 반환

return false

}

if(x < p->data){ // 값이이미있는값보다작으면왼쪽

p = p->LeftChild;

}

else{ // 크다면오른쪽

p = p->RightChild;

}

}

 

p = new BSTnode; // 노드값을삽입

p->LeftChild = p->RightChild = 0;

p->data = x;

 

if(!root){ // 공백트리일때

root = p;

}

else if(x < q->data){

q->LeftChild = p;

}

else{

q->RightChild =p;

}

return true

}

 

bool thrededBST::Delete(const int &x){ // 삭제

BSTnode *p = root;

BSTnode *q = 0;

while(p){

if(x == p->data){ // x 값을찾으면loop 정지

break

}

if(x < p->data){

q = p;

p = p->LeftChild;

}

 

else{

q = p;

p = p->RightChild;

}

}

 

if(p == 0){

cout << "Threre is no delete data : " << x << endl;

return false

}

 

if(p->RightChild == 0 && p->LeftChild == 0){ // 리프노드삭제

if(q->LeftChild==p){

q->LeftChild = 0;

}

else{

q->RightChild = 0;

}

}

 

else if(p->LeftChild == 0 && p->RightChild != 0){ // 왼쪽노드가없는경우

if(p==root){ // p가root

root = p->RightChild;

}

else if(q->RightChild == p){ // q 의오른쪽노드가p이면

q->RightChild = p->RightChild;

}

else{ // 왼쪽이면

q->LeftChild = p->RightChild;

}

}

 

else if(p->LeftChild != 0 && p->RightChild == 0){ // 오른쪽노드가없는경우

if(p==root){

root = p->LeftChild;

}

else if(q->RightChild == p){ // q의오른쪽노드가p이면

q->RightChild = p->LeftChild;

}

else{ // 왼쪽이면

q->LeftChild = p->LeftChild;

}

}

 

else{ // 양쪽노드모두다존재하는비단말노드

BSTnode *r = p;

BSTnode *s = q;

s=r;

r = r->LeftChild;

 

while(r->RightChild == 0){ // r의오른쪽노드가끝날때까지

s = r;

r=r->RightChild;

}

 

p->data = r->data; // p에r의값을입력

// 리프노드삭제또는한개의노드만가지고있는비단말노드의삭제

if(r->LeftChild == 0){

if(s->LeftChild == r){

s->LeftChild=0;

}

else{

s->RightChild=0;

}

}

 

else{

if(s->RightChild == r){

s->RightChild = r->LeftChild;

}

else{

s->LeftChild = r->LeftChild;

}

}

}

 

return true

}

 

void thrededBST::display(){

Display(root);

}

 

void thrededBST::Display(BSTnode *CurrentNode){

 

int i, j;

 

if(!root->data){ // 빈트리인경우종료

cout<<"Tree is Empty"<<endl;

return

}

 

DrawBST(0, 0, 0, CurrentNode); // 배열에트리를그림

 

for(i = 0; i < 20; i++){ // 그려진트리를출력

for(j = 0; j < 20; j++){

if(buff[i][j] == 100) cout<<"─"

else if(buff[i][j] == 101) cout<<"│"

else if(buff[i][j] == 0) cout<<" "

else cout<<buff[i][j];

}

cout<<endl;

}

 

for(int i = 0; i < 20; i++){ // 값변경후출력을위해다시초기화

for(int j = 0; j < 20; j++){

buff[i][j] = 0;

}

}

}

 

int thrededBST::DrawBST(int nRightStart, int nRightFinish, int nLeft, BSTnode *pNode){ // 트리를배열상에그림

 

while(nRightStart < nRightFinish){ // 현재노드전의노드와연결가지를생성

buff[nLeft][nRightStart] = 100;

nRightStart++;

}

if(pNode){

buff[nLeft][nRightStart] = pNode->data;

 

// Draw Left Child

if(pNode->LeftChild){ // 왼쪽자식은아래로

int i = nLeft;

i++;

buff[i][nRightStart] = 101; // 가지그리기.

i++;

// 왼쪽자식이없을때까지.

nRightFinish = DrawBST(nRightStart, nRightFinish, i, pNode->LeftChild);

}

 

// Draw Right Child

if(pNode->RightChild){

nRightStart++;

nRightFinish += 2; // 오른쪽자식은옆으로

DrawBST(nRightStart, nRightFinish, nLeft, pNode->RightChild);

}

}

return nRightFinish;

}

 

void thrededBST::Search(const int &nKey){

BSTnode *Current;

Current = root; // 현재노드를시작으로nKey를탐색

 

while(Current){

 

if(Current->data == nKey){

cout << Current->data << "is exist" << endl; // 탐색성공하면그키값을리턴

break

}

 

else if(Current->data > nKey){

if(!Current->LeftChild){

cout << nKey << "is not exist" << endl;

break // 다음노드가존재하지않으면중단

}

Current = Current->LeftChild;

}

 

else{

if(!Current->RightChild){

cout << nKey << "is not exist" << endl;

break

}

Current = Current->RightChild;

}

}

}