Tree

개요

---

트리순회

트리 순회는 2진트리에서 트리를 순회하는 것을 말한다.

총 4가지의 순회 알고리즘이 있고, 각각의 알고리즘을 알아보고자 한다.

1. 후위순회(postorder traversal)
2. 전위순회(preorder traversal)
3. 중위순회(inorder traversal)
4. 레벨순회(level traversal)

후위순회

---

후위순회(postorder traversal)는 자식들 노드를 방문하고 자신의 노드를 방문하는 것

수도코드

postorder( node )
// 방문하지 않았더라면 
    if (node.visited == false)
// 왼쪽 노드(자식노드) 방문
        postorder( node->left ) 
        postorder( node->right )
// 오른쪽 노드(본인노드) 방문
        node.visited = true

전위순회

---

전위순회(preorder traversal)는 먼저 자신의 노드를 방문하고 그 다음 노드들을 방문하는 것

수도코드

postorder( node )
// 방문하지 않았더라면 
    if (node.visited == false)
// 오른쪽 노드(본인노드) 방문
				node.visited = true
        postorder( node-> right) 
// 왼쪽 노드(자식노드) 방문
        postorder( node->left )
        

중위순회

---

중위순회(inorder traversal)는 왼쪽 노드를 먼저 방문 그다음의 자신의 노드를 방문하고 그 다음 오른쪽 노드를 방문하는 것

---

수도코드

inorder( node )
    if (node.visited == false) 
        inorder( node->left )
        node.visited = true
        inorder( node->right )

레벨순회

---

레벨순회(level traversal) BFS(너비우선 탐색)를 생각하면 된다.

Q. 아래의 그래프가 주어졌을 때 preorder, inorder, postorder를 구현하라.

수도코드를 보고 코드를 구축하는 연습을 하셔야 합니다. 아래와 같이 그래프가 주어졌을 때 비어진 함수를 채워서 preorder, inorder, postorder를 구현하고 이 때 방문했을 때 해당 노드를 출력하는 것을 구현하라.

#include <iostream>
#include <vector>

using namespace std; 
vector<int> adj[1004]; 
int visited[1004];

// 전위순회
void postOrder(int here){  
} 
// 후위순회
void preOrder(int here){ 
}  
// 중위순회
void inOrder(int here){    

} 
int main(){
/*
  1
 2 3
4 5
*/
	adj[1].push_back(2);
	adj[1].push_back(3);
	adj[2].push_back(4);
	adj[2].push_back(5); 
	int root = 1;
    cout << "\n 트리순회 : postOrder \n";
    postOrder(root); memset(visited, 0, sizeof(visited));
    cout << "\n 트리순회 : preOrder \n"; 
    preOrder(root); memset(visited, 0, sizeof(visited)); 
    cout << "\n 트리순회 : inOrder \n"; 
    inOrder(root); 
    return 0;
}

정답코드

#include <bits/stdc++.h>
using namespace std; 
vector<int> adj[1004]; 
int visited[1004];

void postOrder(int here){ 
  	if(visited[here] == 0){ 
  		if(adj[here].size() == 1)postOrder(adj[here][0]);
  		if(adj[here].size() == 2){
  			postOrder(adj[here][0]); 
  			postOrder(adj[here][1]);
		}
  		visited[here] = 1; 
  		cout << here << ' ';
	} 
} 
void preOrder(int here){
  	if(visited[here] == 0){
  		visited[here] = 1; 
  		cout << here << ' ';
  		if(adj[here].size() == 1)preOrder(adj[here][0]);
  		if(adj[here].size() == 2){
  			preOrder(adj[here][0]); 
  			preOrder(adj[here][1]);
		}
	}
}  
void inOrder(int here){   	
	if(visited[here] == 0){ 
  		if(adj[here].size() == 1){ 
  			inOrder(adj[here][0]); 
	  		visited[here] = 1; 
	  		cout << here << ' ';
		}else if(adj[here].size() == 2){
  			inOrder(adj[here][0]); 
	  		
			visited[here] = 1; 
	  		cout << here << ' ';
  			
			inOrder(adj[here][1]);
		}else{
	  		visited[here] = 1; 
	  		cout << here << ' '; 
		}
	}

} 
int main(){
	adj[1].push_back(2);
	adj[1].push_back(3);
	adj[2].push_back(4);
	adj[2].push_back(5); 
/*
  1
 2 3
4 5
*/
	int root = 1;
    cout << "\n 트리순회 : postOrder \n";
    postOrder(root); memset(visited, 0, sizeof(visited));
    cout << "\n 트리순회 : preOrder \n"; 
    preOrder(root); memset(visited, 0, sizeof(visited)); 
    cout << "\n 트리순회 : inOrder \n"; 
    inOrder(root); 
    return 0;
}
/*
 트리순회 : postOrder
4 5 2 3 1
 트리순회 : preOrder
1 2 4 5 3
 트리순회 : inOrder
4 2 5 1 3
*/

Reference

---

큰돌의 터전 : 네이버 블로그