알고리즘...46

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

출력이 위에서부터 아래로 진행되어야 하므로 DFS를 이용한 함수를 만들어 테스트를 진행한다.

 

BinarySearchTree.cpp

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

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

		std::cout << node->data << ' ';

		if (node == _root || IsRightNode(node))
		{
			std::cout << '\n';
		}

		if (node->left != nullptr)
		{
			_queue.push(node->left);
		}
		if (node->right != nullptr)
		{
			_queue.push(node->right);
		}
	}
    
	std::cout << "\n\n";
}

 

main.cpp

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

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

	BinarySearchTree tree;
	for (int i = 0; i < n; i++)
	{
		tree.Insert(arr[i]);
	}
	tree.PrintBinarySearchTree();

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

	delete[] arr;
}

 

출력 결과

2
1 4
3 6
5 8
7 10
9

2
1 4
3 6
8
7 10
9

 

단순히 DFS로 진행하는 게 아니라 각 노드의 깊이 값에 따라 모양을 저장하고 순서대로 출력해야 할 것 같다.