이진 탐색 트리 / 전위 중위 후위

이진 트리의 탐색 방법으로는 전위 중위 후위 3가지 방법이 있다.

 

전위는 뿌리부터 왼쪽으로 타고 내려가면서 출력한 뒤, 왼쪽이 없으면 부모노드로 돌아가 오른쪽노드를 출력하게 된다.

 

중위는 왼쪽 아래부터 출력한 뒤 부모 노드 > 오른쪽 노드 출력을 반복하게 된다.

 

후위는 왼쪽 아래부터 출력한 뒤 오른쪽 형제 노드를 출력하고 부모노드를 출력하게 된다.

 

글로 보면 이해가 힘들지만 코드를 보면 간단하게 이해 가능하다.

 

void BinaryTree::print1(Node* temp) {
	if (!temp)
		return;

	std::cout << temp->Data << " ";

	print1(temp->left);

	print1(temp->right);
}

void BinaryTree::print2(Node* temp) {
	if (!temp)
		return;
	
	print2(temp->left);

	std::cout << temp->Data << " ";

	print2(temp->right);
}

void BinaryTree::print3(Node* temp) {
	if (!temp)
		return;
	
	print3(temp->left);

	print3(temp->right);

	std::cout << temp->Data << " ";
}

차례대로 전위 중위 후위 출력의 함수인데, 

 

재귀함수로 구성되고 어디서 출력을 하느냐의 차이이다.

 

코드를 보고 설명을 다시 보면 이해가 될 것이다. 그냥 코드를 외우는게 더 편할지도 모르겠다. 코드가 너무 간단함