이진 트리(Binary Tree)

 

 

 

 

 

 

 

• 트리의 주요 용어

 

 

 

 

 

 

루트(Root) : 최상위 노드(부모가 없는 노드), 루트 노드는 트리에 단 하나만 존재한다. 노드A가 루트 노드

 

리프(Leaf) : 최하위 노드(자식이 없는 노드), 리프 노드는 트리에 복수가 존재할 수 있다. B, E, C가 리프 노드

 

부모(Parent) : 어떤 노드의 상위 노드, 노드는 단 하나의 부모 노드만을 갖는다.

B와 C의 부모 노드 : A

D와 E의 부모 노드 : B

 

자식(Child) : 어떤 노드의 하위 노드, 자식 노드의 갯수는 구현에 따라 달라질 수 있지만, 이진 트리에선 최대 2개의 자식 노드만 갖는다.

A의 자식 노드 : B, C

B의 자식 노드 : D, E

 

형제(Sibling) : 같은 부모를 갖는 자식 노드들

B와 C

D와 E

 

 

 

• 트리의 순회 알고리즘(링크)

1. 전위 순회(Preorder Traverse)로 가기
2. 중위 순회(Inorder Traverse)로 가기
3. 후위 순회(Postorder Traverse)로 가기
4. 레벨 순회(Level Order Traverse)로 가기

 

 

• 전체 코드

※트리에 사용한 템플릿 스택(Stack)

#pragma once

#include "stdafx.h"

 

template<typename T>

class tStack

{

private:

        typedef struct _Node

        {

               T Data;

               struct _Node* Next;

 

               _Node()

               {

                       Data = NULL;

                       Next = NULL;

               }

 

               _Node(T data)

               {

                       Data = data;

                       Next = NULL;

               }

        } NODE;

 

private:

        NODE *m_top, *m_bottom;

 

public:

        tStack()

        {

               m_top = new NODE();

               m_bottom = new NODE();

 

               Init();

        }

 

        ~tStack()

        {

               Clear();

 

               delete m_top;

               delete m_bottom;

 

               m_top = NULL;

               m_bottom = NULL;

        }

 

        //스택 비우기

        void Clear(void)

        {

               NODE* indexNode = m_top->Next;

               for (indexNode; indexNode != m_bottom;)

               {

                       NODE* deleteNode = indexNode;

                       indexNode = indexNode->Next;

 

                       delete deleteNode;

                       deleteNode = NULL;

               }

 

               Init();

        }

 

        //입력

        void Push(T data)

        {

               //새 노드 생성 및 데이터 입력

               NODE *newNode = new NODE(data);

 

               //새 노드의 Next로 현재 제일 앞에 있는 노드를 지정

               newNode->Next = m_top->Next;

 

               //현재 노드를 제일 앞 노드로 지정

               m_top->Next = newNode;

        }

 

        //출력

        T Pop(void)

        {

               //첫 노드가 마지막 노드(m_bottom : 빈노드)면 데이터가 없음

               if (IsEmpty())

                       return NULL;

 

               //첫번째 노드 데이터 수령

               NODE *deleteNode = m_top->Next;

               T result = deleteNode->Data;

 

               //2번째 노드를 첫번째 노드로

               m_top->Next = m_top->Next->Next;

 

               //첫번째 노드 삭제

               delete deleteNode;

               deleteNode = NULL;    

 

               //결과 반환

               return result;

        }

 

       //삭제 없이 출력

        T Peek(void)

        {

               //첫 노드가 마지막 노드(m_bottom : 빈노드)면 데이터가 없음

               if (IsEmpty())

                       return NULL;

 

               //첫번째 노드 데이터 리턴

               return  m_top->Next->Data;

        }

 

        //비었는지 확인

        bool IsEmpty(void)

        {

               //첫 노드가 마지막 노드(m_bottom : 빈노드)면 데이터가 없음

               if (m_top->Next == m_bottom)

                       return true;

               else

                       return false;

        }

 

private:

        //초기화

        void Init(void)

