이진 트리

이번에 다룰 내용은 그래프의 트리 내용의 심화 내용이다. DFS, BFS는 지난 시간에 앞서 간단히 소개하였기 때문에 오늘은 이진 트리에서의 순회에 대하여 집중적으로 알아볼 시간이다.

 

이진트리란 

정점의 자식이 최대 2개인 트리를 뜻한다. 지금까지 우리가 알아본 순회 방식에는 DFS와 BFS가 존재하지만 특별히 이름이 덧붙여진 순회들이 있다. 바로 레벨 순회와 전위/ 중위/후위 순회이다.

 

이진트리를 집중적으로 알기 전에 우리가 기본적으로 넘겨짚고 가야할 부분들이 있다.

좌측의 트리 그래프와

우측의 이진 트리를 코드에서 표현하는 방식이다.

 

 

기존에 사용했던 방식과 동일하게 트리를 큐나 스택에 저장하게 된다면 인접 리스트의 노드가 좌노드인지 우노드인지 판별이 어렵다.

따라서 구별할 수 있는 방식이 두가지가 존재하는데 이때 구조체를 작성하여 클래스로 만드는 것과 배열을 가지고 처리하는 방식이 있다. 오른쪽 표의 lc는 left children으로 좌 노드를 가리키고, rc는 right children으로 우 노드를 가리킨다.

 

 

---

 

레벨 순회(Level-order Traversal)

 

레벨 순회는 이름 그대로 레벨, 즉 높이 순으로 방문하는 순회이다. 위의 트리에서는 1,2,3,4,5,6,7,8 순으로 방문하게 된다.

해당 순회 방식은 BFS 순회 방식과 동일하다라는 것을 알 수 있다.

 

int lc[9] = {0,2,4,6,0,0,0,0}
int re[9] = {0,3,5,7,0,8,0,0,0}

void bfs()
{
	queue<int> q;
    q.push();
    while(!q.empty())
    {
    
    int curr = q.front();
    q.pop();
    cout << cur << ' ';
    if(lc[cur]) q.push(lc[cur]);
    if(rc[cur]) q.push(rc[cur]);

	}


}

 

 

 

전위 순회(Preorder Traversal)

레벨 순위를 제외한 3개의 순회는 재귀적으로 정의할 수 있다.

 

전위 순회가 노드를 방문하는 방식이다.

1. 현재 정점을 방문한다.

2. 왼쪽 서브 트리를 전위 순회한다.

3. 오른쪽 서브 트리를 전위 순회한다.

 

 

 

 

int lc[9] = { 0, 2, 4, 6, 0, 0, 0, 0 };
int rc[9] = { 0,3 ,5, 7, 0 ,8, 0, 0, 0 };

void preorder(int cur)
{
	cout << cur << ' ';
	if (lc[cur] != 0) preorder(lc[cur]);
	if (rc[cur] != 0) preorder(rc[cur]);

}

 

 

 

 

중위 순회(Inorder Traversal)

 

중위순회는 왼쪽 -> 중간 -> 오른쪽 순으로 처리하는 순회 방법이다.

 

 

int lc[9] = { 0, 2, 4, 6, 0, 0, 0, 0 };
int rc[9] = { 0,3 ,5, 7, 0 ,8, 0, 0, 0 };

void inorder(int cur)
{
	if (lc[cur] != 0) inorder(lc[cur]);
	cout << cur << ' ';
	if (rc[cur] != 0) inorder(rc[cur]);
}

 

 

 

후위 순회(Postorder Traversal)

 

후위 순회는 왼쪽 서브 노드 -> 오른쪽 서브 노드 -> 현재 정점을 방문하는 순으로 순회한다.

 

 

 

 

int lc[9] = { 0, 2, 4, 6, 0, 0, 0, 0 };
int rc[9] = { 0,3 ,5, 7, 0 ,8, 0, 0, 0 };

void postorder(int cur)
{
	if (lc[cur] != 0) postorder(lc[cur]);
	if (rc[cur] != 0) postorder(rc[cur]);
	cout << cur << ' ';
}

 

 

---