경고: 로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다. 로그인하거나 계정을 생성하면 편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.
편집을 취소할 수 있습니다.
이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
| 최신판 |
당신의 편집 |
| 39번째 줄: |
39번째 줄: |
| ;Tree Traversal | | ;Tree Traversal |
| 트리를 조회하는 방식 | | 트리를 조회하는 방식 |
| | | * 전위(Preorder) |
| ====== 전위 순회(Preorder) ======
| | * 중위(Inorder) |
| * 깊이 우선 순회(DFT, Depth-First Traversal) 라고도 하며, 주로 트리를 복사하거나 전위표기법을 구하는데 사용한다.[https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C#%EC%A0%84%EC%9C%84_%EC%88%9C%ED%9A%8C_2]
| | * 후위(Postorder) |
| * 복사할 때 사용하는 이유는 트리의 노드부터 복사해야하기 때문이다.
| |
| * 다음과 같은 방법으로 진행한다.
| |
| *# 노드를 방문한다.
| |
| *# 왼쪽 서브 트리를 전위 순회한다.
| |
| *# 오른쪽 서브 트리를 전위 순회한다. | |
| | |
| ====== 중위 순회(Inorder) ======
| |
| * 대칭 순회(symmetric) 라고도 하며, 이진 탐색 트리(BST, Binary Search Tree) 에서 값을 가져올 때 주로 사용한다.
| |
| * 다음과 같은 방법으로 진행한다.
| |
| *# 왼쪽 서브 트리를 중위 순회한다.
| |
| *# 노드를 방문한다.
| |
| *# 오른쪽 서브 트리를 중위 순회한다. | |
| | |
| ====== 후위 순회(Postorder) ======
| |
| * 값을 삭제할 때 주로 사용한다. 그 이유는 루트 노드를 지우기 전에 하위 노드를 먼저 지워야하기 때문이다.
| |
| * 다음과 같은 방법으로 진행한다.
| |
| *# 왼쪽 서브 트리를 후위 순회한다.
| |
| *# 오른쪽 서브 트리를 후위 순회한다.
| |
| *# 노드를 방문한다.
| |
| | |
| ====== 레벨 순서 순회(level-order) ======
| |
| * 너비 우선 순회(breadth-first traversal) 라고도 한다.
| |
| * 모든 노드를 낮은 레벨부터 차례대로 순회한다.
| |
|
| |
|
| == [[이진 트리]] == | | == [[이진 트리]] == |
| ;Binary Tree | | ;Binary Tree |
