본문 바로가기

C6

이진 트리 순회 이진 트리 순회 이진 트리의 순회 방법 전위순회 : 루트 노드를 먼저 순회 중위순회 : 루트 노드를 중간에 순회 후위순회 : 루트 노드를 마지막에 순회 순회의 재귀적 표현 세 가지 순회의 방법을 재귀적으로 구현하면 높으가 2이상인 트리도 순회 가능 중위순회 함수 void InorderTraverse(BTreeNode* bt) { if (bt == NULL) return; InorderTraverse(bt->left); printf("%d \n", bt->data); InorderTraverse(bt->right); } __BinaryTreeTraverseMain.c #include #include "BinaryTree.h" void InorderTraverse(BTreeNode* bt) { if (bt .. 2022. 6. 2.

이진 트리(Binary Tree) 이진 트리란? 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 짐. 나뉘어진 두 서브 트리도 모두 이진 트리. 노드가 위치 할 수 있는 곳에 노드가 존재하지 않으면, 공집합 노드가 존재하는 것으로 간주. 서브 트리 큰 트리는 작은 트리로 구성이 되는데 이렇듯 큰 트리에 속하는 작은 트리를 서브 트리라 함. 포화 이진 트리와 완전 이진 트리 포화 이진 트리 모든 레벨이 꽉 차 있고 노드를 더 추가하려면 레벨을 늘려야 하는 이진 트리. 완전 이진 트리 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈틈없이 노드가 채워진 이진 트리를 뜻한다. 연결 리스트 기반 이진 트리 구현 헤더파일에 정의된 구조체 // 구조체 자체만으로도 공집합 노드 두 개를 갖은 노드이자 트리 typedef stru.. 2022. 6. 1.

Tree(트리) Tree(트리) 트리란? 비선형 자료구조로써 나무처럼 가지를 늘려가며 뻗어나가는 특징을 갖고 있고, 트리는 계층적 관계를 표현하는 자료구조 트리의 예 트리의 예로는 집안의 족보나 기업및 정부의 조직도도 트리의 예가 됨. 트리 관련 용어 노드 : node 트리의 구성 요소에 해당하는 A, B, C, D, E, F와 같은 요소. 간선 : edge 노드와 노드를 연결하는 연결선. 루트 노드 : root node 트리 구조에서 최상위에 존재하는 A와 같은 노드. 레벨 : level 각 층별로 숫자를 매긴 것. 높이 : height 트리의 최고 레벨을 가리켜 높이라 함. 부모 노드 : parent node 노드 A는 노드 B, C, D의 부모 노드이다. 자식 노드 : child node 노드 B, C, D는 노드.. 2022. 6. 1.

ArrayList (배열 기반 리스트) 리스트란? 리스트 : 원소들이 연속적으로 저장되는 형태의 자료형 리스트의 조건(특징) 저장 형태 : 데이터를 나란히 저장한다(선형) 저장 특성 : 중복된 데이터 저장을 허용 리스트 자료구조 ADT void ListInit(List* plist); //리스트 초기화 void LInsert(List* plist, LData data); //리스트에 데이터를 저장 int LFirst(List* plist, LData* pdata); //리스트의 첫번째 데이터 참조 int LNext(List* plist, LData* pdata); //리스트의 참조 데이터의 다음 데이터 참조 LData LRemove(List* plist); //리스트 마지막 반환 데이터 삭제 int LCount(List* plist); //리.. 2022. 5. 30.

재귀 재귀함수란? 재귀함수 : 함수 내에서 자기 자신을 다시 호출하는 함수를 의미 사용 가능한 재귀 함수 1. 재귀의 탈출이 조건을 통해 가능함. 2. 매개변수를 바꿔서 호출. *재귀 함수를 잘못 사용하면 무한루프에서 빠져나오지 못할 수도 있기 때문에 주의! 예) 피보나치 수열 : Fibonacci Sequence 0 n=1 fibo(n)={ 1 n=2 Fibo(n-1)+Fibo(n-2) otherwise 예) 이진 탐색 알고리즘의 재귀적 구현 1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인 2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작 출처 : 윤성의 열혈 자료구조 2022. 5. 29.

자료 구조 자료 구조 자료구조란 무엇인가? 자료구조 : 프로그램이란 데이터를 표현 및 저장하는 것이다. 알고리즘 : 표현된 데이터를 처리하는 것이다. -알고리즘은 자료 구조에 의존적이다. 자료구조 분류 선형 자료구조 : 리스트, 스택, 큐 비선형 자료구조 : 트리, 그래프 알고리즘의 성능분석 방법 시간 복잡도 : 얼마나 빠른지를 비교 공간 복잡도 : 얼마나 메모리를 적게 쓰는지 비교 *빅-오 표기법 : 데이터의 수의 증가에 따른 연산횟수의 증가 형태를 표현한 것 대표적인 빅오 -O(1) 상수형 빅-오 -O(log n) 로그형 빅-오 -O(n) 선형 빅-오 -O(nlog n) 선형로그형 빅-오 -O(n^2) 데이터의 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘 -O(n^3) 데이터의 수의 세제곱에 해당하는 연산.. 2022. 5. 29.

이전 1 다음

티스토리툴바