인오더, 프리오더, 포스트오더 (Inorder, Preorder, Postorder)

인오더, 프리오더, 포스트오더 (Inorder, Preorder, Postorder)

이진 트리를 순회하는 세 개의 방법

---

 

  정의 

  이진 트리(Binary Tree) 를 순회(Traversal)할 때 위와 같이 세 가지 방법이 존재한다.

 

• Inorder (중위 순회) : left Node -> root Node -> right Node
• preorder (전위 순회) : root Node -> left Node -> right Node
• postorder (후위 순회) : left Node -> right Node -> root Node

---

  중위 순회 (Inorder Traversal) 

  left Node -> root Node -> right Node 순서로 순회한다.

  위 트리에선 (1) -> (3) -> (4) -> (5) -> (6) -> (7) -> (12) -> (15) -> (16) 순서로 순회한다.

---

  전위 순회 (preorder Traversal) 

  root Node -> left Node -> right Node 순서로 순회한다.

  위 트리에선 (7) -> (3) -> (1) -> (5) -> (4) -> (6) -> (15) -> (12) -> (16) 순서로 순회한다.

---

  후위 순회 (postorder Traversal) 

  left Node -> right Node -> root Node 순서로 순회한다.

  위 트리에선 (1) -> (4) -> (6) -> (5) -> (3) -> (12) -> (16) -> (15) -> (7) 순서로 순회한다.

 

  후위 순회는, root Node를 가장 마지막에 방문한다.

---

  Code 

typedef int E;

typedef struct Node {
	E data;
	struct Node* parent;
	struct Node* left_child;
	struct Node* right_child;
} Node;

void preOrder(Node* curNode) { // root -> left -> right
	printf(" %d", curNode->data);
	if (curNode->left_child != NULL) preOrder(curNode->left_child);
	if (curNode->right_child != NULL) preOrder(curNode->right_child);
}

void inOrder(Node* curNode) { // left -> root -> right
	if (curNode->left_child != NULL) inOrder(curNode->left_child);
	printf(" %d", curNode->data);
	if (curNode->right_child != NULL) inOrder(curNode->right_child);
}

void postOrder(Node* curNode) { // left -> right -> root
	if (curNode->left_child != NULL) postOrder(curNode->left_child);
	if (curNode->right_child != NULL) postOrder(curNode->right_child);
	printf(" %d", curNode->data);
}