코딩 공부 일기

접기

void BinarySearchTree::Insert(int key)

{

        //트리가 비어있다면 루트 생성

        if (IsEmpty())

        {

               m_root->Right = new NODE(key);

               return;

        }

 

        NODE* parent = m_root;        //부모 노드

        NODE* node = m_root->Right;   //현재 탐색 노드    

 

        //입력 가능한 곳 검색

        do

        {

               //중복된 키 값은 입력 불가

               if (node->Key == key)

                       return;

 

               parent = node;

               node = (key < parent->Key) ? parent->Left : parent->Right;

 

        } while (node != NULL);

 

        //새 노드 생성

        node = new NODE(key);

 

        //부모보다 작으면 왼쪽

        if (key < parent->Key)

               parent->Left = node;

        //부모보다 크면 오른쪽

        else

               parent->Right = node;

 

}

접기

접기

접기

접기

//자식이 한쪽만 있는 노드 삭제

        else if (deleteNode->Left == NULL || deleteNode->Right == NULL)

        {

               //삭제노드의 자식 확인

               node = deleteNode->Left != NULL ? deleteNode->Left : deleteNode->Right;

                             

               //삭제노드 위치에 삭제노드의 자식을 위치

               if (parent->Key > key)

                       parent->Left = node;   

               else

                       parent->Right = node;  

        }

접기

접기

//자식이 양쪽 다 있는 노드 삭제

        //삭제할 노드의 왼쪽 자식 중 가장 큰 노드를 찾아

        //삭제할 노드의 위치에 둔다.

        else

        {             

               parent = deleteNode;            //최대값 노드의 부모 노드

               node = parent->Left;            //최대값 노드

              

               //왼쪽 자식 중 가장 큰 노드 찾기

               while (node->Right != NULL)

               {

                       parent = node;

                       node = node->Right;

               }

 

               //왼쪽에서 가장 큰 노드가 자식이 있다면

               if (node->Left != NULL)

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if(parent->Left == node)

                              parent->Left = node->Left;

                       else

                              parent->Right = node->Left;

               }

               //왼쪽에서 가장 큰 노드가 자식이 없다면

               else

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if (parent->Left == node)

                              parent->Left = NULL;

                       else

                              parent->Right = NULL;

               }

 

               //삭제할 노드의 데이터를 위에서 찾은 최대값으로

               deleteNode->Key = node->Key;

 

               //최대값 노드를 삭제 노드로

               deleteNode = node;

        }

접기

접기

void BinarySearchTree::Delete(int key)

{

        //트리가 비어있다면 중지

        if (IsEmpty())

               return;

 

        NODE* parent = m_root;          //부모 노드

        NODE* node = m_root->Right;     //자식 노드

        NODE* deleteNode;               //삭제 노드

 

        //검색

        do

        {

               if (node->Key == key)   //노드를 찾았다면 중지

                       break;

 

               //현재 노드를 부모 노드로

               parent = node;

 

               //다음 탐색 노드 설정

               node = (parent->Key > key) ? parent->Left : parent->Right;

 

        } while (node != NULL);

 

        //삭제할 노드가 없다면 중지

        if (node == NULL)

               return;

       

        //삭제할 노드 저장

        deleteNode = node;

 

        //자식이 없는 노드 삭제

        if (deleteNode->Left == NULL && deleteNode->Right == NULL)

        {

               if (parent->Key > key)

                       parent->Left = NULL;    //왼쪽 노드 삭제

               else

                       parent->Right = NULL;   //오른쪽 노드 삭제

        }

 

        //자식이 한쪽만 있는 노드 삭제

        else if (deleteNode->Left == NULL || deleteNode->Right == NULL)

        {

               //삭제노드의 자식 확인

               node = deleteNode->Left != NULL ? deleteNode->Left : deleteNode->Right;

                             

               //삭제노드 위치에 삭제노드의 자식을 위치

               if (parent->Key > key)

                       parent->Left = node;   

               else

                       parent->Right = node;  

        }

 

        //자식이 양쪽 다 있는 노드 삭제

        //삭제할 노드의 왼쪽 자식 중 가장 큰 노드를 찾아

        //삭제할 노드의 위치에 둔다.

        else

        {             

               parent = deleteNode;            //최대값 노드의 부모 노드

               node = parent->Left;            //최대값 노드

              

               //왼쪽 자식 중 가장 큰 노드 찾기

               while (node->Right != NULL)

               {

                       parent = node;

                       node = node->Right;

               }

 

               //왼쪽에서 가장 큰 노드가 자식이 있다면

               if (node->Left != NULL)

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if(parent->Left == node)

                              parent->Left = node->Left;

                       else

                              parent->Right = node->Left;

               }

               //왼쪽에서 가장 큰 노드가 자식이 없다면

               else

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if (parent->Left == node)

                              parent->Left = NULL;

                       else

                              parent->Right = NULL;

               }

 

               //삭제할 노드의 데이터를 위에서 찾은 최대값으로

               deleteNode->Key = node->Key;

 

               //최대값 노드를 삭제 노드로

               deleteNode = node;

        }

 

        //노드 삭제

        delete deleteNode;

        deleteNode = NULL;

}