        {

               m_top->Next = m_bottom;

               m_bottom->Next = m_bottom;

        }

};

 

※트리에 사용한 템플릿 큐(Queue)

#pragma once

#include "stdafx.h"

 

template<class T>

class tCircularQueue

{

private:

        T *m_Queue;                   //큐

        int m_Front;                  //제일 먼저 입력된 데이터의 위치

        int m_Rear;                   //가장 늦게 입력된 데이터의 다음위치 ->빈공간

        const int SIZE;

 

public:

        tCircularQueue(const int QueueSize) :SIZE(QueueSize)

        {

               m_Queue = new T[QueueSize];

               Init();

        }

 

        ~tCircularQueue()

        {

               delete[] m_Queue;

               m_Queue = NULL;

        }

 

        //초기화

        void Init(void)       

        {

               m_Front = 0;

               m_Rear = 0;

        }

 

        //데이터 삽입

        void Put(T data)

        {

               //Rear의 다음 위치 계산

               int nextIndex = (m_Rear + 1) % SIZE;

 

               //다음 위치가 Front위치라면 입력 중단->큐가 꽉찬 상태

               if (nextIndex == m_Front)

                       return;

 

               //현재 Rear위치에 데이터 입력

               m_Queue[m_Rear] = data;

 

               //Rear를 다음 칸으로 이동

               m_Rear = nextIndex;

        }

 

        //데이터 추출

        T Get(void)

        {

               //Front와 Rear가 같은 위치라면 -> 데이터가 없는 상태

               if (IsEmpty())

                       return NULL;

 

               //데이터 저장

               T result = m_Queue[m_Front];

 

               //Front를 한칸 뒤로 이동

               m_Front = (m_Front + 1) % SIZE;

 

               return result;

        }

 

        bool IsEmpty()

        {

               if (m_Front == m_Rear)

                       return true;

 

               return false;

        }

};

 

 

 

※트리 코드

#pragma once

#include "tStack.h"

#include "tCircularQueue.h"

 

class BinaryTree

{

private:

        typedef struct _Node

        {

               _Node(char data)

               {

                       Data = data;

                       Left = NULL;

                       Right = NULL;

               }

 

               char Data;

               struct _Node *Left;

               struct _Node *Right;

        }NODE;

 

private:

        NODE *m_root;

        tStack<NODE*> m_Stack;

        tCircularQueue<NODE*> m_Queue = tCircularQueue<NODE*>(16);

public:

        BinaryTree();

 

        ~BinaryTree();

 

        void Push(char);

 

        void TraversalPreorder(bool);                //전위 순회

        void TraversalInorder(bool);                 //중위 순회

        void TraversalPostorder(bool);               //후위 순회

        void TraversalLevelorder(void);              //레벨 순회

 

private:

        void Preorder_Stack(NODE*);                   //스택을 이용한 전위 순회

        void Preorder_Recursion(NODE*);               //재귀함수를 이용한 전위 순회

 

        void Inorder_Stack(NODE*);                    //스택을 이용한 중위 순회

        void Inorder_Recursion(NODE*);                //재귀함수를 이용한 중위 순회

 

        void Postorder_Stack(NODE*);                 //스택을 이용한 후위 순회

        void Postorder_Recursion(NODE*);             //재귀함수를 이용한 후위 순회

private:

        void PrintNode(char data);                   //노드 데이터 출력

        void StackNode(NODE*);                       //노드 스택에 입력(+NULL체크도)

};

 

#include "stdafx.h"

#include "BinaryTree.h"

 

 

BinaryTree::BinaryTree()

{

        m_root = NULL;

}

 

 

BinaryTree::~BinaryTree()

{

        m_Stack.Clear();

       

        delete m_root;

}

 

//트리에 데이터 입력

void BinaryTree::Push(char data)

