알고리즘...49

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

추가로 3, 7, 15, 25를 추가하여 트리를 출력하고자 한다.

 

main.cpp

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

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

	// 동작 테스트를 위한 값
	//arr = new int[n]{ 2, 4, 6, 8, 10, 9, 7, 5, 3, 1 };
	arr = new int[7]{ 10, 5, 20, 3, 7, 15, 25 };

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

	delete[] arr;
}

 

실행결과

     10
┌────┴────┐
  5  ┌─┴─┐  20  ┌─┴─┐3   7   15   25



       10
  ┌────┴────┐
  5         20
┌─┴─┐     ┌─┴─┐
5   20    5   20

 

막대를 중간에 그리게 되는 문제가 발생한다.

이것을 해결하기 위해 숫자용 문자열과 막대용 문자열을 추가하여 따로 처리해본다.

 

BinarySearchTree.cpp

/// <summary>
/// 이진 검색 트리를 출력한다.
/// </summary>
/// <param name="node">현재 출력할 노드</param>
void BinarySearchTree::PrintBinarySearchTree(BinarySearchNode* node)
{
	static string numberStr;
	static string stickStr;

	int depth{ node->GetMaxDepth() };
	int center{ (depth - 1) * 5 / 2 };

	bool isNeedReturn{ ((node == _root) || IsRightNode(node) 
		&& (node->parent == _root || IsRightNode(node->parent))) };

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

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

	if (isNeedReturn)
	{
		std::cout << numberStr << '\n';
		if (stickStr.size() > 0)
		{
			std::cout << stickStr << '\n';
		}

		numberStr.clear();
		stickStr.clear();
	}
}

 

실행결과

     10
┌────┴────┐
  5    20
┌─┴─┐┌─┴─┐
371525



       10
  ┌────┴────┐
  5         20
┌─┴─┐     ┌─┴─┐
5   20    5   20

 

숫자와 막대의 간격 설정을 다시 생각해 봐야 할 것 같다.