알고리즘...55

노드를 연결하는 막대 그리기

이전 계산을 통해 노드 사이의 간격을 알고 있으므로 막대는 다음과 같이 그릴 수 있다.

대략적인 막대 그림

 

막대의 경우 현 노드가 왼쪽 자식인지, 오른쪽 자식인지에 따라 처리가 달라지게 된다.

먼저 왼쪽 자식의 처리는 다음과 같이 진행한다.

1. 노드와 동일한 공백 입력
2. 노드의 크기의 절반 만큼 공백 추가
3. 오른쪽 아래 막대 추가
4. 노드의 크기의 절반 만큼 가로 막대 추가
5. 공백의 절반 - 1 만큼 가로 막대 추가
6. 위로 향하는 막대 추가

오른쪽 자식의 처리는 다음과 같이 진행한다.

1. 위로 향하는 막대 추가
2. 공백의 절반 - 1 만큼 가로 막대 추가
3. 노드의 크기의 절반 만큼 가로 막대 추가
4. 왼쪽 아래 막대 추가
5. 노드의 크기의 절반 만큼 공백 추가

 

BinarySearchTree.h

/// <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, int lineWidth);

	BinarySearchNode* GetNode(int data);

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

	int GetTreeMaxDepth();
	string GetNodeStick(BinarySearchNode* node, int blankSize);

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 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();

		PrintBinarySearchTree(node, lineWidth);

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

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

/// <summary>
/// 주어진 노드에 맞는 막대를 만들어 반환한다.
/// </summary>
/// <param name="node">처리할 노드</param>
/// <returns>막대 노드 문자열</returns>
string BinarySearchTree::GetNodeStick(BinarySearchNode* node, int blankSize)
{
	if (node == _root)
	{
		return "";
	}

	int halfNodeWidth{ BinarySearchNode::Width / 2 };
	int halfBlankSize{ blankSize / 2 };

	if (node->isEmpty)
	{
		int stringLength{ BinarySearchNode::Width + blankSize };
		return string(stringLength, ' ');
	}

	string result;
	if (IsLeftNode(node))
	{
		int leftSpaceCnt{ blankSize + halfNodeWidth
			- (BinarySearchNode::Width % 2 == 0 ? 1 : 0) };
		result.append(string(leftSpaceCnt, ' '));
		result.append("┌");
		int rightHypenCnt{ halfBlankSize + halfNodeWidth - 1 };
		for (int i = 0; i < rightHypenCnt; i++)
		{
			result.append("─");
		}
		result.append("┘");
	}
	else
	{
		result.append("└");
		int leftHypenCnt{ halfBlankSize + halfNodeWidth - 1 };
		for (int i = 0; i < leftHypenCnt; i++)
		{
			result.append("─");
		}
		result.append("┐");
		result.append(string(halfNodeWidth, ' '));
	}

	return result;
}

 

실행결과

                                        _10__
                           ┌─────────────┘└─────────────┐
                         __5__                         _20__
               ┌───────┘└───────┐                 ┌───────┘└───────┐
             __3__             __7__             _15__             _25__
       ┌───┘└───┐
     __1__     __4__     _____     _____     _____     _____     _____     _____



                                        __7__
                           ┌─────────────┘└─────────────┐
                         __4__                         _20__
               ┌───────┘                                    └───────┐
             __3__             _____             _____             _25__
       ┌───┘
     __1__     _____     _____     _____

 

깔끔한 결과는 아니지만 어느정도 알아볼 수 있는 결과를 얻었다.