JArchive 프로그래밍 일기

이진 트리란?

모든 노드가 2개의 자식을 가진 트리입니다.

이진 트리의 순회 

전위 순회, 중위 순회, 후위 순회 세 가지 방식이 있습니다.  

'루트 노드' 중심으로 생각하면 어렵지 않습니다. 

루트 노드를 가장 먼저 가면 전위 순회.

중간에 루트노드에 가면 중위 순회.

루트 노드를 맨 마지막에 가면 후위 순회입니다. 

전위 순회 

루트 -> 왼쪽 -> 오른쪽  순으로 방문합니다. 

/* 전위 순회 */
void Preorder(Node* node) {

	// 루트 -> 왼쪽 -> 오른쪽 

	if (NULL == node) {
		return;
	}

	printf("%d\n", node->data);
	
	Preorder(node->leftChild);

	Preorder(node->rightSibling);

}

중위 순회 

왼쪽 -> 루트 -> 오른쪽 순으로 방문합니다. 

/* 중위 순회 */
void Inorder(Node* node) {

	// 왼쪽 -> 루트 -> 오른쪽

	if (NULL == node) {
		return;
	}

	Inorder(node->leftChild);

	printf("%d\n", node->data);

	Inorder(node->rightSibling);

}

후위 순회

왼쪽 -> 오른쪽 -> 루트  순으로 방문합니다. 

/* 후위 순회 */
void Postorder(Node* node) {

	// 왼쪽 -> 오른쪽 -> 루트

	if (NULL == node) {
		return;
	}

	Postorder(node->leftChild);
	
	Postorder(node->rightSibling);

	printf("%d\n", node->data);

}