1. 스레드 이진 트리1) 이진 트리의 연결 리스트 표현• 노드의 구성: 노드들은 데이터 필드와 링크 필드를 가짐.• NULL 링크 문제: 특정 노드가 자식 노드가 없으면 링크 필드는 NULL이 저장됨. 링크 개수 비교:• n개의 노드로 구성된 이진 트리의 총 링크 개수: 2n개• 실제 사용되는 링크 개수: n-1개• 사용되지 않는 NULL 링크 개수: n+1개 2) 스레드 이진 트리(Thread Binary Tree)개념:• NULL 링크를 다른 노드를 가리키는 포인터로 설정한 이진 트리.• 자식 노드가 없는 경우, NULL 대신 순회 순서상의 다른 노드를 가리키도록 설정. 스레드(Thread)의 역할:• 트리의 다른 노드를 가리키는 포인터 역할 수행.• 트리 순회 정보를 유지하는 용도로 활용.• 순회..
자료구조
1. 이진 트리의 순회 방법1) 트리 순회 (Tree Traversal)• 트리를 구성하는 모든 노드를 특정 순서대로 한 번씩 방문하는 과정• 모든 노드를 중복 없이 방문하여 데이터를 목적에 맞게 처리• 선형 자료구조는 순차적으로 저장되므로 순회 방법이 단순하지만, 트리는 다양한 순회 방식 존재• 이진 트리에서 중요한 연산 중 하나 2) 이진 트리의 순회• 기본 연산: 왼쪽 서브 트리 방문 → 루트 노드 방문 → 오른쪽 서브 트리 방문• 이진 트리의 순회 방법- 전위 순회 (Preorder Traversal)- 중위 순회 (Inorder Traversal)- 후위 순회 (Postorder Traversal) 3) 전체 트리와 서브 트리의 구조• 서브 트리는 전체 트리보다 크기만 작을 뿐 동일한 구조• 전..
1. 이진 트리의 개념과 구조1) 트리• 일반 트리와 이진 트리로 구분됨. 2) 일반 트리• 각 노드의 차수가 가변적이므로 자식 노드의 개수를 예상하기 힘들고, 이를 구현하려면 기억 공간 면에서도 비효율적임. 3) 이진 트리• 트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리.• 데이터의 구조적인 관계를 잘 반영하고 효율적인 삽입과 탐색을 가능하게 함.• 일반 트리에 비해 간단하고 효율적으로 구현 가능.• 가장 중요하면서도 자주 사용되는 트리.• 다양한 탐색 트리(search tree), 히프(heap) 자료구조, 컴파일러의 수식을 위한 구문 트리(syntax tree) 등의 기본이 되는 자료구조.• 광범위하게 응용됨. 일반 트리와의 차이점• 공백 이진 트리 존재.• 서브 트..
1. 트리의 개념트리의 특성• 선형 자료구조: 배열, 리스트, 스택, 큐 등• 트리(tree): 데이터를 계층적으로 저장하는 자료구조 트리의 특징• 일대다 관계 표현• 그래프 중에서 사이클을 포함하지 않는 연결 그래프• 데이터 탐색, 삽입, 삭제에서 선형 구조보다 효율적 트리의 예시• 가계도: 가족 구성원을 계층적으로 표현• 기업 조직도: 부서와 직급 구조 표현• 컴퓨터 디렉터리 구조: 폴더와 파일 체계 표현• 결정 트리: 인공지능에서 의사결정을 위한 트리• 운영체제 파일 시스템: 파일 저장 구조 표현• 데이터베이스: 계층적 데이터 구성 2. 트리의 용어트리의 구성 요소• 루트 노드(root node): 트리의 최상위 노드 (부모 없음)• 자식 노드(child node): 특정 노드의 하위 노드• 부모..
1. 다중 스택(Multiple Stack)• 스택의 오버플로우 방지를 위해 여러 개의 스택을 하나의 기억 공간에 저장하는 구조 구현 방법• 2개의 스택을 연결: 배열 양쪽에서 각각의 스택이 증가• n개의 스택을 연결: 사용 가능한 기억 공간을 균등 또는 가변적으로 분할 삽입 및 삭제 연산• 삽입: 특정 스택이 가득 찼는지 확인 후 데이터 추가• 삭제: 스택이 비어있는지 확인 후 top 데이터를 제거 2. 다중 큐(Multiple Queue)• 프로세스 효율적 관리를 위해 여러 개의 큐를 연결하여 운영 운영 방식• 고정 우선순위 방식: 프로세스가 종료될 때까지 우선순위 유지• 변동 우선순위 방식: 실행 중 우선순위 변경 가능• 반전 우선순위 방식: 낮은 우선순위를 높은 우선순위로 변경• 대기 상태 큐..
1. 원형 큐와 데크1) 원형 큐(Circular Queue)• 순차 큐의 단점을 보완한 큐의 한 형태로, 배열의 처음과 끝을 연결하여 원형으로 구성됨.• 개념적으로 원형이므로 데이터를 이동시키지 않고 rear 포인터를 조정하여 삽입 가능. 논리적 구조• 초기 상태에서는 front = rear = -1• front는 첫 번째 원소의 앞을, rear는 마지막 원소를 가리킴. 순차 큐 vs 원형 큐• 순차 큐: rear = rear + 1, front = front + 1• 원형 큐: rear = (rear + 1) mod n, front = (front + 1) mod n 2) 데크(Deque: Double-Ended Queue)• 양쪽 끝에서 삽입과 삭제가 가능한 큐의 특수한 형태. 추상 자료형(ADT)..
1. 큐의 개념1) 큐 (Queue)• 큐는 일상생활에서 흔히 볼 수 있는 자료구조로, 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First-In First-Out) 구조를 가진다. 큐의 특징• 스택과 유사하지만, 삽입과 삭제가 서로 다른 위치에서 수행됨• 삽입은 rear에서, 삭제는 front에서 이루어짐• front와 rear라는 두 개의 포인터를 사용 큐의 예시• 신호등 앞에서 줄 서 있는 자동차• 키보드 입력 시 버퍼 메모리에 저장되는 문자들• 프린터 인쇄 대기열 2) 큐의 주요 동작삽입 연산 (Enqueue)• rear 포인터가 가리키는 위치에 원소 삽입• 삽입 후 rear 증가 삭제 연산 (Dequeue)• front 포인터가 가리키는 위치의 원소 삭제• 삭제 후 front 증가 ..
1. 스택의 응용 분야문서 편집기의 되돌리기(Undo) 기능• 사용자가 작업을 수행한 후 이전 상태로 되돌리기 위해 사용• 실행한 작업을 순차적으로 기록하고, 역순으로 취소해야 하므로 스택 이용 컴퓨터 프로그램의 함수 호출• 함수 호출 시 복귀 주소, 지역 변수, 매개변수 등을 스택에 저장• 함수 실행 완료 후 스택에서 최근 복귀 주소를 가져와 원래 위치로 돌아감 컴파일러의 산술식 변환• 컴파일러는 산술식을 분석하여 연산자와 피연산자를 구별하고 우선순위에 맞게 변환• 전위 표기법, 중위 표기법, 후위 표기법 변환 시 스택 사용 문자열 뒤집기• 문자열을 입력 순서대로 스택에 저장한 후, 역순으로 꺼내어 출력• 예: "ABCD" → "DCBA" 괄호 검사• 소스 코드에서 괄호의 짝을 확인하기 위해 사용• 여..
