본문 바로가기

tree

 (3)
[JavaScript] Tree(트리) - Depth-first Search(깊이 우선 탐색), Breadth-first Search(너비 우선 탐색) 이진 트리의 탐색에는 크게 2가지 방법이 있다. 이번 포스팅에서는 깊이 우선 탐색(Depth-first Search)과 너비 우선 탐색(Breadth-first Search) 이 두 가지에 대하여 알아보고 각 순회들을 코드로 구현해 보려고 한다. Depth-first Search(깊이 우선 탐색) 1. Pre-Order Traversal(전위 순회) root -> left -> right 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 A, B, D, H, I, E, J, K, C, F, L, M, G, N, O 순으로 탐색 2. In-Order Traversal(중위 순회) left -> root -> right 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 H, D, I, B, J, ..
[JavaScript] Tree(트리) - Binary Search Tree(이진 탐색 트리) 지난 포스팅에서 트리 구조의 이론적인 부분을 학습하였다. 이제 그 이론을 바탕으로 이진 트리를 Javacript언어로 구현하려고 한다. 이진 트리를 구현하는 방법론 이진 트리를 구현하는 방법은 두 가지가 있다. 1. Array(배열)를 이용하는 방법 노드에 번호를 부여하고 그 번호에 해당하는 값을 인덱스 번호로 활용한다. 따라서 배열을 첫 번째 요소인 인덱스 0 직관화를 위해 비워둔다. 2. Linked List(연결 리스트)를 이용하는 방법 Linked List(연결 리스트)기반으로 왼쪽 링크와 오른쪽 링크에 자식 노드를 연결하는 방법이다. 연결 리스트 구조 자체가 트리 구조와 일치 하기 때문에 굉장히 직관적인 이해가 가능하다. 이 방법으로 트리 구조를 구현하는 것은 굉장히 좋은 구현이라고 할 수 있다..
[JavaScript] Tree(트리) - 이론학습 트리의 정의 계층적 관계를 표현하는 자료구조를 트리라고 한다. 회사내의 조직도, 의사결정을 하는데 필요한 알고리즘 등을 트리 형태로 나타내고 있다. 트리의 용어 정리 - 노드(node) : 트리를 구성하는 각 요소 A, B, C, D, E, F - 간선(edge) : 노드와 노드를 연결하는 선 - 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 노드 A - 단말 노드(terminal node) or leaf : 트리 구조에서 아래로 또 다른 노드(자식 노드)가 존재하지 않는 노드 C, D, E, F - 내부 노드(internal node) : 단말 노드를 제외한 모든 노드 A, B - A는 B, C, D의 부모 노드(parent node)이다. - B, C, D는 A의 자식 노드(chi..

티스토리툴바