In University ☆ In Bucket Place ☆ Hobby & Study Room ☆

*이진 탐색 트리 1. 특징 ⓐ 트리의 모든 노드의 키 값은 유일 해야한다. ⓑ 왼쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 작아야 한다. ⓒ 오른쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 커야한다. ⓓ 왼쪽과 오른쪽 서브트리 모두 이진 탐색 트리이다. - ⓐ~ⓓ의 특징을 만족해야만 이진 탐색 트리라고 할수 있다. - "탐색"이라는 단어가 들어 있을 만큼 자료 탐색에 효율을 두기 위해 만든 자료구조 ( >특정 키 값에 해당하는 노드를 찾는 것이 기본 기능 ) ex) 2. 이진 탐색 트리의 삽입/삭제 ⓐ 삽입 Step 1: 추가되는 키 값이 트리에 존재하는지를 탐색한다.(값의 탐색연산) (같은 키 값이 존재하면 False / 다른 키 값을 가지면 Step 2 실행) Step 2: 추가되는..

*히프 1. 특징 - 루트 노드가 언제나 그 트리의 최대값 혹은 최솟값을 가지는 독특한 구조의 완전 이진 트리 2. 종류 - 최대 히프 : 최대 트리(각 노드의 키 값이 작은 자식 노드의 키 값보다 크가나 같은 트리)의 속성을 가진 히프 ex) - 최소 히프 : 최소 트리(각 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 트리)의 속성을 가진 히프 ex) 3. 히프의 삽입/삭제 연산 - 히프의 삽입/삭제 연산은 연산 뒤에 정렬이 따른다. ⓐ 히프의 삽입 : 히프에 값을 삽입하면, 완전 이진 트리의 특징에 맞는 위치에 값이 삽입되며, 그 뒤에 그 값이 히프로서의 특징을 가질 수 있는 위치로 정렬/이동을 하게된다. ex) 최대 히프에서의 삽입을 예로 들겠다. ⓑ 히프의 삭제 : 삭제 연산은 루트에서 이..

~프로로그~ Microsoft Visual C++ 2010 Express, 즉, 체험판을 열심이 쓰고 있었는데.... 만료 됬다. 다시 다운 받아서 해야된다... ㅠ_ㅠ 귀차니즘에 구현은 둘째치고 트리의 순회에 대해서 알아보도록하자~ ----------------------------------------------------------------------------------------------------- *트리의 순회란? - 트리의 모든 노드를 한 번씩 방문 하는 것 *특징 - 이진트리의 최대 차수가 2이기 때문에 현재 방문중인 V(Visit)노드 왼쪽자식노드 L(Left node), 오른쪽자식노드 R(Right)로 나눠 일반화 하여 생각할수 있다. *트리의 순회 종류 ⓐ 전위 순회 - 순회 순..

* 이진 트리 > 모든 노드의 차수가 2이하인 트리 > 종류 : 포화 이진트리, 완전 이진트리, 편향 이진트리 ⓐ 포화 이진 트리 : 모든 레벨의 노드가 꽉 차 있는 이진 트리 : 저장 가능한 총 노드의 개수 > 2^h - 1 // h : 트리의 높이 = 같은 높이의 이진 트리에서 가질 수 있는 가장 많은 노드의 개수 ⓑ 완전 이진 트리 : 마지막 레벨에서 왼쪽 부터 오른쪽으로 노드가 채워져 있는 트리, 중간에 빈 노드가 있어서는 안된다. ⓒ 편향 이진 트리 : 같은 높이의 이진 트리중 최소 개수의 노드 개수를 가진 트리 : 오른쪽 or 왼쪽 서브 트리만 가지는 것 ------------------------------------------------------------------------------..

* Tree 트리구조 ⓐ 특징 > 노드와 간선의 집합 > 계층 구조 - 트리를 구성하는 노드의 관계가 부모-자식이라는 의미 - 특정 부모노드 하나에 여러개의 자식 노드들이 연결되는 구조 > 트리를 구성하는 부모-자식 노드의 관계가 1:1 이 아님! → 비선형구조! > 특정 노드 하나가 여러개의 자식을 보유 가능하나, 각 노드는 단 하나의 부모노드만을 가질 수 있음. ⓑ 용어정리 > 노드의 구성 - 노드 : 일반적으로 모델링하는 자료구조/시스템의 객체 - 간선 : 노드 사이의 연결선(부모-자식 관계를 정의해줌) > 노드의 종류 - 루트 노드 : 트리의 첫번째 노드 / 부모노드가 없는 노드 - 단말 노드 : 자식 노드가 없는 노드 - 내부 노드 : 자식 노드가 있는 노드 / 모든 노드 집합 - 단말 노드 집..