{

        //루트가 NULL이라면 루트에 데이터 입력

        if (m_root == NULL)

        {

               m_root = new NODE(data);

               return;

        }

       

        //루트 노드부터 검색 시작

        NODE* indexNode = m_root;            

        while (true)

        {

               //중복 데이터 입력 방지

               if (indexNode->Data == data)

                       return;

 

               //입력 받은 데이터가 현재 노드의 데이터 보다 작다면 -> 왼쪽 노드 체크

               if (indexNode->Data > data)

               {

                       //자식 노드가 비어있다면, 노드 생성 & 데이터 입력

                       if (indexNode->Left == NULL)

                       {

                              indexNode->Left = new NODE(data);

                              break;

                       }

                       else//아니라면 index노드에 현재 왼쪽 자식 노드 입력

                              indexNode = indexNode->Left;

               }

               else //입력 받은 데이터가 현재 노드의 데이터 보다 크다면 -> 오른쪽 노드 체크

               {

                       //자식 노드가 비어있다면, 노드 생성 & 데이터 입력

                       if (indexNode->Right == NULL)

                       {

                              indexNode->Right = new NODE(data);

                              break;

                       }

                       else//아니라면 index노드에 현재 오른쪽 자식 노드 입력

                              indexNode = indexNode->Right;

               }

        }

}

 

//전위순회

void BinaryTree::TraversalPreorder(bool bUseStack)

{

        printf("전위순회");

 

        if (bUseStack)

               printf("[스택]"), Preorder_Stack(m_root);

        else

               printf("[재귀]"), Preorder_Recursion(m_root);

 

        printf("\n");

}

 

//중위 순회

void BinaryTree::TraversalInorder(bool bUseStack)

{

        printf("중위순회");

 

        if (bUseStack)

               printf("[스택]"), Inorder_Stack(m_root);

        else

               printf("[재귀]"), Inorder_Recursion(m_root);

       

 

        printf("\n");

}

 

//후위 순회

void BinaryTree::TraversalPostorder(bool bUseStack)

{

        printf("후위순회");

 

        if (bUseStack)

               printf("[스택]"), Postorder_Stack(m_root);

        else

               printf("[재귀]"), Postorder_Recursion(m_root);

 

 

        printf("\n");

}

 

//레벨 순회

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::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);

        }

}

 

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

void BinaryTree::Preorder_Recursion(NODE* node)

{

        if (node == NULL)

               return;

 

        //자신을 출력하고

        PrintNode(node->Data);

 

        //왼쪽 방문

        Preorder_Recursion(node->Left);

 

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

        Preorder_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::Inorder_Recursion(NODE * node)

{

        if (node == NULL)

               return;

 

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

        Inorder_Recursion(node->Left);

 

        //자신 데이터 출력

        PrintNode(node->Data);

 

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

        Inorder_Recursion(node->Right);

}

 

 

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

void BinaryTree::Postorder_Stack(NODE* node)

{

        m_Stack.Clear();

 

        while (true)

        {

               while (NULL != node)

               {

                      //현재 노드를 2번 입력

                       m_Stack.Push(node);

                       m_Stack.Push(node);

 

                       //왼쪽 노드로 이동

                       node = node->Left;

               }

 

               if (!m_Stack.IsEmpty())

               {

                       node = m_Stack.Pop();

 

                       //현재 노드의 첫번째 방문일때, 오른쪽으로 이동

                       if (!m_Stack.IsEmpty() && node == m_Stack.Peek())

                       {

                              node = node->Right;

                       }

                       //현재 노드를 두번째 방문 했을때 출력한다.

                       else

                       {

                              PrintNode(node->Data);

                              node = NULL;

                       }

               }

               else

               {

                       break;

               }

        }

}

 

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

void BinaryTree::Postorder_Recursion(NODE *node)

{

        if (node == NULL)

               return;

 

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

        Postorder_Recursion(node->Left);

 

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

        Postorder_Recursion(node->Right);

 

        //자신 데이터 출력

        PrintNode(node->Data);

}

 

//노드 데이터 프린트

void BinaryTree::PrintNode(char data)

{

        printf(" -> %c", data);

}

 

//스택에 노드 입력

void BinaryTree::StackNode(NODE *node)

{

        if (node != NULL)

               m_Stack.Push(node);

}

 

 

후위 순위(스택) 코드 출처: https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/