트리 순회
-
[ 비선형 자료구조 ] 트리 순회Computer Science/자료 구조 2023. 1. 19. 17:36
1. pre-order traversal (전위 순회) [root - 왼쪽 자식 노드 - 오른쪽 자식 노드] 순으로 순회하는 방식이다. 이 방식에 따르면 A-B-D-E-C-F-G 순으로 트리를 순회하며, 자바스크립트로 구현한 코드는 아래와 같다. fucntion preOrder(root) { if (!root) return; console.log(root.data); preOrder(root.left); preOrder(root.right); } 2. in-order traversal (중위 순회) [왼쪽 자식 노드 - root - 오른쪽 자식 노드] 순으로 순회하는 방식이다. 이 방식에 따르면 D-B-E-A-F-C-G 순으로 트리를 순회하며, 자바스크립트로 구현한 코드는 아래와 같다. fucntion ..
-
[ 비선형 자료구조 ] 트리Computer Science/자료 구조 2023. 1. 18. 07:23
트리 1. 개념 트리는 그래프의 한 종류로서 각 노드가 특정 값을 저장하고 하나 이상의 자식 노드에 대한 참조값을 가지고 있는 자료구조이다. 트리를 구성하는 노드들은 계층구조로 이루어져있으며 최상위 노드를 root라 한다. 트리는 일반적으로 파일 시스템, 데이터 베이스, 의사결정 알고리즘 등에서 사용된다. 2. 용어 root : 부모 노드가 존재하지 않는 노드, 최상위 노드 (A) node : 데이터와 다음 노드에 대한 주소값을 저장한 자료구조 leaf : 자식노드가 존재하지 않는 노드, 최하위 노드 (H, I, E, J, K, L) parent : 하나 이상의 자식 노드를 가진 노드 (A, B, C, D, F, G) child : 다른 노드의 자손인 노드 (B, C, D, E, F, G, H, I, J..