~프로로그~ 어느 덧 책에서 재귀라는 단어가 나오게 되었습니다. 재귀라는 것은 전에 포스팅한 글 보다 잘쓰기가 힘들거 같아서 설명은 링크로 하고... 하노이 탑에 대해서 설명해볼까합니다. 재귀호출에 대한 설명 글 보기! 자 그럼 S t A r T !! ------------------------------------------------------------ 하노이 탑에 대해서 일단 설명 해보겠습니다. 위 그림에서 원판이 있는 막대를 A 중앙을 B 가장 왼쪽을 C 막대로 지칭하도록 하겠습니다. 일단, 목표는 간단합니다. A막대에서 C막대로 모든 원판을 크기 순서대로 옮기면 됩니다. 이때 제약 사항이있죠~ ⓐ 한번에 하나의 원판만 이동 가능!! ⓑ 맨 위에 있는 원판만 이동 가능!! ⓒ 크기가 작은 원판 ..

스택의 응용 분야 ① 산술 연산 : 중위 연산 - * 나 / 가 + 와 -보다 우선순위가 높은것을 감안하여 연산자를 우선 스택에 저장하고 우선순위가 더 높은것이 나중에 들어오면 하나식 빼는 과정을 가지고 있습니다. ② Subroutine call과 return(서브루틴의 복귀 번지) 주프로그램에 의해 호출되는 프로그램. (C로 작성한 프로그램에서 함수를 사용했을때 main()함수에서 a();라는 함수를 호출했을때 현재 가지고 있는 번지 수를 기억하였다가 a(); 함수가 종료되면 스택에 저장되어있는 주소를 꺼내어 다시 되돌아 갈때 쓰입이다 ) ③ 인터럽트 처리 현재 프로세스가 메모리를 할당받어 실행하고 있는도중 인터럽트가 발생하면 현재 프로세스 정보를 스택에 저장하고 인터럽트 처리후에 다시 사용합니다 ④ ..

* 덱(Deque) ⓐ 특징 - 두 개의 끝을 가지는 큐 - Double Ended Queue의 약자 - 구조의 앞과 뒤에서 모두 추가/삭제가 가능한 구조 - 큐와 스택의 기능을 합친 자료구조 ⓑ 변수 - 맨 앞을 가르키는 front - 맨 뒤를 가르키는 rear ⓒ 함수 - makeDeque() : 덱 생성 - insertFront() : 맨 앞에 자료 추가 - insertRear() : 맨 뒤에 자료 추가 - deleteFront() : 맨 앞의 자료 삭제 - deleteRear() : 맨 뒤의 자료 삭제 ⓓ 구현 - 배열 이용 / 특이 사항 없음 - 리스트 이용 > 단일 링크드리스트를 사용하면 자료의 맨끝(rear)에 자료를 삭제 할시 문제가 발생한다. > 이중 링크드리스트 사용을 추천한다. ---..

#include #include #include typedef struct nodetype{ int data; struct nodetype *next; }node; typedef struct Quetype{ int count; node * rear; node * front; }Que; //자료형태 구조체 및 Que구조체 생성 //배열 큐와의 차이점 : ⓐ최대 저장개수가 불필요 / ⓑ rear/front가 포인터로써 쓰임 Que *makeQue(){ Que *returnQue; returnQue = (Que *)malloc(sizeof(Que)); if ( returnQue != NULL ){ returnQue -> count = 0; // 현재저장된 개수 초기화 returnQue -> rear = NUL..

#include #include #include typedef struct nodetype{ int data; }node; typedef struct Quetype{ int max; int count; int rear; int front; node *ArrayQue; }Que; //자료형태 구조체 및 Que구조체 생성 Que *makeQue(int max){ Que *returnQue; returnQue = (Que *)malloc(sizeof(Que)); if ( returnQue != NULL ){ returnQue -> max = max; // 최대값 지정 returnQue -> count = 0; // 현재값 지정 returnQue -> rear = -1; // 현재 꼬리 위치지정 returnQu..