[Algorithm] 이진 트리(Binary Tree)와 트리 순회(Tree Traversal)

예시는 모두 Javascript를 이용하여 구현하였다.

 

트리 & 그래프

우선 그래프 탐색을 하기 위해서는 그래프에 대해 알아야한다. 트리와 그래프는 가장 대표적인 그래프형 자료구조이다. 

Tree는 서로 연결된 Node의 계층형 자료구조로써, root와 부모-자식 관계의 subtree로 구성되어있다.
두 개의 노드 사이에 1개의 경로만을 가지며 사이클이 존재하지 않은 방향 그래프이다. 따라서 '최소 연결 트리'라고 부르기도 한다.
트리 순회에는 전위순회, 중위순회, 후휘순회 3가지가 존재한다.

그래프(G)는 정점(vertex)들의 집합 V와 이들을 연결한 간선(edge)들의 집합 E로 구성된 자료구조이다. 이를 통해 연결된 노드 간의 관계를 표현할 수 있는 자료구조이다.

 

\	트리	그래프
정의	단일 루트 노드로 연결된 노드들로 이루어진 계층적인 데이터 구조.	각각의 노드들이 엣지로 연결된 비계층적인 데이터 구조.
노드	각 노드(루트 제외)는 정확히 하나의 부모를 가지며 사이클이 없다.	노드들은 여러 엣지로 연결될 수 있으며 사이클이 존재할 수 있다.
루트 노드	트리 구조에서 최상위 노드.	그래프에는 루트 노드의 개념이 없다
방향성 vs 무방향성	트리는 일반적으로 무방향이다.	그래프는 방향이 있는지, 없는지에 따라 방향성이나 무방향성이 될 수 있다.
가중치 vs 무가중치	트리는 일반적으로 무가중치이다.	그래프는 가중치가 있을 수 있으며(엣지가 연결된 가중치를 가짐), 없을 수도 있다.
비순환성 vs 순환성	트리는 항상 비순환적이다(사이클이 없음).	그래프는 비순환적일 수 도 있고 (사이클 없음), 순환적일 수 도 있다(사이클 포함).
연결성	모든 노드 쌍 사이에는 정확히 하나의 경로가 있다.	그래프는 연결될 수도 있고(모든 노드가 어떤 노드에서 시작해서 다른 모든 노드에 도달 가능), 분리될 수 도 있다.
구성요소	트리는 연결된 구성요소를 가지지 않는다.	연결된 구성요소는 모든 노드 쌍이 적어도 하나의 경로로 연결되어 있는 하위 그래프이다.

 

이진 트리(Binary Tree)란?

이진 트리는 트리 중에서도 각 노드가 최대 2개의 자식 노드를 가질 때 이진트리(Binary Tree)라고 한다.

최대 2개이기 때문에 자식이 없을 수도 있고, 한개만 있을 수도 있다. 

이때 자식 노드는 각각 왼쪽 자식 노드와 오른쪽 자식 노드로 표현한다.

 

그래서 같은 루트에 같은 자식 노드 하나를 가지고 있어도 자식 노드의 위치가 각각 왼쪽과 오른쪽으로 다르다면 그 두 트리는 서로 다른 트리가 된다.

이진 트리의 종류

• Full Binary Tree: 각각의 노드가 child가 0개 혹은 2개
• Complete Binary Tree: 왼쪽 위에서부터 가득 차 있는 트리
• PerfectBinary Tree: 모든 내부 노드가 2개의 children을 가지고 있으며, leaf node의 level이 같은 트리

이진 트리 순회 알고리즘

트리에 저장된 모든 값을 중복이나 빠짐 없이 살펴보고 싶을 때 사용

이진 트리의 순회 방법 중 깊이 우선 순회 방법(Depth First Traversal)으로는

전위 순회(Pre-order taversal), 정위 순회(In-order traversal), 후위 순회(Post-order traversal)가 있으며,