접기

접기

#pragma once

class BinarySearchTree

{

private:

        typedef struct _Node

        {

               _Node(int key)

               {

                       Key = key;

                       Left = NULL;

                       Right = NULL;

               }

 

               int Key;

               struct _Node *Left;

               struct _Node *Right;

        }NODE;

 

private:

        NODE *m_root;

 

public:

        BinarySearchTree();

        ~BinarySearchTree();

 

        void Insert(int);

        NODE* Search(int);

        void Delete(int);

        void Print();

        bool IsEmpty();

        void Clear();

private:

        void Preorder(NODE*);

        void PrintNode(NODE*);

        void Clear(NODE*);

};

접기

접기

#include "stdafx.h"

#include "BinarySearchTree.h"

 

 

BinarySearchTree::BinarySearchTree()

{

        //루트 생성(실질적인 루트가 아님)

        //m_root->Right가 진짜 루트

        m_root = new NODE(-1);  

}

 

 

BinarySearchTree::~BinarySearchTree()

{

        Clear();

 

        delete m_root;

        m_root = NULL;

}

 

void BinarySearchTree::Insert(int key)

{

        //트리가 비어있다면 루트에 입력

        if (IsEmpty())

        {

               m_root->Right = new NODE(key);

               return;

        }

 

        NODE* parent = m_root;

        NODE* node = m_root->Right;

 

        //입력 가능한 곳 검색

        do

        {

               //중복된 키 값은 입력 불가

               if (node->Key == key)

                       return;

 

               parent = node;

               node = (key < parent->Key) ? parent->Left : parent->Right;

 

        } while (node != NULL);

 

        //새 노드 생성

        node = new NODE(key);

 

        //부모보다 작으면 왼쪽

        if (key < parent->Key)

               parent->Left = node;

        //부모보다 크면 오른쪽

        else

               parent->Right = node;

 

}

 

BinarySearchTree::NODE* BinarySearchTree::Search(int key)

{

        //트리가 비어있다면 중지

        if (IsEmpty())

               return NULL;

 

        NODE* node = m_root->Right;

       

        while (node != NULL)

        {

               if (node->Key == key)

                       return node;

 

               node = (node->Key > key) ? node->Left : node->Right;

        }

 

        return NULL;

}

 

void BinarySearchTree::Delete(int key)

{

        //트리가 비어있다면 중지

        if (IsEmpty())

               return;

 

        NODE* parent = m_root;          //부모 노드

        NODE* node = m_root->Right;      //자식 노드

        NODE* deleteNode;                      //삭제 노드

 

        //검색

        do

        {

               if (node->Key == key)   //노드를 찾았다면 중지

                       break;

 

               //현재 노드를 부모 노드로

               parent = node;

 

               //다음 탐색 노드 설정

               node = (parent->Key > key) ? parent->Left : parent->Right;

 

        } while (node != NULL);

 

        //삭제할 노드가 없다면 중지

        if (node == NULL)

               return;

       

        //삭제할 노드 저장

        deleteNode = node;

 

        //자식이 없는 노드 삭제

        if (deleteNode->Left == NULL && deleteNode->Right == NULL)

        {

               if (parent->Key > key)

                       parent->Left = NULL;    //왼쪽 노드 삭제

               else

                       parent->Right = NULL;   //오른쪽 노드 삭제

        }

 

        //자식이 한쪽만 있는 노드 삭제

        else if (deleteNode->Left == NULL || deleteNode->Right == NULL)

        {

               //삭제노드의 자식 확인

               node = deleteNode->Left != NULL ? deleteNode->Left : deleteNode->Right;

                             

               //삭제노드 위치에 삭제노드의 자식을 위치

               if (parent->Key > key)

                       parent->Left = node;   

               else

                       parent->Right = node;  

        }

 

        //자식이 양쪽 다 있는 노드 삭제

        //삭제할 노드의 왼쪽 자식 중 가장 큰 노드를 찾아

        //삭제할 노드의 위치에 둔다.

        else

        {             

               parent = deleteNode;            //최대값 노드의 부모 노드

               node = parent->Left;            //최대값 노드

              

               //왼쪽 자식 중 가장 큰 노드 찾기

               while (node->Right != NULL)

               {

                       parent = node;

                       node = node->Right;

               }

 

               //왼쪽에서 가장 큰 노드가 자식이 있다면

               if (node->Left != NULL)

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if(parent->Left == node)

                              parent->Left = node->Left;

                       else

                              parent->Right = node->Left;

               }

               //왼쪽에서 가장 큰 노드가 자식이 없다면

               else

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if (parent->Left == node)

                              parent->Left = NULL;

                       else

                              parent->Right = NULL;

               }

 

               //삭제할 노드의 데이터를 위에서 찾은 최대값으로

               deleteNode->Key = node->Key;

 

               //최대값 노드를 삭제 노드로

               deleteNode = node;

        }

 

        //노드 삭제

        delete deleteNode;

        deleteNode = NULL;

}

 

