LCRS 트리 (LCRS Tree)
글 작성자: NoHack
728x90
LCRS Tree 🙂
LCRS 트리에서 LCRS는 Left Child, Right Siblings를 의미합니다. 그렇기에 이 트리는 왼쪽에는 자식이 붙고, 오른쪽에는 형제 노드만 붙는 형태의 트리라 볼 수 있습니다. 일반적으로 트리를 표현하는 방법은 다소 복잡한 편이지만, 이 트리는 왼쪽 자식에 대한 포인터와 오른쪽 형제에 대한 포인터만 있으면 모든 노드를 참조할 수 있기 때문에 구현이 간단합니다. 이 외에도 트리를 표현하는 방법으로 이진 트리(Binary Tree)가 있는데, 다음 시간에 알아 보도록 하겠습니다.
노드 생성
function LCRSNode(data) {
this.data = data;
this.leftChild = null;
this.rightSibling = null;
}
const root = new LCRSNode('A');
const b = new LCRSNode('B');
const c = new LCRSNode('C');
앞서 언급한 것처럼 LCRS 트리의 노드는 왼쪽은 자식, 오른쪽은 형제에 대한 정보만 담으면 됩니다.
노드 추가
const appendChild = (parent, child) => {
if (parent.leftChild === null) {
parent.leftChild = child;
} else {
let temp = parent.leftChild;
while (temp.rightSibling !== null) {
temp = temp.rightSibling;
}
temp.rightSibling = child;
}
};
메소드로 작성할 만큼의 기능은 없기 때문에, 외부 함수로 만들었습니다. parent에 연결할 child 노드는 leftChild가 비어 있다면 그 자리를 차지하면 되고, 그렇지 않다면 rightSibling의 끝으로 이동해 붙이면 됩니다.
트리 출력
const printTree = (node, depth) => {
if (node === null) return;
for (let i = 0; i < depth; i++) {
process.stdout.write(' ');
}
process.stdout.write(`${node.data}\n`);
if (node.leftChild !== null) printTree(node.leftChild, depth + 1);
if (node.rightSibling !== null) printTree(node.rightSibling, depth);
};
트리를 출력하는 부분은 depth라는 매개변수를 추가로 사용해, 트리의 깊이에 따라 들여쓰기를 함께 출력할 수 있도록 했습니다. 왼쪽 노드는 자식이므로 depth + 1을, 그리고 오른쪽은 형제이므로 depth 값에 변화가 없음을 유의해야 합니다.
References 📝
본문의 내용은 GeeksforGeeks의 LCRS Tree 자료를 참고해 작성했습니다 ❤️
'💻 컴퓨터공학 > 자료구조' 카테고리의 다른 글
수식 트리 (Expression Tree) (0) | 2021.10.26 |
---|---|
이진 트리 (Binary Tree) (0) | 2021.10.26 |
큐 (Queue) (0) | 2021.10.14 |
스택 (Stack) (0) | 2021.10.14 |
원형 링크드 리스트 (Circular Linked List) (0) | 2021.10.13 |
댓글
이 글 공유하기
다른 글
-
수식 트리 (Expression Tree)
수식 트리 (Expression Tree)
2021.10.26 -
이진 트리 (Binary Tree)
이진 트리 (Binary Tree)
2021.10.26 -
큐 (Queue)
큐 (Queue)
2021.10.14 -
스택 (Stack)
스택 (Stack)
2021.10.14