[자료구조] 트리 탐색(tree traversal) 방법- inorder traverse, postorder traverse, preorder traverse, level order traversal

트리를 탐색하는 방법은 크게 Depth-First Traversal, Breadth-First Traversal로 나뉜다.

*Breadth-First Traversal은 같은 level(height)에 있는 노드들을 모두 탐색한 후, 다음 level로 넘어가는 방식이다.

 

*Depth-First Traversal은 깊이 우선 탐색방법으로 현재 노드와 연결된 노드들을 먼저 탐색한 후에 다음 노드로 넘어가는 것이다.

 

Depth-First Traversal에는 inorder, postorder, preorder 세 가지 탐색법이 있다. 

 

1. inorder traverse: left subtree -> root -> right subtree

이 방식은 이진트리(binary tree)에서만 사용할 수 있다. 

 

이러한 이진 트리가 있다고 할 때

먼저 왼쪽의 subtree로 이동한다.

왼쪽의 subtree에서 왼쪽노드가 가장 먼저 탐색되고, 그 다음 root, 마지막으로 오른쪽 노드가 탐색된다. 

 

왼쪽의 subtree의 탐색이 모두 끝났기 때문에 이제 root 노드가 탐색된다.  

 

그 다음 오른쪽 subtree로 이동한다. 

오른쪽 subtree에서 가장 왼쪽 노드가 탐색되고 그다음 root노드가 탐색된다. 

오른쪽에 또 subtree가 있다. 

 

오른쪽 subtree로 이동해서 왼쪽 노드를 탐색하고 그다음 root노드를 탐색한다. 

 

inorder 탐색의 전체적인 순서이다. 

 

 

 

 

2. postorder traverse: left subtree -> right subtree -> root

먼저 왼쪽의 subtree로 이동한다.

왼쪽의 subtree에서 왼쪽노드가 가장 먼저 탐색되고, 그 다음 오른쪽 노드, 마지막으로 root가 탐색된다. 

 

그 다음 오른쪽 subtree로 이동한다.

오른쪽 subtree에서 가장 왼쪽 노드가 탐색되고 그다음 오른쪽 노드가 탐색된다. 

그런데 오른쪽에 또 subtree가 있다. 

 

 

오른쪽 subtree로 이동해서 왼쪽 노드를 탐색하고 그다음 오른쪽 노드를 탐색해야하는데 오른쪽 노드가 없으니 바로 root를 탐색한다. 

 

오른쪽 subtree를 모두 탐색했기 때문에 마지막으로 root를 탐색한다. 

 

 

오른쪽 subtree를 모두 탐색했기 때문에 root를 탐색한다. 

 

postorder의 전체적인 탐색순서이다. 

 

 

 

3. preorder travers: root -> left subtree -> right subtree

 

 

preorder 탐색의 전체적인 순서이다. 

typedef struct node
{
	int data;
	struct node *left,*right;
}node;

void preorder(node *T)
{
	if(T!=NULL)
	{
		printf("%d ",T->data);
		preorder(T->left);
		preorder(T->right);
	}
}
 
void inorder(node *T)
{
	if(T!=NULL)
	{
		inorder(T->left);
		printf("%d",T->data);
		inorder(T->right);
	}
}

void postorder(node *T)
{
	if(T!=NULL)
	{
		inorder(T->left);
		inorder(T->right);
        printf("%d",T->data);
	}
}