void BinarySearchTree::Print()

{

        if (IsEmpty())

        {

               printf("트리 비어 있음\n");

               return;

        }

 

        printf("전위순회");

 

        Preorder(m_root->Right);

 

        printf("\n");

}

 

bool BinarySearchTree::IsEmpty()

{

        if (m_root->Right == NULL)

               return true;

        else

               return false;

}

 

void BinarySearchTree::Clear()

{

        if (IsEmpty())

               return;

 

        Clear(m_root->Right);

 

        m_root->Right = NULL;

}

 

void BinarySearchTree::Preorder(NODE *node)

{

        if (node == NULL)

               return;

 

        //자신을 출력하고

        PrintNode(node);

 

        //왼쪽 방문

        Preorder(node->Left);

 

        //마지막으로 오른쪽 방문

        Preorder(node->Right);

}

 

//노드 데이터 프린트

void BinarySearchTree::PrintNode(NODE* node)

{

        printf(" -> K:%d", node->Key);

}

 

void BinarySearchTree::Clear(NODE *node)

{

        if (node == NULL)

               return;

 

        Clear(node->Left);

 

        Clear(node->Right);

 

        node->Left = NULL;

        node->Right = NULL;

 

        delete node;

        node = NULL;

}

접기

접기

//힙 정렬

//*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수)

void Sort::HeapSort(int * Array, const int Length)

{

        //힙 사이즈 조절 & 초기화

        m_Heap.Resize(Length);

 

        //힙에 데이터 입력

        for (int i = 0; i < Length; i++)

               m_Heap.Insert(Array[i]);

 

        //힙에서 데이터 다시 수령하여 입력

        //오름차순 정렬을 위해 최소 힙 사용(최대 힙을 사용하고, 데이터를 역순으로 넣어도 된다)

        for (int i = 0; i < Length; i++)

               Array[i] = m_Heap.Get();

}

접기

접기

//삽입

void Heap::Insert(int data)

{

        //힙이 가득 찼는지 확인

        if (IsFull())

               return;

 

        //가장 뒷쪽에 데이터 삽입

        m_Heap[m_Last] = data;

                             

        //처음 삽입된 데이터가 아니라면, 업힙 수행

        if (IsEmpty() == false)

               UpHeap(m_Last);

 

        //last를 뒤로 한칸 밀어냄

        m_Last++;

}

 

//데이터를 위로 밀어냄

void Heap::UpHeap(int index)

{

        //현재 데이터의 부모 데이터

        int parent = PARENT(index);

 

        //최대 힙

        ////자신보다 더 큰 부모를 찾을때까지 반복

        while (m_Heap[parent] < m_Heap[index])

        {

               //부모와 자신의 위치 교환

               SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

               index = parent;                           //위치

 

               //현재 위치에서 부모 위치 계산                                                               

               parent = PARENT(index);

        }

 

 

        //최소 힙

        //자신보다 더 작은 부모를 찾을때까지 반복

        //while (m_Heap[parent] > m_Heap[index])

        //{

        //      //부모와 자신의 위치 교환

        //      SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

        //      index = parent;                           //위치

 

        //      //현재 위치에서 부모 위치 계산

        //      parent = PARENT(index);

        //}

}

접기

접기

//출력(혹은 삭제)

int Heap::Get(void)

