자료구조
-
트리(Tree)와 이진 탐색 트리(Binary Search Tree)프로그래밍 기초/자료구조 2021. 3. 29. 19:33
트리 각각의 자료가 노드를 이루고 각 노드가 부모-자식 관계를 형성하는 자료구조를 말한다. 트리의 구성 요소 트리는 하나의 루트와 여러 개의 자식 노드로 구성된다. 노드 트리를 이루는 각각의 요소 루트 트리의 최상단 요소 리프 트리의 최말단 요소 차수 각 노드가 가진 자식의 수 트리의 차수 해당 트리에 존재하는 각 노드의 차수 중 가장 큰 값 높이 트리의 노드의 레벨 중 가장 큰 값 이진트리 리프 노드를 제외한 노드의 자식이 1개 혹은 2개로 이루어진 트리로 각 서브 트리는 다음과 같은 구조로 이루어진다. ※ 각 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드로 구분하며 각각의 자식 노드가 자식 노드를 가진 경우 자식 노드를 루트로 하는 노드 집단을 서브 트리라고 한다. 이진 트리의 특징 n개의 노드를 ..
-
자료구조...71일지 2021. 3. 25. 19:20
이진 탐색 트리 삭제, 기능 메서드 구현 BinarySearchTree.cpp /// /// BinarySearchTree의 모든 노드를 제거한다. /// void BinarySearchTree::Clear() { while (m_root != nullptr) { Delete(m_root->m_data); } } /// /// BinarySearchTree에 지정된 값이 존재하는지 검색한다. /// /// 검색할 값 bool BinarySearchTree::Search(int value) { if (m_root == nullptr) { return false; } Node* target{ m_root }; while (target != nullptr) { if (target->m_data == value..
-
자료구조...70일지 2021. 3. 24. 19:52
이진 탐색 트리 삽입 메서드 구현 더블 포인터 구현을 싱글 포인터 구현으로 변경 BinarySearchTree.cpp /// /// /// /// 추가할 값 void BinarySearchTree::Insert(int value) { if (m_root == nullptr) { m_root = PopNode(value); return; } Node* target{ m_root }; while (target != nullptr) { if (target->m_data == value) { break; } if (target->m_data > value) { if (target->m_left == nullptr) { target->m_left = PopNode(value); m_count++; } target..
-
자료구조...69일지 2021. 3. 23. 20:48
이진 탐색 트리 삭제 메서드 구현 BinarySearchTree.cpp /// /// BinarySearchTree에서 지정된 값을 가진 노드를 제거한다. /// /// 제거할 값 void BinarySearchTree::Delete(int value) { if (m_root == nullptr) { return; } Node* target{ m_root }; Node* parent{ nullptr }; while ((target != nullptr) && (target->m_data != value)) { parent = target; if (target->m_data > value) { target = target->m_left; } else { target = target->m_right; } } ..
-
자료구조...68일지 2021. 3. 22. 18:09
이진 탐색 트리 삭제 메서드 구현 BinarySearchTree.cpp /// /// BinarySearchTree에서 지정된 값을 가진 노드를 제거한다. /// /// 제거할 값 void BinarySearchTree::Delete(int value) { Node** target{ &m_root }; Node* parent{ nullptr }; while (*target != nullptr) { if ((*target)->m_data == value) { break; } if ((*target)->m_data > value) { parent = *target; target = &((*target)->m_left); } else { parent = *target; target = &((*target)->..
-
자료구조...67일지 2021. 3. 17. 12:29
이진 탐색 트리 삽입 메서드 구현 BinarySearchTree.cpp #pragma region 생성자 /// /// 비어있는 DoublyLinkedList를 생성한다. /// BinarySearchTree::BinarySearchTree() : m_count(0), m_max(0), m_min(0), m_root(nullptr), m_free(nullptr) { } /// /// 메모리 누수를 막기 위해 동적 생성한 노드들을 제거한다. /// BinarySearchTree::~BinarySearchTree() { Clear(); while (m_free != nullptr) { Node* curNode{ m_free }; m_free = m_free->m_right; delete curNode; } ..
-
자료구조...66일지 2021. 3. 16. 21:02
이진 탐색 트리 구현 준비 구현에 필요한 메서드 및 속성은 다음과 같다. 속성 Count BinarySearchTree에 포함된 데이터의 개수 Max BinarySearchTree에 추가된 데이터 중 가장 큰 값 Min BinarySearchTree에 추가된 데이터 중 가장 작은 값 메서드 Search(data) 데이터가 저장되어 있는지 여부 확인 Insert(data) BinarySearchTree의 규칙에 맞게 데이터를 저장 Delete(data) 일치하는 데이터를 제거하고 실행 결과를 반환 Clear() 저장되어 있는 모든 데이터 삭제 이진 탐색 트리 구현 연결 자료구조를 이용하여 이진 탐색 트리를 구현한다. BinarySearchTree.h #pragma once #include class Bin..