scriptplay330 우선순위 큐(STL 힙 정렬) #include #include // STL 우선순위 큐를 이용한 내림차순 정렬. 최대 힙void heapSortDec(int arr[], int n){ priority_queue maxHeap; for (int i = 0; i 2019. 9. 3. 우선순위 큐(힙) 부모 노드의 키 값이 자식 노드의 키 값보다 큰 이진 트리. 최대 힙(max heap) ; 부모 노드의 키 값이 자식 노드의 키값보다 크거나 같은 완전 이진트리 key(부모 노드) >= key(자식 노드) 최소 힙(min heap) ; 부모 노드의 키 값이 자식 노드의 키값보다 작거나 같은 완전 이진트리 key(부모 노드) getParent(i).getKey()) // 루트가 아니고 부모노드보다 키값이 크면 { node[i] = getParent(i); // 부모를 자신노드로 끌어내림 i /= 2; // 한 레벨 위로 상승 } node[i].setKey(key); // 최종 위치에 데이터 복사 } // 힙의 루트 노드를 반환하고 힙을 재구성 HeapNode remove() { if (isEmpty()) .. 2019. 9. 3. 이진 탐색 트리 모든 노드는 유일한 키를 갖는다. 왼쪽 서브트리의 키들은 루트의 키보다 작다. 오른쪽 서브트리의 키들은 루트의 키보다 크다. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다. #include "BinaryTree.h" class BinSrchTree : public BinaryTree { public: BinSrchTree(void) {} ~BinSrchTree(void) {} // 이진 탐색 트리의 탐색 연산 BinaryNode* search(int key) { BinaryNode* node = searchRecur(root, key); if (node != NULL) printf("탐색 성공: 키값이 %d인 노드 있음\n", node->getData()); else printf("탐색 실패: 키값이 %d.. 2019. 9. 3. 스레드 이진트리 노드의 개수가 n 이면 전체 링크의 수는 2n. 루트를 제외한 n-1 개의 노드가 부모와 연결됨(간선). 2n 중에 n-1 개를 제외한 n+1 개의 링크가 항상 NULL. n+1개의 NULL 링크에 중위 순회 시에 선행 노드인 중위선행자(inorder predecessor)나 중위 순회 시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리 class ThreadBinNode{private: int data; ThreadBinNode* left; ThreadBinNode* right;public: bool bThread; public: ThreadBinNode(int value, ThreadBinNode* l, ThreadBinNode* r, bool bTh) : data(.. 2019. 8. 29. BinaryTree 구현. -트리의 용어 루트 노드(root node): 부모가 없는 노드. 트리는 단 하나의 루트 노드를 가짐. 서브 트리(sub tree): 루트 노드를 제외한 나머지 노드들. 링크(link): 루트 노드와 서브트리를 연결하는 선. 간선/에지(edge)라 부름. 형제(sibling): 같은 부모 노드를 가지는 노드. 단말 노드(leaf node): 자식 노드가 없는 노드. 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수. 노드의 깊이(depth): 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 링크(간선)의 수. 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합. (루트 = 1레벨) 노드의 차수(degree): 노드가 지닌 가지(간선)의 수. 트리의 차수(degree of .. 2019. 8. 23. 순환 int factorial(int n){ if (n == 1) return 1; else return (n * factorial(n - 1));} int factorialIter(int n){ int result = 1; for (int i = n; i > 0; i--) { result = result * i; } return result;} double power(double x, int n){ if (n == 0) return 1; else if (n % 2 == 0) return power(x*x, n / 2); else return x * power(x*x, (n - 1) / 2);} int fibonacci(int n){ if (n == 0) return 0; if (n == 1) return 1.. 2019. 8. 22. 이전 1 ··· 49 50 51 52 53 54 55 다음