{

        //힙이 비었으면 수행 안함

        if (IsEmpty())

               return -999999;

 

        //리턴할 데이터 저장, ROOT = 0 <= 즉, 첫번째 데이터

        int data = m_Heap[ROOT];

              

        //가장 마지막에 위치함 데이터를 첫번째 위치로 이동

        m_Heap[ROOT] = m_Heap[--m_Last];

 

        //다운 힙 수행

        DownHeap(ROOT);

 

        return data;

}

 

//데이터를 아래로 밀어냄

void Heap::DownHeap(int index)

{

        //위치를 교환할 자식의 위치

        int child = 0;

 

        //왼쪽 자식

        int left = LEFT(index);

 

        //오른쪽 자식의 위치

        int right = RIGHT(index);

 

        //최대 힙

        while (left < m_Last)

        {

 

               //오른쪽 자식이 있다면, 좌우 자식을 비교해 큰 자식을 고름

               if (right < m_Last)

                       child = m_Heap[left] > m_Heap[right] ? left : right;

               else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

                       child = left;

 

               //자식들 중 큰 수와 비교해, 밀어내릴 대상이 더 크다면 반복 종료

               if (m_Heap[index] >= m_Heap[child])

                       break;

 

               //자식과 대상을 교환

               SWAP(int, m_Heap[index], m_Heap[child]);

 

               //자식의 위치를 현재 위치로

               index = child;

 

               left = LEFT(index);             //왼쪽 자식 위치

               right = RIGHT(index);   //오른쪽 자식 위치

        }

 

 

        //최소 힙

        //while (left < m_Last)

        //{

        //      //오른쪽 자식이 있다면, 좌우 자식을 비교해 작은 자식을 고름

        //      if (right < m_Last)

        //             child = m_Heap[left] < m_Heap[right] ? left : right;

        //      else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

        //             child = left;

 

        //      //자식들 중 작은 수와 비교해, 밀어내릴 대상이 더 작다면 반복 종료

        //      if (m_Heap[index] <= m_Heap[child])

        //             break;

 

        //      //자식과 대상을 교환

        //      SWAP(int, m_Heap[index], m_Heap[child]);

 

        //      //자식의 위치를 현재 위치로

        //      index = child;

 

        //      left = LEFT(index);             //왼쪽 자식 위치

        //      right = RIGHT(index);   //오른쪽 자식 위치

        //}

}

접기

접기

#pragma once

 

//매크로 함수들

#define ROOT 0

#define PARENT(n) (n-1)/2  //부모 위치

#define LEFT(n) 2*n + 1    //왼쪽 자식 위치

#define RIGHT(n) 2*n + 2   //오른쪽 자식 위치

//교환

#define SWAP(type, a, b) do{ \

    type temp = a;      \

    a = b;                     \

    b = temp;           \

}while(false)

 

class Heap

{

public:

        Heap();

        Heap(int size);

        ~Heap();

 

private:

        int *m_Heap;            //데이터들 저장할 공간

        int m_Last;             //현재 마지막 자료의 위치 + 1(빈 위치)

        int m_Size;             //최대 사이즈

 

public:

        bool IsEmpty(void);     //힙이 비었는지 확인

        bool IsFull(void);      //힙이 가득 찼는지 확인

        void Insert(int);       //삽입

        int  Get(void);         //데이터 수령

        void Print(void);       //프린트

 

        void Resize(int size);   //배열 크기 다시설정

        void Clear();            //다시 사용가능한 상태로

        void Reset();            //다시 사용가능한 상태로

private:

        void UpHeap(int);        //업힙 : 데이터를 위로 밀어냄

        void DownHeap(int);      //다운힙 : 데이터를 아래로 밀어냄

        void SetSize(int size);  //사이즈 지정

};

접기

접기

#include "stdafx.h"

#include "Heap.h"

 

 

Heap::Heap()

{

        Reset();

 

        SetSize(10);

}

 

Heap::Heap(int size)

{

        Reset();

 

        SetSize(size);

}

 

 

Heap::~Heap()

{

        Clear();

}

 

//힙이 비었는지 확인

bool Heap::IsEmpty(void)

{

        //last가 0이면 데이터가 없음

        if (m_Last == 0)

               return true;

        else

               return false;

}

 

//힙이 가득 찼는지 확인

bool Heap::IsFull(void)

{

        //last와 최대크기가 같으면, 가득찬 것

        if (m_Last == m_Size)

               return true;

        else

               return false;

}

 

//삽입

void Heap::Insert(int data)

