자료구조 (4) 썸네일형 리스트형 트리(이진트리순회) 트리는 일대다의 관계를 가지는 자료구조이다. 트리를 구현하면 나무모양을 닮아 트리라고 한다. 트리의 특징은 다음과 같다. 1. 노드 사이에 사이클이 존재하지 않는다. 2. 노드 사이에는 오직 하나의 경로만 존재한다. 트리는 비선형 구조이다. 앞서 설명한 스택, 리스트, 큐는 선형구조이다. 선형 구조는 순차적으로 데이터를 나열한 반면 비선형 구조는 데이터를 계층적으로 나열하였다. 트리를 구현하기 위해서는 먼저 트리의 용어를 알아야 한다. 1. 노드 : 트리를 구성하는 요소, 각각의 value값을 가지고 있다. 2. 엣지 : 노드와 노드 사이를 연결하는 하나의 경로, 부모와 자식을 연결한다. 3. 루트 노드 : 트리에서 맨 꼭대기에 존재하는 노드, 부모 노드가 없다. 4. 리프 노드 : 트리에서 맨 마지막에.. 큐(Queue) 큐는 뒤에서 데이터의 입력, 앞에서 데이터 삭제가 일어나는 자료구조이다. 데이터의 접근을 큐에 꼭대기와 바닥에서 일어나게 함으로 자료의 접근을 제한한다고 할 수 있다. 큐는 오직 인큐와 디큐를 이용하여 자료의 갱신이 가능하다. 인큐란 자료를 넣어서 저장하는 행동이고 디큐는 자료를 빼서 삭제하는 행동이다. 데이터의 삽입이 항상 뒤에서 일어나기 때문에 데이터의 삭제는 가장 나중에 들어온 자료에서 일어난다. 이러한 과정을 선입선출(FIFO)라고 한다. 큐는 실제 프로그램을 구현하는데도 많이 사용한다. 예를 들어 인쇄순서, 식권 프로그램 등이 있다. 다음은 선형으로 구현한 큐이다. 다음은 선형으로 배열을 이용하여 큐를 구현할 때 필요한 함수들이다. enque : 원소를 맨 뒤에 삽입하는 함수, 큐가 꽉 차있다면.. 스택(Stack) 스택은 꼭대기에서 데이터의 입출력이 일어나는 자료구조이다. 데이터의 접근을 스택 꼭대기에서만 일어나게 함으로 자료의 접근을 제한한다고 할 수 있다. 스택은 오직 푸쉬와 팝 연산을 이용하여 자료의 갱신이 가능하다. 푸쉬란 자료를 넣어서 저장하는 행동이고 팝은 자료를 빼서 삭제하는 행동이다. 이런 작업은 항상 데이터의 꼭대기에서 일어나기 때문에 빨리 저장될 수록 데이터의 수정이 빨라진다. 이러한 과정을 후입선출(LIFO)라고 한다. 스택은 실제 프로그램을 구현하는데도 많이 사용한다. 예를 들어 뒤로가기, 후위연산, 역순 문자열 만들기 등이 있다. 다음은 배열을 이용한 스택을 구현할 때 필요한 함수들이다. push : 원소를 맨 앞에 삽입하는 함수, 스택이 꽉 차있다면 원소를 넣지 않음, 원소를 하나씩 넣어줄.. 단순 연결 리스트(Single linked list) 연결리스트는 노드들이 모여서 다음 데이터를 가리키는 형태로 구성되어 있다. 각각의 노드는 노드가 가지고 있는 데이터와 다음 노드를 가리키는 포인터가 모여서 구성된다. 배열과 달리 연결리스트는 인덱스가 없기 때문에 삽입과 삭제를 위해 원하는 위치까지 노드를 이동해야 된다. 또한 배열과 다르게 자료형의 주소가 순차적이 아니라 임의의 주소로 정해진다. 리스트를 탐색하는 경우에도 원하는 값을 찾을 때 까지 노드를 이동해야 한다. 단순 연결리스트는 노드의 이동이 한쪽 방향으로 일어나는 리스트이다. 다음은 단순 연결 리스트를 구현할 때 필요한 함수들이다. insert : 노드를 추가하는 함수, 맨 앞에 노드를 추가하는 경우는 새로 추가한 노드가 head 노드가 되게 하고 원래 자리에 있던 노드를 새로 만든 노드에 .. 이전 1 다음
