05. 이진 트리의 구현 및 순회

이진 트리의 순회

전위 순회

• 자기 자신 출력
• 왼쪽 자식 출력
• 오른쪽 자식 출력

전위 순회 결과 : 30 - 17 - 5 - 23 - 48 - 37 - 50

중위 순회

• 왼쪽 자식 출력
• 자기 자신 출력
• 오른쪽 자식 출력

중위 순회 결과 : 5 - 17 - 23 - 30 - 37 - 48 - 50

후위 순회

• 왼쪽 자식 출력
• 오른쪽 자식 출력
• 자기 자식 출력

후위 순회 결과 : 5 - 23 - 17 - 37 - 50 - 48 - 30

이진 트리의 구현

#include <stdio.h>
#include <stdlib.h>

// 노드 정의
typedef struct {
	int data;
	struct Node* leftChild;
	struct Node* rightChild;
} Node;

// 노드 초기화
Node* initNode(int data, Node* leftChild, Node* rightChild) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->leftChild = leftChild;
	node->rightChild = rightChild;
	return node;
}

// 전위 순회
void preorder(Node* root) {
	if (root) { // null값이 아니라면
		printf("%d ", root->data);
		preorder(root->leftChild);
		preorder(root->rightChild);
	}
}

// 중위 순회
void inorder(Node* root) {
	if (root) {
		inorder(root->leftChild);
		printf("%d ", root->data);
		inorder(root->rightChild);
	}
}

// 후위 순회
void postorder(Node* root) {
	if (root) {
		postorder(root->leftChild);
		postorder(root->rightChild);
		printf("%d ", root->data);
	}
}

// main
int main(void) {
	Node* n7 = initNode(50, NULL, NULL);
	Node* n6 = initNode(37, NULL, NULL);
	Node* n5 = initNode(23, NULL, NULL);
	Node* n4 = initNode(5, NULL, NULL);
	Node* n3 = initNode(48, n6, n7);
	Node* n2 = initNode(17, n4, n5);
	Node* n1 = initNode(30, n2, n3);
	preorder(n1);
	printf("\n");
	inorder(n1);
	printf("\n");
	postorder(n1);
	printf("\n");
	system("pause");
	return 0;
}