알고리즘...45

이진 탐색 트리 출력

이진 탐색 트리 구현 후 테스트를 위한 출력 함수를 만든다. 이때 다음과 같은 정보가 필요하다.

• 노드의 간격과 왼쪽 공백에 필요한 정보 루트 기준으로 최대 깊이를 파악하여 깊이에 따라 간격을 조절한다.
• 노드의 출력 순서 라인별로 출력이 되어야 하므로 BFS를 이용하여 출력을 진행한다.

 

깊이 파악을 위한 함수

struct BinarySearchNode
{
	int GetMaxDepth()
	{
		int leftMaxDepth{ left != nullptr ? left->GetMaxDepth() : 0 };
		int rightMaxDpth{ right != nullptr ? right->GetMaxDepth() : 0 };
		return (leftMaxDepth > rightMaxDpth ? leftMaxDepth : rightMaxDpth) + 1;
	}
    
	int data;
	BinarySearchNode* parent;
	BinarySearchNode* left;
	BinarySearchNode* right;
};

 

참고문헌

Christopher Oicles.(2016.04.23).Print binary tree in a pretty way using c++

Wikipedia.Breadth-first search