오늘 배우는건 어떤 트리에서든지 사용할 수 있는 개념이다.
트리를 순회하는데 두가지 방식
너비 우선
깊이 우선
자식 노드를 보기 전에 먼저 형제 노드를 다 보는것이다.
10
6 15
3 8 20
queue : []
visited : [10,6,15,3,8,20]
class Node{
constructor(value){
this.value = value; // 각 노드는 값을 가진다.
this.left = null; // left 값과
this.right = null; // right 값
}
}
class BinarySearchTree{
constructor(){
this.root = null; // 딱 하나의 중요한 프로퍼티를 가진다. 루트!
}
insert(value){
let newNode = new Node(value);
if(this.root === null){
this.root = newNode;
return this;
}else{
let current = this.root;
while(true){
if(value < current.value){
if(current.left === null){
current.left = newNode;
return this;
}
current = current.right;
}
}
}
// 값, 노드를 출력하는 find
find(value){
if(this.root === null) return false;
let current = this.root,
found = false;
while(!found && current){
if(value < current.value){
current = current.left;
}else if(value > current.value){
current = current.right;
}else{
found = true;
}
}
if(!found) return undefined; // 값에 이 트리에 없다면
return current;
}
// 참과 거짓을 출력하는 contains고
contains(value){
if(this.root === null) return false;
let current = this.root,
found = false;
while(!found && current){
if(value < current.value){
current = current.left;
}else if(value > current.value){
current = current.right;
}else{
return true;
}
}
return false;
}
BFS(){
let data = [],
queue = [],
node = this.root
queue.push(node)
while(queue.length>0){
node = queue.shift() //선입선출
data.push(node.value) // 출력할 목록에 node를 더하는것
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
return data // 데이터에는 지금까지 거쳐온 변수들이 저장되어있음
//QUEUE : [15,3,8]
//DATA: [10,6]
// 10
// 6 15
// 3 8 20
}
}
깊이 우선 탐색에는 세가지 종류가 있다. DFS알고리즘이다.
: 왼쪽 전체를 순회하고 나서 오른쪽 전체를 순회하는 방식
class Node{
constructor(value){
this.value = value; // 각 노드는 값을 가진다.
this.left = null; // left 값과
this.right = null; // right 값
}
}
class BinarySearchTree{
constructor(){
this.root = null; // 딱 하나의 중요한 프로퍼티를 가진다. 루트!
}
insert(value){
let newNode = new Node(value);
if(this.root === null){
this.root = newNode;
return this;
}else{
let current = this.root;
while(true){
if(value < current.value){
if(current.left === null){
current.left = newNode;
return this;
}
current = current.right;
}
}
}
// 값, 노드를 출력하는 find
find(value){
if(this.root === null) return false;
let current = this.root,
found = false;
while(!found && current){
if(value < current.value){
current = current.left;
}else if(value > current.value){
current = current.right;
}else{
found = true;
}
}
if(!found) return undefined; // 값에 이 트리에 없다면
return current;
}
// 참과 거짓을 출력하는 contains고
contains(value){
if(this.root === null) return false;
let current = this.root,
found = false;
while(!found && current){
if(value < current.value){
current = current.left;
}else if(value > current.value){
current = current.right;
}else{
return true;
}
}
return false;
}
BFS(){
let data = [],
queue = [],
node = this.root
queue.push(node)
while(queue.length>0){
node = queue.shift() //선입선출
data.push(node.value) // 출력할 목록에 node를 더하는것
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
return data // 데이터에는 지금까지 거쳐온 변수들이 저장되어있음
//QUEUE : [15,3,8]
//DATA: [10,6]
// 10
// 6 15
// 3 8 20
}
DFSPreOrder(){
let data = [];
let current = this.root;
function traverse(node){
data.push(node.value);
if(node.left) traverse(node.left);
if(node.right) traverse(node.right);
}
traverse(current)
return data;
}
}
결과는 [10,6,3,8,15,20]
후위 탐색을 보겠다. 위에서 한걸 약간 순서만 바꾸면 된다. 그러나, 실제 결과로 나오는 순서에는 아주 큰 차이가 발생한다.
class Node{
constructor(value){
this.value = value; // 각 노드는 값을 가진다.
this.left = null; // left 값과
this.right = null; // right 값
}
}
class BinarySearchTree{
constructor(){
this.root = null; // 딱 하나의 중요한 프로퍼티를 가진다. 루트!
}
insert(value){
let newNode = new Node(value);
if(this.root === null){
this.root = newNode;
return this;
}else{
let current = this.root;
while(true){
if(value < current.value){
if(current.left === null){
current.left = newNode;
return this;
}
current = current.right;
}
}
}
// 값, 노드를 출력하는 find
find(value){
if(this.root === null) return false;
let current = this.root,
found = false;
while(!found && current){
if(value < current.value){
current = current.left;
}else if(value > current.value){
current = current.right;
}else{
found = true;
}
}
if(!found) return undefined; // 값에 이 트리에 없다면
return current;
}
// 참과 거짓을 출력하는 contains고
contains(value){
if(this.root === null) return false;
let current = this.root,
found = false;
while(!found && current){
if(value < current.value){
current = current.left;
}else if(value > current.value){
current = current.right;
}else{
return true;
}
}
return false;
}
BFS(){
let data = [],
queue = [],
node = this.root
queue.push(node)
while(queue.length>0){
node = queue.shift() //선입선출
data.push(node.value) // 출력할 목록에 node를 더하는것
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
return data // 데이터에는 지금까지 거쳐온 변수들이 저장되어있음
//QUEUE : [15,3,8]
//DATA: [10,6]
// 10
// 6 15
// 3 8 20
}
DFSPreOrder(){
let data = [];
let current = this.root;
function traverse(node){
data.push(node.value);
if(node.left) traverse(node.left);
if(node.right) traverse(node.right);
}
traverse(current)
return data;
}
}
DFSPostOrder(){
let data = [];
function traverse(node){
if(node.left) traverse(node.left)
if(node.right) traverse(node.right)
data.puah(node.value);
}
traverse(this.root);
return data;
}
// 결과 [3,8,6,20,15]
1) 어느 시점에서든 노드를 방문해야 한다.
2) 왼쪽 전체를 순회해야 한다.
3) 오른쪽 전체를 순회해야 한다.
정위탐색에서는 먼저 왼쪽 전체를 순회하고 노드를 방문하고 그다음, 오른쪽 전체를 순회한다.
기본적으로 위와 같은 의사코드다.
//결과 [3,6,8,10,15,20]
class Node{
constructor(value){
this.value = value; // 각 노드는 값을 가진다.
this.left = null; // left 값과
this.right = null; // right 값
}
}
class BinarySearchTree{
constructor(){
this.root = null; // 딱 하나의 중요한 프로퍼티를 가진다. 루트!
}
insert(value){
let newNode = new Node(value);
if(this.root === null){
this.root = newNode;
return this;
}else{
let current = this.root;
while(true){
if(value < current.value){
if(current.left === null){
current.left = newNode;
return this;
}
current = current.right;
}
}
}
// 값, 노드를 출력하는 find
find(value){
if(this.root === null) return false;
let current = this.root,
found = false;
while(!found && current){
if(value < current.value){
current = current.left;
}else if(value > current.value){
current = current.right;
}else{
found = true;
}
}
if(!found) return undefined; // 값에 이 트리에 없다면
return current;
}
// 참과 거짓을 출력하는 contains고
contains(value){
if(this.root === null) return false;
let current = this.root,
found = false;
while(!found && current){
if(value < current.value){
current = current.left;
}else if(value > current.value){
current = current.right;
}else{
return true;
}
}
return false;
}
BFS(){
let data = [],
queue = [],
node = this.root
queue.push(node)
while(queue.length>0){
node = queue.shift() //선입선출
data.push(node.value) // 출력할 목록에 node를 더하는것
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
return data // 데이터에는 지금까지 거쳐온 변수들이 저장되어있음
//QUEUE : [15,3,8]
//DATA: [10,6]
// 10
// 6 15
// 3 8 20
}
DFSPreOrder(){
let data = [];
let current = this.root;
function traverse(node){
data.push(node.value);
if(node.left) traverse(node.left);
if(node.right) traverse(node.right);
}
traverse(current)
return data;
}
}
DFSPostOrder(){
let data = [];
function traverse(node){
if(node.left) traverse(node.left)
if(node.right) traverse(node.right)
data.puah(node.value);
}
traverse(this.root);
return data;
}
DFSInOrder(){
let data = [];
function traverse(node){
node.left && traverse(node.left)
data.push(node.value)
node.right && traverse(node.right)
// data.push(node.value) 여기에도 작성해야 하는줄 알았는데 쌤은 안씀
}
traverse(this.root);
return data;
}
어떤 것이 더 나은지, 어떤 것을 사용해야 하는지를 다뤄보자.
=> 상황에 따라 다르다.
만약에 트리가 아주 넓은 모양의 구조라면, 너비 우선은 큐를 저장하는데 더 많은 공간을 차지한다.
아주 깊고 긴 트리라면 깊이 우선이 더 많은 공간을 사용한다.
사실, 다른 것들에 비해서 하나를 골라 사용해야 하는 좋은 예시 상황은 없다
그래도 예시를 좀 들어보자)
[3,6,8,10,15,20] => 이건 정위순회인 것을 알 수 있다.
[10,6,3,8,15,20]