코딩 공부 일기

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;

}

//삽입

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];

}

void BinaryTree::TraversalLevelorder(void)

{

        printf("레벨순회");

        NODE* indexNode;

        //큐 초기화

        m_Queue.Init();

        //루트노드 입력

        m_Queue.Put(m_root);

        //큐가 빌때까지 반복

        while (!m_Queue.IsEmpty())

        {

               //제일 먼저 입력된 노드 수령

               indexNode = m_Queue.Get();

               //방문(출력)

               PrintNode(indexNode->Data);

               //왼쪽 노드가 있다면 큐에 입력

               if (indexNode->Left != NULL)

                       m_Queue.Put(indexNode->Left);

               //오른쪽 노드가 있다면 큐에 입력

               if (indexNode->Right != NULL)

                       m_Queue.Put(indexNode->Right);

        }

        printf("\n");

}

//재귀함수를 이용한 중위 순회

void BinaryTree::Inorder_Recursion(NODE * node)

{

        if (node == NULL)

               return;

        //왼쪽 노드 재귀함수 실행

        Inorder_Recursion(node->Left);

        //자신 데이터 출력

        PrintNode(node->Data);

        //오른쪽 노드 재귀함수 실행

        Inorder_Recursion(node->Right);

}

//스택을 이용한 중위 순회

void BinaryTree::Inorder_Stack(NODE* rootNode)

{

        NODE *indexNode = rootNode;

        m_Stack.Clear();

        while (true)

        {

               //현재 노드에서 도달 할 수 있는 최좌측 노드 찾기 & 경로에 있는 노드들 저장

               while (indexNode != NULL)

               {

                       //현재 노드 저장

                       m_Stack.Push(indexNode);

                       //다음 좌측 노드 지정

                       indexNode = indexNode->Left;

               }

               //스택에 노드가 있다면

               if (!m_Stack.IsEmpty())

               {

                       //가장 늦게 이력된 노드 수령

                       indexNode = m_Stack.Pop();

                       //그 노드 데이터 출력

                       PrintNode(indexNode->Data);

                       //현재 노드의 우측노드를 다음 노드로 => 다음 반복에서 상위 While문에 있는 m_Stack.Push로 스택에 입력됨

                       indexNode = indexNode->Right;

               }

               else

                       break;

        }

}

//스택을 이용한 전위 순회

void BinaryTree::Preorder_Stack(NODE* rootNode)

{

        NODE* indexNode;

        m_Stack.Clear();

        //스택에 제일먼저 루트를 입력

        m_Stack.Push(rootNode);

        //스택이 빌때까지 반복

        while (!m_Stack.IsEmpty())

        {

               //스텍 최상단 노드 출력

               indexNode = m_Stack.Pop();

               //노드 데이터 프린트

               PrintNode(indexNode->Data);

               //오른쪽 노드가 있다면 스텍에 입력

               StackNode(indexNode->Right);

               //왼쪽 노드가 있다면 스텍에 입력 <= 후입선출(LIFO)이니까 먼저 출력됨

               StackNode(indexNode->Left);

        }

}