[자료구조] 이진탐색트리 구현 - 중위순회, 전위순회, 후위순회 메소드
2021. 3. 16. 10:57ㆍFront-end/자료구조
728x90
반응형
중위순회(in-order traversal) : (왼쪽 - 루트 - 오른쪽)
- 오름차순(작은 값에서 큰 값 순)으로 방문된다.
- 트리 정렬 시 사용되는 방법임
전위순회(pre-order traversal) : (루트 - 왼쪽 - 오른쪽)
- 자식 노드보다 노드 자신을 먼저 방문한다.
- 구조화된 문서를 출력할 때 많이 이용하는 방법
후위순회(post-order traversal) : (왼쪽 - 오른쪽 - 루트)
- 자식 노드를 노드 자신보다 먼저 방문
- 디렉토리와 서브 디렉토리의 파일 용량을 계산할 때 쓰는 방법
//in-order traversal 중위순회 (왼쪽 - 루트 - 오른쪽)
inOrderTraverse(callback){
this.inOrderTraverseNode(this.root, callback);
}
inOrderTraverseNode(node, callback){
if(node !== null){
this.inOrderTraverseNode(node.left, callback);
callback(node.key);
this.inOrderTraverseNode(node.right, callback);
}
}
//pre-order traversal 전위순회 (루트 - 왼쪽 - 오른쪽)
preOrderTraverse(callback){
this.preOrderTraverseNode(this.root,callback);
}
preOrderTraverseNode(node, callback){
if(node !== null){
callback(node.key);
this.preOrderTraverseNode(node.left, callback);
this.preOrderTraverseNode(node.right, callback);
}
}
//post-order traversal 후위순회 (왼쪽-오른쪽-루트)
postOrderTraverse(callback){
this.postOrderTraverseNode(this.root, callback);
}
postOrderTraverseNode(node, callback){
if(node !== null){
this.postOrderTraverseNode(node.left, callback);
this.postOrderTraverseNode(node.right, callback);
callback(node.key);
}
}
사용 방법
예를 들면 callback이 const printValue = (value) => console.log(value);
라면 사용할 때 이렇게 함수를 정의해주고 인자로 넣어주면 된다.
insert메소드와 순회 메소드까지 구현한 전체 코드와 사용하는 코드는 다음과 같다.
class Node{
constructor(key){
this.key = key;
this.left = null;
this.right = null;
}
}
class BinarySearchTree{
constructor(){
this.root = null;
}
insert(key){
let newNode = new Node(key);
if(this.root === null){
this.root = newNode;
}else{
this.insertNode(this.root,newNode);
}
}
insertNode(node, newNode){
if(newNode.key < node.key){
if(node.left === null){
node.left = newNode;
}else{
this.insertNode(node.left, newNode);
}
}else{
if(node.right === null){
node.right = newNode;
}else{
this.insertNode(node.right, newNode);
}
}
}
//in-order traversal 중위순회 (왼쪽 - 루트 - 오른쪽)
inOrderTraverse(callback){
this.inOrderTraverseNode(this.root, callback);
}
inOrderTraverseNode(node, callback){
if(node !== null){
this.inOrderTraverseNode(node.left, callback);
callback(node.key);
this.inOrderTraverseNode(node.right, callback);
}
}
//pre-order traversal 전위순회 (루트 - 왼쪽 - 오른쪽)
preOrderTraverse(callback){
this.preOrderTraverseNode(this.root,callback);
}
preOrderTraverseNode(node, callback){
if(node !== null){
callback(node.key);
this.preOrderTraverseNode(node.left, callback);
this.preOrderTraverseNode(node.right, callback);
}
}
//post-order traversal 후위순회 (왼쪽-오른쪽-루트)
postOrderTraverse(callback){
this.postOrderTraverseNode(this.root, callback);
}
postOrderTraverseNode(node, callback){
if(node !== null){
this.postOrderTraverseNode(node.left, callback);
this.postOrderTraverseNode(node.right, callback);
callback(node.key);
}
}
}
let tree = new BinarySearchTree();
tree.insert(11); // 11은 루트노드가 된다.
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
console.log(tree);
const printNode = (value) => {
console.log(value);
}
console.log('------------중위순회------------');
tree.inOrderTraverse(printNode); // 중위순회(in-order traversal, 왼쪽-루트-오른쪽)
console.log('------------전위순회------------');
tree.preOrderTraverse(printNode); // 전위순회(pre-order traversal, 루트-왼쪽-오른쪽)
console.log('------------후위순회------------');
tree.postOrderTraverse(printNode); // 후위순회(post-order traversal, 왼쪽-오른쪽-루트)
728x90
반응형
'Front-end > 자료구조' 카테고리의 다른 글
[자료구조] 이진탐색트리 구현 - 삭제 (0) | 2021.03.17 |
---|---|
[자료구조] 이진탐색트리 구현 - 최솟값, 최댓값 찾기 / 특정 값 찾기 (0) | 2021.03.17 |
[자료구조] 이진탐색트리 구현 - 기본 뼈대, insert 메소드 (0) | 2021.03.15 |
[자료구조] 트리 - 이진 탐색 트리(Binary Search Tree) (0) | 2021.03.15 |
[자료구조] 트리 (0) | 2021.03.15 |