22-11-02-자료구조, 알고리즘 (3)

트리와 그래프

obejct, array로 트리나 링크드리스트 구현하지 않고 클래스로 구현하는 이유
1. 더 라이트한 모델을 위해
2. 확장성
3. 객체 지향 프로그래밍 철학에 맞아서

class Node {
  	constructor(data) {
    	this.data = data;
		this.right = null;
		this.left = null;
    }
}
class Tree {
	constructor(data) {
    	let init = new Node(data);
      	this.root = init;
      	this.length = 0;
    }
  	insert(data) {
    	let 새로운노드 = new Node(data);
      	let 순회용현재노드 = this.root;
      	while(순회용현재노드) {
        	if (data == 순회용현재노드.data) {
            	// 들어오는 값이 이미 존재하는 경우
              	return;
            } else if (data < 순회용현재노드.data) {
            	// 왼쪽에 붙이기
              	// 왼쪽이 비었으면 붙이고 존재한다면 더 타고 내려가기
              	if (!순회용현재노드.left) {
                	// 비어있는 경우 데이터 넣기 -> 순회용현재노드.left 빈 경우 null 이지만 !를 통해 true로 변환시켜 해당 if문 실행
					순회용현재노드.left = 새로운노드;
                  	this.length += 1;
                  	return;
                }
              	// 값이 존재하는 경우 밑으로 내려가기!
              	순회용현재노드 = 순회용현재노드.left;
            } else if (data > 순회용현재노드.data) {
            	// 오른쪽에 붙이기
              	if (!순회용현재노드.right) {
                	순회용현재노드.right = 새로운노드;
                  	this.length +=1;
                  	return;
                }
              	순회용현재노드 = 순회용현재노드.right;
            }
        }
    }
}
let t = new Tree(5)
t.insert(3);
t.insert(8);
t.insert(1);
t.insert(4);
t.insert(6);
t.insert(9);

깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS)

• DFS 구현하기 (스택 이용)

DFS {
	let 방문경로 = [];
  	let 스택 = [this.root];
  
  	while(스택.length != 0) {
      	// 스택에서 빠져서 current에 넣기
    	let current = 스택.pop();
      	if (current.right) {
        	스택.push(current.right);
        }
      	if (current.left) {
        	스택.push(current.left);
        }
      	방문경로.push(current.data);
    }
  	return 방문경로;
}

• BFS 구현하기 (큐 이용)

// 맨 앞 데이터 꺼내기 - shift()
DFS {
	let 방문경로 = [];
  	let 큐 = [this.root];
  
  	while(큐.length != 0) {
      	// 스택에서 빠져서 current에 넣기
    	let current = 큐.shift();
      	if (current.right) {
        	큐.push(current.right);
        }
      	if (current.left) {
        	큐.push(current.left);
        }
      	방문경로.push(current.data);
    }
  	return 방문경로;
}