이진 트리 (Binary Tree)
Binary Tree 🙂
이진 트리(Binary Tree)는 최대 2개의 자식을 가질 수 있는 노드들로 구성된 트리입니다. 데이터를 2개까지만 담을 수 있어 저장의 용도로 쓰기에는 조금 아쉬운 트리이지만, 데이터를 아주 빠르게 찾을 수 있는 이진 탐색(Binary Search)이나 수식을 트리 형태로 표현하여 계산하는 수식 트리(Expression Tree) 등에 활용할 수 있는 개성 넘치는 트리입니다.
이진 트리의 종류로 포화 이진 트리(FBT: Full Binary Tree)와 완전 이진 트리(CBT: Complete Binary Tree)라는 것도 있습니다. 포화 이진 트리는 잎이 되는 모든 노드가 채워진 이진 트리를 의미하고, 완전 이진 트리는 잎이 되는 노드들이 왼쪽부터 빼곡하게 자리를 채운 트리를 의미합니다. 이진 트리를 이용한 탐색을 하려면 기본적으로 완전 이진 트리의 형태를 갖추고 있어야 하기 때문에 추가로 소개했습니다.
본문에서는 이진 트리의 노드를 간단하게 연결했고, 트리를 순회하는 3가지 방법에 대해서만 구현했습니다.
노드 & 트리 생성
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor({ root }) {
this.root = root;
}
}
const tree = new BinaryTree({ root: new Node('A') });
이진 트리의 노드는 왼쪽과 오른쪽 자식을 가질 수 있으므로, Node 클래스를 위와 같이 만들어야 합니다. 그리고 순회 메소드를 구현하기 위해 트리도 생성자 함수로 만들었으며, 매개변수는 비구조화 문법(Destructuring)을 사용해 받도록 했습니다.
자식 추가
append({ parent, child }) {
if (parent.left === null) {
parent.left = child;
} else if (parent.right === null) {
parent.right = child;
} else {
throw new Error('Child node is not empty!');
}
}
tree.append({ parent: tree.root, child: new Node('B') });
tree.append({ parent: tree.root.left, child: new Node('C') });
tree.append({ parent: tree.root.left, child: new Node('D') });
tree.append({ parent: tree.root, child: new Node('E') });
tree.append({ parent: tree.root.right, child: new Node('F') });
tree.append({ parent: tree.root.right, child: new Node('G') });
자식을 추가하는 메소드인 append는 좌우가 비어 있는지만 체크하는 식으로 간단하게 구현했습니다.
전위 순회 (Preorder Traversal)
preorder(node = this.root) {
if (node === null) return;
process.stdout.write(`${node.data} `);
this.preorder(node.left);
this.preorder(node.right);
}
preorderByLoop() {
const stack = [];
stack.push(this.root);
while (true) {
if (stack.length === 0) {
console.log();
return;
}
const popped = stack.pop();
process.stdout.write(`${popped.data} `);
if (popped.right !== null) stack.push(popped.right);
if (popped.left !== null) stack.push(popped.left);
}
}
전위 순회는 루트 노드부터 시작하여 왼쪽으로 내려오면서, 최하위 왼쪽 노드까지 먼저 방문합니다. 최하위 왼쪽 노드까지 방문했다면, 그 다음에는 오른쪽 노드를 방문하는 식으로 순회합니다. 재귀 함수와 반복문을 이용해 구현했으며, 반복문의 경우 스택을 사용했습니다. 스택이 후입선출(Last In, First Out)의 구조를 띄고 있기 때문에, 오른쪽 자식을 먼저 삽입했습니다.
중위 순회 (Inorder Traversal)
inorder(node = this.root) {
if (node === null) return;
this.inorder(node.left);
process.stdout.write(`${node.data} `);
this.inorder(node.right);
}
inorderByLoop() {
const stack = [];
let temp = this.root;
while (true) {
for (; temp !== null; temp = temp.left) {
stack.push(temp);
}
if (stack.length === 0) {
console.log();
return;
}
const popped = stack.pop();
process.stdout.write(`${popped.data} `);
temp = popped.right;
}
}
중위 순회는 최하위 왼쪽 노드부터 방문한 다음 루트를 거쳐 오른쪽 노드를 방문하는 식으로 동작합니다. 반복문을 통한 구현은 전위 순회와 동일하게 스택을 사용했습니다. 하지만 중위 순회는 최하위 왼쪽 노드부터 순회하므로, 앞 쪽에서 모든 왼쪽 노드를 스택에 삽입해야 합니다.
후위 순회 (Postorder Traversal)
postorder(node = this.root) {
if (node === null) return;
this.postorder(node.left);
this.postorder(node.right);
process.stdout.write(`${node.data} `);
}
postorderByLoop() {
const stack = [];
stack.push(this.root);
while (true) {
if (stack.length === 0) {
console.log();
return;
}
const top = stack[stack.length - 1];
const topLeft = top.left;
if (topLeft !== null && !topLeft.visited) {
stack.push(topLeft);
} else {
const topRight = top.right;
if (topRight !== null && !topRight.visited) {
stack.push(topRight);
} else {
const popped = stack.pop();
process.stdout.write(`${popped.data} `);
popped.visited = true;
}
}
}
}
후위 순회는 전위 순회와 반대되는 공식을 가지고 있으며, 왼쪽, 오른쪽, 루트 순으로 방문합니다. 후위 순회 역시 스택을 사용하나, 순회 시 노드마다 방문 여부를 체크해야 합니다. 예제 코드에는 없지만 저는 visited라는 변수를 Node 생성자에 별도로 추가해 방문 여부를 확인할 수 있도록 했습니다. 앞의 두 순회와 달리 방문 여부까지 고려해야 하므로 처음에는 어려울 수 있지만, 한 번 읽어 보시면 금방 이해하실 거라 생각합니다.
References 📝
본문의 내용은 GeeksforGeeks의 자료구조 튜토리얼을 참고해 작성했습니다 ❤️
'💻 컴퓨터공학 > 자료구조' 카테고리의 다른 글
분리 집합 (Disjoint Set) (0) | 2021.10.26 |
---|---|
수식 트리 (Expression Tree) (0) | 2021.10.26 |
LCRS 트리 (LCRS Tree) (0) | 2021.10.25 |
큐 (Queue) (0) | 2021.10.14 |
스택 (Stack) (0) | 2021.10.14 |
댓글
이 글 공유하기
다른 글
-
분리 집합 (Disjoint Set)
분리 집합 (Disjoint Set)
2021.10.26 -
수식 트리 (Expression Tree)
수식 트리 (Expression Tree)
2021.10.26 -
LCRS 트리 (LCRS Tree)
LCRS 트리 (LCRS Tree)
2021.10.25 -
큐 (Queue)
큐 (Queue)
2021.10.14