{

        //힙이 가득 찼는지 확인

        if (IsFull())

               return;

 

        //가장 뒷쪽에 데이터 삽입

        m_Heap[m_Last] = data;

 

        //처음 삽입된 데이터가 아니라면, 업힙 수행

        if (IsEmpty() == false)

               UpHeap(m_Last);

 

        //last를 뒤로 한칸 밀어냄

        m_Last++;

}

 

//데이터 수령

int Heap::Get(void)

{

        //힙이 비었으면 수행 안함

        if (IsEmpty())

               return -999999;

 

        //리턴할 데이터 저장, ROOT = 0 <= 즉, 첫번째 데이터

        int data = m_Heap[ROOT];

 

        //가장 마지막에 위치함 데이터를 첫번째 위치로 이동

        m_Heap[ROOT] = m_Heap[--m_Last];

 

        //다운 힙 수행

        DownHeap(ROOT);

 

        return data;

}

 

//데이터를 위로 밀어냄

void Heap::UpHeap(int index)

{

        //현재 데이터의 부모 데이터

        int parent = PARENT(index);

 

        //최대 힙

        ////자신보다 더 큰 부모를 찾을때까지 반복

        while (m_Heap[parent] < m_Heap[index])

        {

               //부모와 자신의 위치 교환

               SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

               index = parent;                                                       //위치

 

                                                                                                   //현재 위치에서 부모 위치 계산                                                               

               parent = PARENT(index);

        }

 

 

        //최소 힙

        ////자신보다 더 큰 부모를 찾을때까지 반복

        //while (m_Heap[parent] > m_Heap[index])

        //{

        //      //부모와 자신의 위치 교환

        //      SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

        //      index = parent;                                                       //위치

 

        //                                                                                          //현재 위치에서 부모 위치 계산                                                               

        //      parent = PARENT(index);

        //}

}

 

//데이터를 아래로 밀어냄

void Heap::DownHeap(int index)

{

        //위치를 교환할 자식의 위치

        int child = 0;

 

        //왼쪽 자식

        int left = LEFT(index);

 

        //오른쪽 자식의 위치

        int right = RIGHT(index);

 

        //최대 힙

        while (left < m_Last)

        {

               //left = LEFT(index);           //왼쪽 자식 위치

               right = RIGHT(index);   //오른쪽 자식 위치

 

                                                             //오른쪽 자식이 있다면, 좌우 자식을 비교해 큰 자식을 고름

               if (right < m_Last)

                       child = m_Heap[left] > m_Heap[right] ? left : right;

               else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

                       child = left;

 

               //자식들 중 큰 수와 비교해, 밀어내릴 대상이 더 크다면 반복 종료

               if (m_Heap[index] >= m_Heap[child])

                       break;

 

               //자식과 대상을 교환

               SWAP(int, m_Heap[index], m_Heap[child]);

 

               //자식의 위치를 현재 위치로

               index = child;

 

               left = LEFT(index);             //왼쪽 자식 위치

               right = RIGHT(index);   //오른쪽 자식 위치

        }

 

 

        //최소 힙

        //while (left < m_Last)

        //{

        //      //오른쪽 자식이 있다면, 좌우 자식을 비교해 작은 자식을 고름

        //      if (right < m_Last)

        //             child = m_Heap[left] < m_Heap[right] ? left : right;

        //      else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

        //             child = left;

 

        //      //자식들 중 작은 수와 비교해, 밀어내릴 대상이 더 작다면 반복 종료

        //      if (m_Heap[index] <= m_Heap[child])

        //             break;

 

        //      //자식과 대상을 교환

        //      SWAP(int, m_Heap[index], m_Heap[child]);

 

        //      //자식의 위치를 현재 위치로

        //      index = child;

 

        //      left = LEFT(index);             //왼쪽 자식 위치

        //      right = RIGHT(index);   //오른쪽 자식 위치

        //}

}

 

void Heap::Print(void)

{

        for (int i = 0; i < m_Last; i++)

               printf("%d ", m_Heap[i]);

 

        printf("\n");

}

 

// 배열 크기 다시설정

void Heap::Resize(int size)

{

        Clear();

 

        SetSize(size);

 

        Reset();

}

 

//데이터 삭제

void Heap::Clear()

{

        delete[] m_Heap;

        m_Heap = NULL;

}

 

//다시 사용가능한 상태로

void Heap::Reset()

{

        m_Last = 0;

}

 

//배열 크기 지정

void Heap::SetSize(int size)

{

        m_Size = size;

        m_Heap = new int[m_Size];

}

접기