자료구조13 [자료구조] 이진 트리 (Binary Tree) 이진 트리 (Binary Tree) 모든 노드의 차수가 2 이하인 트리 이진 트리 종류 1. 포화 이진 트리 (Full Binary Tree) 모든 레벨의 노드가 꽉 차있는 이진 트리 n = 2 ^ h - 1 ( 높이가 h 인 이진 포화 트리의 노드 개수) 2. 완전 이진 트리 (Complete Binary Tree) 높이가 h 일 때, 레벨1 ~ 레벨 h-1까지는 포화 이진트리처럼 꽉 채워져 있고 마지막 레벨 h(단말 노드) 에서는 중간에 빈 노드 없이 노드가 왼쪽부터 차례로 채워져 있어야함. n < 2 ^ h - 1 (높이가 h인 완전 이진 트리의 노드 개수) 3. 편향 이진 트리 (Skewed Binary Tree) 같은 높이의 이진 트리 중에서 최소 개수의 노드 개수를 가지면서 왼쪽 혹.. 2020. 9. 8. [자료구조] 트리 (Tree) 트리 (Tree) - 계층 구조 (Hierarchical Structure)로 자료를 저장하는 자료구조 (비선형 자료구조) - 노드(Node), 간선 (Edge)의 집합 - 계층 구조 : 특정 부모 노드 하나에 여러 개의 자식 노드들이 연결되는 구조 회사 조직도 모델링 노드 종류 1. 위치 기준 노드 이름 설명 루트(Root) 노드 트리의 첫 번째 노드 단말(Leaf 혹은 Terminal) 노드 자식 노드가 없는 노드 내부 (Internal) 노드 자식 노드가 있는 노드 2. 관계 기준 노드 이름 설명 부모(Parent) 노드 자식 노드와 간선(Edge)으로 연결 자식(Child) 노드 부모 노드와 간선(Edge)으로 연결 선조(Ancestor) 노드 루트 노드 - 부모 노드까지 경로 상에 있는 모든.. 2020. 8. 31. [자료구조] 큐 (Queue) 큐 (Queue) 추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터가 나오는 자료구조 FIFO (First In First Out, 선입선출) 저장된 자료들은 선후 관계가 모두 1:1 front : 큐의 제일 앞, 자료가 반환되는 곳 rear : 큐의 제일 뒤, 자료가 추가되는 곳 enqueue() : 큐에 자료를 삽입하는 함수 dequeue() : 큐에서 자료를 빼내는 함수 peek() : 큐에 맨 위에 있는 자료 반환하는 함수 (큐에서 삭제는 하지 않는다) 큐의 크기 : 큐가 저장할 수 있는 최대 자료의 개수 → 이 갯수를 넘어버리면 오버플로우(Overflow) 발생 ex) 은행 업무 처리 대기열, 프린터 대기 문서 //배열로 구현한 선형 큐 public class Main { stati.. 2020. 8. 31. [자료구조] 스택 (Stack) 스택 (Stack) 자료를 한 방향으로만 쌓는 자료구조 LIFO (Last In First Out 후입선출 : 마지막에 들어온 것이 가장 먼저 나간다) push : 스택에 data를 넣는 것 pop : 스택 맨 위의 data를 빼는 것 peek : pop과 유사하게 맨 위의 data를 반환하지만 스택에서 제거하지는 않는다. top : 가장 마지막에 추가된 data의 위치 (가장 맨위) 가장 마지막에 push 한 data가 가장 먼저 pop 된다. 오버플로우 (Overflow) : 자료가 스택 크기를 넘어서서 더 이상 push 하지 못할 때 발생 언더플로우 (Underflow) : 스택에 자료가 남아있지 않아서 더 이상 pop하지 못할 때 발생 배열로 구현해보기 public class Main { stat.. 2020. 8. 26. 이전 1 2 3 4 다음
