알고리즘...50

이진 검색 트리 출력 함수 제작

노드의 깊이와 넓이의 관계를 파악하기 위해 1, 4 를 추가한다.

 

main.cpp

#include "Common.h"
#include "검색트리/BinarySearchTree.h"

int main()
{
	int n = 9;
	int* arr;

	// 동작 테스트를 위한 값
	//arr = new int[n]{ 2, 4, 6, 8, 10, 9, 7, 5, 3, 1 };
	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.PrintBinarySearchTree();

	//tree.Delete(5);
	//tree.PrintBinarySearchTree();

	// 출력하고 싶은 모양
	std::cout << "         10\n";
	std::cout << "    ┌────┴────┐\n";
	std::cout << "    5         20\n";
	std::cout << "  ┌─┴─┐     ┌─┴─┐\n";
	std::cout << "  5   20    5   20\n";
	std::cout << "┌─┴─┐\n";
	std::cout << "1   4\n";

	delete[] arr;
}

 

실행결과

       10
┌──────┴──────┐
     5       20
┌────┴────┐┌─┴─┐
  3  71525
┌─┴─┐


         10
    ┌────┴────┐
    5         20
  ┌─┴─┐     ┌─┴─┐
  5   20    5   20
┌─┴─┐
1   4

 

엔터 처리가 잘못됐다. 항상 가득 찬 상태의 이진 검색 트리로 처리하다 보니 잘못 생각한 부분이 있었다.

이 문제를 처리하기 위해 map을 도입했다.

 

BinarySearchTree.h

#pragma once
#include "../Common.h"
#include <string>
#include <queue>
#include <map>

using std::string;
using std::queue;
using std::map;

/// <summary>
/// 이진 검색 트리에 사용할 노드
/// </summary>
struct BinarySearchNode
{
	BinarySearchNode() : data{ 0 }, parent{ nullptr }, 
		left{ nullptr }, right{ nullptr } {}
	BinarySearchNode(int data) : data{ data }, parent{ nullptr }, 
		left{ nullptr }, right{ nullptr } {}

	void Clear()
	{
		data = 0;
		parent = nullptr;
		left = nullptr;
		right = nullptr;
	}

	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;
	}

	bool HasLeftChild()
	{
		return left != nullptr;
	}

	bool HasRightChild()
	{
		return right != nullptr;
	}

	int data;
	BinarySearchNode* parent;
	BinarySearchNode* left;
	BinarySearchNode* right;
};

/// <summary>
/// 이진 검색 트리에서 노드의 재활용을 위한 매니저
/// </summary>
class BinarySearchNodeManager
{
public:
	~BinarySearchNodeManager();

	void Push(BinarySearchNode* node);
	BinarySearchNode* Pop();

private:
	BinarySearchNode* nodes;
};

/// <summary>
/// 연결 자료구조를 이용한 이진 검색 트리
/// </summary>
class BinarySearchTree
{
public:
	~BinarySearchTree();

	bool Exists(int data);
	const BinarySearchNode& Search(int data);
	void Insert(int data);
	void Delete(int data);

	void PrintBinarySearchTree();

private:
	void Insert(BinarySearchNode* parent, int data);
	void Delete(BinarySearchNode* node);

	void PrintBinarySearchTree(BinarySearchNode* node);

	BinarySearchNode* GetNode(int data);

	bool IsLeftNode(BinarySearchNode* node);
	bool IsRightNode(BinarySearchNode* node);

	int GetTreeMaxDepth();

private:
	BinarySearchNode* _root;
	BinarySearchNodeManager _nodeManager;
	queue<BinarySearchNode*> _queue;
	map<int, string> _numberMap;
	map<int, string> _stickMap;
};

 

BinarySearchTree.cpp

/// <summary>
/// 이진 검색 트리를 출력한다.
/// </summary>
void BinarySearchTree::PrintBinarySearchTree()
{
	if (_root == nullptr)
	{
		std::cout << "EMPTY\n";
		return;
	}

	int depth{ _root->GetMaxDepth() };

	for (int i = 1; i <= depth; i++)
	{
		_numberMap[i] = "";
		_stickMap[i] = "";
	}

	_queue.push(_root);
	while (!_queue.empty())
	{
		BinarySearchNode* node{ _queue.front() };
		_queue.pop();

		PrintBinarySearchTree(node);

		if (node->left != nullptr)
		{
			_queue.push(node->left);
		}
		if (node->right != nullptr)
		{
			_queue.push(node->right);
		}
	}

	for (int i = 1; i <= depth; i++)
	{
		std::cout << _numberMap[i] << '\n';
		std::cout << _stickMap[i] << '\n';
	}
	std::cout << "\n\n";
}

/// <summary>
/// 이진 검색 트리를 출력한다.
/// </summary>
/// <param name="node">현재 출력할 노드</param>
void BinarySearchTree::PrintBinarySearchTree(BinarySearchNode* node)
{
	int targetDepth{ node->GetCurDepth() };
	int depth{ node->GetMaxDepth() };
	int width{ (depth - 1) * 5 };
	int center{ width / 2 };

	string& numberStr{ _numberMap[targetDepth] };
	string& stickStr{ _stickMap[targetDepth] };

	for (int i = 0; i < width; i++)
	{
		numberStr.push_back(' ');
	}
	numberStr.append(std::to_string(node->data));
	for (int i = 0; i < width; i++)
	{
		numberStr.push_back(' ');
	}

	for (int i = 0; i < center; i++)
	{
		stickStr.push_back(' ');
	}
	if (node->HasLeftChild())
	{
		stickStr.append("┌");
		for (int i = 1; i < center; i++)
		{
			stickStr.append("─");
		}
	}
	else
	{
		for (int i = 0; i < width; i++)
		{
			stickStr.push_back(' ');
		}
	}

	if (node->HasLeftChild() || node->HasRightChild())
	{
		stickStr.append("┴");
	}

	if (node->HasRightChild())
	{
		for (int i = 1; i < center; i++)
		{
			stickStr.append("─");
		}
		stickStr.append("┐");
	}
	else
	{
		for (int i = 0; i < width; i++)
		{
			stickStr.push_back(' ');
		}
	}
}

 

실행결과

               10
       ┌──────┴──────┐
          5               20
     ┌────┴────┐  ┌─┴─┐
     3     71525
  ┌─┴─┐
14



         10
    ┌────┴────┐
    5         20
  ┌─┴─┐     ┌─┴─┐
  5   20    5   20
┌─┴─┐
1   4

 

엔터 처리는 설정이 되었으나 여전히 간격이 적절하지 못하다.