의미
(출처: Introduction to Tree – Data Structure and Algorithm Tutorials)
부모-자식 관계에 있는 노드로 구성된 비선형 데이터 구조
구조
- Root : 트리 구조에서 최상위에 있는 노드
- 자식 노드(Child): Root를 기준으로 부모 노드 아래 바로 연결된 노드
- 부모 노드(Parent): 자식 노드를 가지고 있는 노드
- 형제 노드(Siblings): 같은 부모 노드를 가진 노드
- Leaf: 자식이 없는 노드
- Edge: 각각의 노드 간의 연결
종류
이진 트리(Binary Trees)
(출처: 위키피디아, Binary tree)
각각의 노드가 최대 2개의 자식 노드를 가지는 트리
이진 탐색 트리(Binary Search Tress)
출처: java T point, Binary Search tree
- 부모 노드의 왼쪽에 위치한 자식 노드가 부모 노드보다 항상 작고, 부모 노드의 오른쪽에 위치한 자식 노드가 부모 노드보다 항상 큰 이진 트리
- 데이터가 반드시 정렬되어있어야 사용할 수 있음
의사코드
-
left, right, mid 변수 선언 및 할당하기
1-1. left: array에 0번째 인덱스
1-2. right: array에 맨 마지막 요소의 인덱스
1-3. mid: array의 중간 요소의 인덱스. 단 소수점은 내리기
-
array[mid]이 target이 아니고 left가 right보다 작거나 같을 때까지 while문 반복
2-1. array[mid] < target 이면 left = mid + 1 하기
2-2. array[mid] > target 이면 righ = mid - 1 하기
-
while문을 빠져나왔을 때, array[mid] === target이면 mid값 리턴
3-1. 그렇지 않으면 -1 리턴
코드 작성하기
function binarySearch(array, target){
let left = 0;
let right = array.length - 1;
let mid = Math.ceil((right + left) / 2);
while(array[mid] !== target && left <= right) {
if (array[mid] < target) {
left = mid + 1;
}else {
right = mid - 1;
}
mid = Math.ceil((right + left) / 2);
}
if(array[mid] === target) {
return mid
}
return -1
}트리 순회(Tree Traversal)
- 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
- 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽임
너비 우선 탐색(BFS)
코드 작성해보기
문제
임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 너비 우선 탐색(BFS, Breadth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다.
입력
인자 1 : node
'value', 'children' 속성을 갖는 객체 (Node)
'node.value'는 number 타입
'node.children'은 Node를 요소로 갖는 배열
출력
배열을 리턴해야 합니다.
주의사항
생성자 함수(Node)와 메소드(addChild)는 변경하지 않아야 합니다.
입출력 예시
let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = bfs(root);
console.log(output); // --> [1, 2, 3, 4, 5]
leaf1.addChild(new Node(6));
rootChild2.addChild(new Node(7));
output = bfs(root);
console.log(output); // --> [1, 2, 3, 4, 5, 7, 6]의사코드
1. 결과를 담을 배열(result)을 만든다.
2. queue 배열을 만들고 배열에 node를 넣는다.
3. queu 배열의 길이가 0이 될 때까지 while 반복문 실행
3-1. queue 배열의 첫번째 요소를 head로 지정
3-2. queue 배열에서 첫번째 요소를 제외한 배열을 변수 queue에 재할당
3-3. head의 값을 result에 추가
3-4. head의 각각의 자식 노드를 queue에 추가하기
4. result 리턴하기코드
let bfs = function (node) {
// TODO: 여기에 코드를 작성합니다.
const result = [];
let queue = [node];
while (queue.length) {
const head = queue[0];
queue = queue.slice(1);
result.push(head.value);
head.children.forEach((child) => queue.push(child));
}
return result
};
// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
this.value = value;
this.children = [];
};
// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
this.children.push(child);
return child;
};깊이 우선 탐색(DFS)
전위 순회(Pre Order)
맨 처음에 Root 노드를 방문한 뒤, 하위 노드 방문
코드 작성해보기
문제
임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다.
입력
인자 1 : node
'value', 'children' 속성을 갖는 객체 (Node)
'node.value'는 number 타입
'node.children'은 Node를 요소로 갖는 배열
출력
배열을 리턴해야 합니다.
주의사항
생성자 함수(Node)와 메소드(addChild)는 변경하지 않아야 합니다.
입출력 예시
let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = dfs(root);
console.log(output); // --> [1, 2, 4, 5, 3]
leaf1.addChild(new Node(6));
rootChild2.addChild(new Node(7));
output = dfs(root);
console.log(output); // --> [1, 2, 4, 6, 5, 3, 7]의사코드
1. result 배열에 루트 노드 넣기
2. 노드의 chilren을 하나하나 순회하면서 dfs(n)을 실행
2-1. result와 concat하기
3. result 리턴하기코드
let dfs = function (node) {
// TODO: 여기에 코드를 작성합니다.
let result = [node.value];
node.children.forEach((child) => result = result.concat(dfs(child)));
return result
};
// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
this.value = value;
this.children = [];
};
// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
this.children.push(child);
return child;
};
중위 순회(In Order)
왼쪽 최하위 노드에서 시작해서 Root 노드 방향으로 올라가면서 노드 방문 후 다시 하위 노드 방문
후위 순회(Post Order)
하위 노드 모두 방문 후 Root 노드를 맨 마지막에 방문
