Data Structure

트리의 순회 방법에 대해 알아보기에 앞서 트리에 대한 기본적인 배경지식은 아래의 포스팅을 참고하면 좋을 것 같다. https://go2gym365.tistory.com/274 [자료구조] Tree & Binary Tree 1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지 go2gym365.tistory.com 1. 전위 순회 / PreOrder 순회 순서 : [ 루트 노드(부모 노드) > 왼쪽 노드 > 오른쪽 노드] 순서로 방문한다. 위의 그림에서 전위 순회한 결과 : [1 > 2 > 4 > 8 > 5 > 3 > 6 > 7 ] 2. 중위 순회 / InOr..

트리에 대한 기본적인 배경지식은 아래의 포스팅을 참고하면 좋을 것 같다. https://go2gym365.tistory.com/274 [자료구조] Tree & Binary Tree 1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지 go2gym365.tistory.com 1. Node 구조체 노드는 값과 자식 노드로 left, right노드를 가지고 있다. struct Node { int data; Node* left; Node* right; Node() { left = nullptr; right = nullptr; } }; 2. Binary Tree Cl..

1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지고있고 무한히 반복가능하다. 컴퓨터의 디렉터리 구조가 대표적인 트리 구조로 이루어져 있다! 1-2. Tree 용어 루트 노드(root node) : 부모가 없는 노드. 트리에는 오직 하나의 루트 노드만이 존재한다. 리프 노드, 단말 노드(leaf node, terminal node) : 자식이 없는 최말단 노드 내부 노드, 비단말 노드(internal node, nonterminal node) : 단말 노드를 제외한 나머지 노드 가지, 링크(branch, link, edge) : 노드와 노드를 연결하는 선...

1. 단일 연결 리스트란? 각 요소들이 데이터부분과 다음 값 주소를 포인팅하는 노드라는 형태로 이루어져 있으며 체인 형태로 선형으로 이루어진 자료구조이다. 값을 추가할 때 배열은 정해진 사이즈를 넘으면 Overflow가 발생하지만 Linked List는 동적으로 할당해서 노드들을 이어주면 되기 때문에 메모리 사이즈 문제에서 벗어날 수 있다. 하지만 노드들이 서로 체인형태로 이어져 있어 배열처럼 인덱스 개념으로 접근이 불가하기 때문에 순회하여 값을 찾아야 하으로 탐색에 있어서는 배열보다 느리다. 하지만 값을 중간에 넣는 경우 배열은 중간에 값을 삽입하고 한칸씩 뒤로 미뤄줘야 하기 때문에 원소의 갯수에 따라 시간이 차이가 나는 방면, 연결 리스트의 경우 단지 노드의 포인팅만 바꿔주면 되기 때문에 최악의 경우..

1. Queue란? 선입 선출(First In First Out) 즉 먼저 들어간 데이터가 제일 먼저 나오는 성질을 가지는 자료구조이다. 우리의 실생활에서 가장 많이 볼 수 있다. ex) 대기열, 프린터 큐 시간 복잡도 : O(1) 2. Queue 구현 구현해본 기능은 1. Push : 원소를 큐에 넣음 2. Pop : 큐에 가장 먼저 들어간 원소를 제거 3. Front : 큐에 가장 먼저 들어간 원소를 출력 4. Size : 큐에 들어가있는 원소의 갯수를 출력 5. IsEmpty : 큐가 비었는지 확인 6. IsFull : 큐가 다 찼는지 확인 나는 처음에 사용자한테 queue의 사이즈를 입력받아서 구현했고, 원형 큐 형태로 구현했기 때문에 실제로 사용자가 입력한 큐의 사이즈보다 -1만큼 적게 사용한다..

1. Stack이란? 후입선출(Last In First Out) 즉 나중에 들어간 데이터가 제일 먼저 나오는 성질을 가지는 자료구조이다. 시간복잡도 : O(1) 2. Stack구현 Push(int value) : value를 스택의 최상단에 삽입 Pop() : 최상단의 원소를 스택에서 제거. 만약 스택이 비었다면 프로그램 종료 Top() : 스택의 최상위 원소를 반환. 만약 스택이 미었다면 프로그램 종료 Size() : 스택의 원소의 갯수를 반환. isEmpty() : 스택이 비어있는지 여부를 반환. #include #include using namespace std; class Stack{ private: int *arr; int top; int capacity; public: Stack(int siz..