본문 바로가기

컴퓨터과학개론_이관용, 정광식16

2.5.2 이진트리 2.5.2 이진트리 이진트리(binary tree) - 모든 노드의 차수가 최대 2를 넘지 않는 트리. 이진트리의 모든 노드 - 최대 2개의 서브트리(왼쪽 서브트리와 오른쪽 서브트리 - 왼쪽 노드와 오른쪽 노드에 ‘순서’ 부여) 이진트리의 특성 - N개의 노드를 가진 이진트리의 최대 높이와 최소 높이를 계산 가능. 이진트리의 최대 높이는 N개의 노드를 사용해서 왼쪽 또는 오른쪽으로 치우친 이진트리(경사 이진트리)를 형성하는 경우. - 노드의 개수와 같은 N 이진트리의 최소 높이 - 각 노드가 최대 2개의 자식 노드를 채워서 갖는 경우 - [logN] +1이 최소 높이 이진트리에 대한 주요 연산 - 삽입, 삭제, 순회 순회(traverse) - 이진트리의 순회 연산은 일정한 순서에 따라 트리에 있는 각 노.. 2022. 11. 27.
2.5 트리 2.5.1 트리의 개념 트리 - 데이터 간의 관계를 나타내는 중요한 비선형 자료구조. 예) 족보(가계도), 기업이나 학교의 조직도 트리는 데이터가 저장되는 노드(node)와 노드를 연결하는 가지(branch, edge)로 구성. • 노드- 계층적인 관계 • 트리 - 정보 항목과 가지를 합친 것. • 루트(root) - 빈 트리(노드의 개수가 0인 트리)가 아닌 경우에 맨 꼭대기에 있는 하나의 노드. • 차수(degree) - 각 노드에 있는 아래로 향하는 가지의 수. • 트리의 차수 - 트리의 모든 노드의 차수 중에서 제일 큰 차수. • 단말 노드(terminal node) / 잎 노드(leaf node)- 노드의 차수가 0인 노드(자식 노드를 가지지 않는 노드). • 비단말 노드/내부(internal).. 2022. 10. 22.
2.4 스택과 큐 2.4.1 스택 빈 접시들이 가지런히 쌓여 있는 상황에서 가장 위의 접시를 가져가거나, 책상 위에 쌓여진 책 더미 위에 책을 하나 올려 놓는 것과 같은 상황을 표현할 수 있는 자료구조(접시 더미나 책 더미)= 스택. * 스택- 데이터의 삽입과 삭제가 한쪽 끝(더미의 가장 위쪽)에서만 이루어지는 자료구조. top- 데이터의 삽입과 삭제가 일어나는 부분. 데이터 삽입 - top이 가리키는 곳의 바로 위쪽에 저장. 데이터 삭제 - top이 가리키는 데이터가 제거. 후입선출(LIFO: Last-In First-Out) - 가장 마지막으로 삽입된 데이터가 가장 먼저 삭제되는 구조. 데이터의 삽입 연산= push, 삭제 연산=pop 2.4.2 큐 매표창구에서 표를 사서 가는 사람과 표를 사기 위해 줄의 맨 끝에서 .. 2022. 10. 9.
2.3 리스트 2.3.1 리스트의 개념 리스트[선형 리스트(linear list) 또는 순서 리스트(ordered list)]는 1개 이상의 원소들이 순서를 가지고 구성됨. 선형 리스트는 A=(a1, a2,…, ai,…, an), i= i번째 원소, n=리스트의 크기. 예) •요일 리스트: (월, 화, 수, 목, 금, 토, 일) • 전쟁 리스트: ((황산벌 전투, 660), (임진왜란, 1592), (제1차 세계대전,1914), (제2차세계대전, 1939)) 2.3.2 리스트의 구현 리스트를 표현하는 가장 간단한 방법 - 1차원 배열 이용. 선형 리스트와 1차원 배열 - 순차적인 구조. 리스트의 논리적인 순서 = 배열의 물리적인 저장 순서. 리스트에 원소를 삽입하기 위해서는 원소를 삽입할 위치에 있는 원소와 그 다음의.. 2022. 10. 2.

티스토리툴바