이진트리(Binary Tree)란 하나의 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리를 말한다.
어떤 하나의 노드를 부모 노드(parent node)라고 할 때, 왼쪽 자식 노드(left child node)와 오른쪽 자식 노드(right child node)가 존재할 수 있다.
class Node {
constructor(_data) {
this.data = _data;
this.leftChild = null;
this.rightChild = null;
this.parent = null;
this.sibling = null;
}
}
class BinaryTree {
//_data를 루트노드로 가지는 BinaryTree 초기화
constructor(_data) {
this.root = new Node(_data);
this.level = 1;
this.height = 1;
}
// targetNode의 왼쪽에 _data를 자식 노드로 추가
insertLeftChildNode(targetNode, _data) {
if (this.root) {
const newNode = new Node(_data);
newNode.parent = this.root;
if (this.root.rightChild) {
newNode.sibling = this.root.rightChild;
this.root.rightChild.sibling = newNode;
}
targetNode.leftChild = newNode;
}
}
// targetNode의 오른쪽에 _data를 자식 노드로 추가
insertRightChildNode(targetNode, _data) {
if (this.root) {
const newNode = new Node(_data);
newNode.parent = this.root;
if (this.root.leftChild) {
newNode.sibling = this.root.leftChild;
this.root.leftChild.sibling = newNode;
}
targetNode.rightChild = newNode;
}
}
// 전위 순회(TLR)
preOrder(node) {
if (node) {
console.log(node.data);
this.preOrder(node.leftChild);
this.preOrder(node.rightChild);
}
}
// 중위 순회(LTR)
inOrder(node) {
if (node) {
this.inOrder(node.leftChild);
console.log(node.data);
this.inOrder(node.rightChild);
}
}
// 후위 순회(LRT)
postOrder(node) {
if (node) {
this.postOrder(node.leftChild);
this.postOrder(node.rightChild);
console.log(node.data);
}
}
// targetNode의 왼쪽 자식 노드를 반환
getLeftChildNode(targetNode) {
return targetNode.leftChild;
}
// targetNode의 오른쪽 자식 노드를 반환
getRightChildNode(targetNode) {
return targetNode.rightChild;
}
getRootNode() {
return this.root;
}
}
const tree = new BinaryTree(1);
tree.insertLeftChildNode(tree.root, 2);
tree.insertLeftChildNode(tree.root.leftChild, 3);
tree.insertRightChildNode(tree.root, 4);
tree.postOrder(tree.root);