[TIL 23][Data Structure] Tree - 1
13251 단어 TILdata structureTIL
개요
Tree는 이름처럼 나무가 뿌리를 내리는듯한 구조로 되어있다.
트리 중 가장 최상위에 위치한 Node를 Root Node라고 부른다.
function tree(value){
this.value = value;
this.children = [];
}
1. 이진트리
- 이진트리는 자식 노드가 왼쪽, 오른쪽 두개뿐인 트리이다.
function binaryTreeNode(value) {
this.value = value;
this.left = null;
this.right = null;
}
function binaryTree(){
this.root = null;
}
이진트리의 순회 방법
- 순회의 방법 기준은 root node(현재 node)의 기준점에 따라 순회 과정이 진행된다.
선순위 순회 (pre-order)
선순위 순회는 root(현재 node) -> 왼쪽 -> 오른쪽순으로 진행된다.
과정
- root인 1번이 출력
- 왼쪽 node 시작
- root의 왼쪽에 위치한 node 2번 출력
- 2번 node의 왼쪽에 위치한 node 3번 출력
- 2번 node의 오른쪽에 위치한 node 4번 출력
- 왼쪽 node 끝
- 오른쪽 node 시작
- root의 오른쪽에 위치한 node 5번 출력
- 5번 node 왼쪽에 위치한 node 6번 출력
- 5번 node 오른쪽에 위차한 node 7번 출력
- 오른쪽 node 끝
- 순회 완료
코드
function preOrderIteration(){
// 빈 스택에 루트 추가
let nodeStack = [];
nodeStack.push(this.root);
// 모든 항목 하나씩 출력
while(nodeStack.length){
// 스택 최상위 항목 꺼내서 출력
let node = nodeStack.pop();
// 꺼낸 노드의 오른쪽, 왼쪽 자식 노드를 스택에 추가
if(node.right)
nodeStack.push(node.right)
if(node.left)
nodeStack.push(node.left)
}
}
중순위 순회 (in-order)
중순위 순회는 왼쪽 -> root(현재 node) -> 오른쪽순으로 진행된다.
과정
- 왼쪽 node 시작
- 왼쪽인 1번이 출력
- 1번 node의 root인 node 2번 출력
- node 2번의 오른쪽 자식인 node 3번 출력
- 왼쪽 node 끝
- node 2번의 root인 node 4번 출력
- 오른쪽 node 시작
- 오른쪽 노드들의 왼쪽 node인 5번 출력
- 5번 node의 root인 node 6번 출력
- root node 5번의 오른쪽 자식 node인 7번 출력
- 오른쪽 node 끝
- 순회 완료
코드
function inOrderIterate(){
let current = this.root;
let s = [];
let done = false;
while(!done){
if (current !== null) {
s.push(current);
current = current.left;
} else {
if (s.length) {
current = s.pop();
current = current.right;
} else {
done = true;
}
}
}
}
후순위 순회 (post-order)
후순위 순회는 왼쪽 -> 오른쪽 -> root(현재(node)순으로 진행된다.
과정
- 가장 최상위 node의 자식 node 중 왼쪽부터 시작
- 왼쪽 node 시작
- 3번 node의 자식 node 중 왼쪽 node인 1번 출력
- 3번 node의 자식 node 중 오른쪽 node인 2번 출력
- node 1번과 2번의 root인 3번 출력
- 왼쪽 node 끝
- 오른쪽 node 시작
- 6번 node의 자식 node 중 왼쪽 node인 4번 출력
- 6번 node의 자식 node 중 오른쪽 node인 5번 출력
- node 4번과 5번의 root인 6번 출력
- 오른쪽 node 끝
- 가장 최상위 node 7번 출력
- 순회 완료
코드
function postOrderIterate() {
let s1 = [], s2 = [];
s1.push(this.root);
// 첫번째 스택 비울때까지 계속 실행
while(s1.length){
const node = s1.pop();
s2.push(node);
// 제거된 항목의 왼쪽과 오른쪽 자식노드를 s1에 추가
if (node.left)
s1.push(node.left);
if (node.right)
s1.push(node.right);
}
// 두번째 스택의 모든 항목 출력
while(s2.length){
const node = s2.pop();
}
}
이진 tree 순회 선택 기준
- 자식 node가 없는 node에 접근하기 전에 root를 먼저 접근해야 하는 경우 선순위 순회를 선택하면 된다.
- 부모 node를 선택하기 전에 자식 node가 없는 node를 먼저 접근해야 하는 경우 후순위 순회를 선택하면 된다. 후순위 순회를 선택하면 root를 접근하는 시간 낭비를 하지 않기 때문이다.
- tree의 node 자체에 순서가 있어서 tree를 원래 순서대로 순회하고 싶을 때는 중순위 순회를 선택하면 된다.
Author And Source
이 문제에 관하여([TIL 23][Data Structure] Tree - 1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@devpark_0x1c/TIL-23Data-Structure-Tree-1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)