너비 우선 순회 방법(Breadth First Traversal)으로는 레벨 순회가 있다.

 

• Pre-order : NLR
• In-order : LNR
• Post-order : LRN
• Level-order : NLR

• Pre-order : 1 2 4 5 3 6 7
• In-order : 4 2 5 1 6 3 7
• Post-order : 4 5 2 6 7 3 1
• Level-order : 1 2 3 4 5 6 7

이진 트리 순회 알고리즘 구현

깊이 우선 탐색 방법(DFS)

이진 트리 순회 방법 중 깊이 우선 탐색 방법(DFS)은 재귀적(Recursive) 혹은 반복적(Iterative) 방법으로  구현할 수 있다.

재귀적(Recursive) 방법

Class Tree {
	constructor(value) {
    	this.value = value;
        this.leftNode = null;
        this.rightNode = null;
    }
    
    setValue(value) {
    	this.value = value;
    }
    
    setLeft(node) {
    	this.leftNode = node;
    }
    
    setRight(node) {
    	this.rightNode = node;
    }
}

//전위 순회(Pre-order)
const recursivePreOrder = (node) => {
	if(!node) {
    	return;
    }
    console.log(node.value);
    this.recursivePreOrder(node.leftNode);
    this.recursivePreOrder(node.rightNode);
}

//정위 순회(In-order)
const recursiveInOrder = (node) => {
	if(!node) {
    	return;
    }
    this.recursiveInOrder(node.leftNode);
    console.log(node.value);
    this.recursiveInOrder(node.rightNode);
}

//후위 순회(Post-order)
const recursivePostOrder = (node) => {
	if(!node) {
    	return;
    }
    this.recursivePostOrder(node.leftNode);
    this.recursivePostOrder(node.rightNode);
    console.log(node.value);
}

반복적(Iterative) 방법

반복적인 방법으로 구현할 때는 스택(Stack)을 사용한다.

//전위 순회
const iterativePreOrder = (node) => {
	if(node == null) {
    	return;
    }
    let stack = [];
    stack.push(node);
    
    while(stack.length > 0) {
    	let pop_node = stack.pop();
        console.log(pop_node.value);
        if(pop_node.right) stack.push(pop_node.right);
        if(pop_node.left) stack.push(pop_node.left);
    }
};

//중위 순회
const iterativeInOrder = (node) => {
	if(node == null) {
    	return;
    }
    let crnt_node = node;
    let stack = [];
    while(true) {
    	if(crnt_node != null) {
        	stack.push(crnt_node);
            crnt_node = crnt_node.left;
        } else if (stack.length > 0) {
        	crnt_node = stack.pop();
            console.log(crnt_node.value);
            crnt_node = crnt_node.right;
        } else {
        	break;
        }
    }
}

//후위 순회
const iterativePostOrder = (node) => {
	if(node == null) {
    	return;
    }
    let crnt_node = node;
    let stack = [];
    let last_visit_node = null;
    while (true) {
    	if (crnt_node != null) {
        	stack.push(crnt_node);
            crnt_node = crnt_node.left;
        } else if (stack.length > 0) {
        	peek_node = stack[stack.length -1];
            if (peek_node.right != null && last_visit_node != peek_node.right) {
            	crnt_node = peek_node.right;
            } else {
            	console.log(peek_node.value);
                last_visit_node = stack.pop();
            }
        } else {
        	break;
        }
    }
}

 

너비 우선 순회 방법(BFS)

너비 우선 순회에는 레벨 순회가 있다. 큐(queue) 자료구조를 사용하면 간단히 구현할 수 있다.

const levelOrderTraversal = (node) => {
	if(node == null){
    	return;
    }
    let queue = [];
    queue.push(node);
    while(queue.length > 0) {
    	let pop_node = queue.shift();
        console.log(pop_node.value);
    	if(pop_node.left) queue.push(pop_node.left);
        if(pop_node.right) queue.push(pop_node.right);
    }
};

levelOrderTraversal(root);