중위 순회
중위 순회 결과 : A -> B -> C -> D ->E -> F -> G -> H
-왼쪽을 가장 먼저 방문하며, 오른쪽 노드 방문전에 부모노드를 방문
-이진 탐색 트리에서 사용하면 크기 순서대로 나열됨
코드보기
-재귀함수를 이용한 중위 순회
-스택을 이용한 중위 순회
| 트리 순회 알고리즘#04 레벨 순회(Level Order Traversal) (0) | 2017.01.23 |
|---|---|
| 트리 순회 알고리즘#03 후위 순회(Postorder Traversal) (4) | 2017.01.23 |
| 트리 순회 알고리즘#01 전위 순회(Preorder Traversal) (0) | 2017.01.23 |
| 이진 트리(Binary Tree) (0) | 2017.01.23 |
| 큐(Queue) (0) | 2017.01.22 |
전위 순회
전위 순회 결과 : E -> B -> A -> D -> C -> G -> F -> H
-왼쪽을 우선으로 진행하며, 부모노드 방문 후 자식노드를 좌, 우 순서로 방문한다고 생각하면 쉽다.
코드보기
-재귀함수를 이용한 전위 순회
-스택을 이용한 전위 순회
| 트리 순회 알고리즘#03 후위 순회(Postorder Traversal) (4) | 2017.01.23 |
|---|---|
| 트리 순회 알고리즘#02 중위 순회(Inorder Traversal) (0) | 2017.01.23 |
| 이진 트리(Binary Tree) (0) | 2017.01.23 |
| 큐(Queue) (0) | 2017.01.22 |
| 스택(Stack) (0) | 2017.01.21 |
루트(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
#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;
}
};
#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/
| 트리 순회 알고리즘#02 중위 순회(Inorder Traversal) (0) | 2017.01.23 |
|---|---|
| 트리 순회 알고리즘#01 전위 순회(Preorder Traversal) (0) | 2017.01.23 |
| 큐(Queue) (0) | 2017.01.22 |
| 스택(Stack) (0) | 2017.01.21 |
| 이중 링크드 리스트(Doubly Linked List) (1) | 2017.01.20 |
