-
이진 검색 트리 출력 함수 구현프로그래밍 기초/알고리즘 2021. 9. 21. 13:55
이진 검색 트리 출력
이진 검색 트리를 화면에 출력하는 함수를 구현한다.
노드 출력 알고리즘
노드를 동일한 간격으로 출력하기 위해 다음의 제약 사항이 존재해야 한다.
- 모든 노드는 동일한 크기를 갖는다.
- 최대 깊이의 노드 간의 간격은 노드의 크기와 같다.
- 최대 깊이에 빈 노드가 없다고 가정하여 최대 크기를 구한다.
- 구한 최대 크기를 모든 깊이에 사용하여 출력한다.
깊이가 n 일 때, 노드의 개수 및 공백의 개수는 다음과 같다.
- 노드의 수 2ⁿ - ¹ 개
- 공백의 수 n + 1 개
따라서 최대 깊이에서 출력에 필요한 크기는 다음의 식을 만족한다.
출력에 필요한 크기 = (공백의 수 + 노드의 수) * 노드의 크기
※ 깊이에 따라 노드의 수가 달라지므로 공백의 크기는 출력에 필요한 크기 - (노드의 수 * 노드의 크기) / 공백의 수가 된다.
노드 연결 막대 출력 알고리즘
노드를 연결하는 막대를 출력하는 알고리즘도 기본적으로 출력에 필요한 크기를 공유하며 노드의 크기에 따라 중간 막대 위치를 조정해 주면 된다.
좌측 노드를 출력하는 순서는 다음과 같다.
- 공백의 크기만큼 공백(' ') 추가
- 노드의 크기의 절반만큼 공백(' ') 추가
- 위 오른쪽 막대('┌') 추가
- 노드의 크기의 절반 만큼 가로 막대('─') 추가
- 공백의 크기 / 2 - 1 만큼 가로 막대('─') 추가
- 오른쪽 위 막대('┘') 추가
오른쪽 노드를 출력하는 순서는 다음과 같다.
- 아래 오른쪽 막대('└') 추가
- 공백의 크기 / 2 - 1 만큼 가로 막대('─') 추가
- 노드의 크기의 절반 만큼 가로 막대('─') 추가
- 오른쪽 아래 막대('┐') 추가
- 노드의 크기의 절반 만큼 공백(' ') 추가
이진 검색 트리 출력 함수 구현
기존 BinarySearchTree의 코드에서 출력 함수를 위해 필요한 함수 및 변수만 표시했다. 필요한 경우 전체 코드는 깃허브에서 확인하면 된다.
BinarySearchNode
struct BinarySearchNode { const static int Width = 8; // ... 생략 int GetMaxDepth() { int leftMaxDepth{ left != nullptr ? left->GetMaxDepth() : 0 }; int rightMaxDpth{ right != nullptr ? right->GetMaxDepth() : 0 }; return (leftMaxDepth > rightMaxDpth ? leftMaxDepth : rightMaxDpth) + 1; } int GetCurDepth() { return (parent != nullptr ? parent->GetCurDepth() : 0) + 1; } // ... 생략 string ToString() { if (isEmpty) { return string(Width, ' '); } string dataStr = std::to_string(data); size_t spaceCnt = Width - dataStr.size(); size_t leftSpaceCnt = spaceCnt / 2; size_t rightSpaceCnt = spaceCnt / 2 + spaceCnt % 2; return string(leftSpaceCnt, '_') + dataStr + string(rightSpaceCnt, '_'); } bool isEmpty; // ... 생략 };BinarySearchNodeManager
class BinarySearchNodeManager { public: // ... 생략 BinarySearchNode* GetEmptyNode(BinarySearchNode* parent); // ... 생략 }; BinarySearchNode* BinarySearchNodeManager::GetEmptyNode(BinarySearchNode* parent) { BinarySearchNode* emptyNode = Pop(); emptyNode->parent = parent; emptyNode->isEmpty = true; return emptyNode; }BinarySearchTree
#include <string> #include <queue> #include <map> using std::string; using std::queue; using std::map; class BinarySearchTree { public: // ... 생략 void PrintTree(); private: // ... 생략 void PrintTree(BinarySearchNode* node, int lineWidth); string GetNodeStick(BinarySearchNode* node, int blankSize); // ... 생략 private: // ... 생략 queue<BinarySearchNode*> _queue; map<int, string> _numberMap; map<int, string> _stickMap; }; void BinarySearchTree::PrintTree() { if (_root == nullptr) { std::cout << "EMPTY\n"; return; } int maxDepth{ _root->GetMaxDepth() }; int maxNodeCount{ static_cast<int>(std::pow(2, maxDepth - 1)) }; int totalCount{ maxNodeCount * 2 + 1 }; int lineWidth{ totalCount * BinarySearchNode::Width }; for (int i = 1; i <= maxDepth; i++) { _numberMap[i] = ""; _stickMap[i] = ""; } _queue.push(_root); while (!_queue.empty()) { BinarySearchNode* node{ _queue.front() }; _queue.pop(); PrintTree(node, lineWidth); if (!node->isEmpty) { if (node->left != nullptr) { _queue.push(node->left); } else { BinarySearchNode* emptyNode{ _nodeManager.GetEmptyNode(node) }; emptyNode->left = node; _queue.push(emptyNode); } if (node->right != nullptr) { _queue.push(node->right); } else { BinarySearchNode* emptyNode{ _nodeManager.GetEmptyNode(node) }; emptyNode->right = node; _queue.push(emptyNode); } } if (node->isEmpty) { _nodeManager.Push(node); } } for (int i = 1; i <= maxDepth; i++) { std::cout << _stickMap[i] << '\n'; std::cout << _numberMap[i] << '\n'; } std::cout << "\n\n"; } void BinarySearchTree::PrintTree(BinarySearchNode* node, int lineWidth) { int curDepth{ node->GetCurDepth() }; int curNodeCount{ static_cast<int>(std::pow(2, curDepth - 1)) }; int totalNodeSize{ curNodeCount * BinarySearchNode::Width }; int blankCount{ curNodeCount + 1 }; int totalBlankSize{ lineWidth - totalNodeSize }; int blankSize{ totalBlankSize / blankCount }; string& numberStr{ _numberMap[curDepth] }; numberStr.append(string(blankSize, ' ')); numberStr.append(node->ToString()); string& stickStr{ _stickMap[curDepth] }; stickStr.append(GetNodeStick(node, blankSize)); } string BinarySearchTree::GetNodeStick(BinarySearchNode* node, int blankSize) { if (node == _root) { return ""; } int halfNodeWidth{ BinarySearchNode::Width / 2 }; int halfBlankSize{ blankSize / 2 }; string result; if ((node->isEmpty && node->left != nullptr) || IsLeftNode(node)) { int leftSpaceCnt{ blankSize + halfNodeWidth - (BinarySearchNode::Width % 2 == 0 ? 1 : 0) }; result.append(string(leftSpaceCnt, ' ')); result.append(node->isEmpty ? " " : "┌"); int rightHypenCnt{ halfBlankSize + halfNodeWidth - 1 }; for (int i = 0; i < rightHypenCnt; i++) { result.append(node->isEmpty ? " " : "─"); } result.append(node->isEmpty ? " " : "┘"); } else { result.append(node->isEmpty ? " " : "└"); int leftHypenCnt{ halfBlankSize + halfNodeWidth - 1 }; for (int i = 0; i < leftHypenCnt; i++) { result.append(node->isEmpty ? " " : "─"); } result.append(node->isEmpty ? " " : "┐"); result.append(string(halfNodeWidth, ' ')); } return result; }이진 검색 트리 출력 함수 테스트
여러 값을 트리에 삽입한 뒤 출력하고 특정 값을 삭제한 뒤 다시 출력하여 결과를 확인한다.
main.cpp
#include "Common.h" #include "검색트리/BinarySearchTree.h" int main() { int n = 9; int* arr; // 동작 테스트를 위한 값 arr = new int[n]{ 10, 5, 20, 3, 7, 15, 25, 1, 4 }; BinarySearchTree tree; for (int i = 0; i < n; i++) { tree.Insert(arr[i]); } tree.PrintTree(); tree.Delete(5); tree.PrintTree(); tree.Delete(10); tree.PrintTree(); tree.Delete(15); tree.PrintTree(); delete[] arr; }실행결과
___10___ ┌───────────────────────┘└───────────────────────┐ ___5____ ___20___ ┌─────────────┘└─────────────┐ ┌─────────────┘└─────────────┐ ___3____ ___7____ ___15___ ___25___ ┌───────┘└───────┐ ___1____ ___4____ ___10___ ┌───────────────────────┘└───────────────────────┐ ___4____ ___20___ ┌─────────────┘└─────────────┐ ┌─────────────┘└─────────────┐ ___3____ ___7____ ___15___ ___25___ ┌───────┘ ___1____ ___7____ ┌───────────────────────┘└───────────────────────┐ ___4____ ___20___ ┌─────────────┘ ┌─────────────┘└─────────────┐ ___3____ ___15___ ___25___ ┌───────┘ ___1____ ___7____ ┌───────────────────────┘└───────────────────────┐ ___4____ ___20___ ┌─────────────┘ └─────────────┐ ___3____ ___25___ ┌───────┘ ___1____NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)
GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소
알고리즘 학습 및 예제 코드 작성을 위한 저장소. Contribute to NadanKim/Algorithm development by creating an account on GitHub.
github.com