- 트리는 가계도와 같은 계층적인 구조를 표현할때 사용하는 자료구조이다.
[트리 관련 용어]
- 루트 노드[root node]: 부모가 없는 최상위 노드
- 단말 노드[leaf node]: 자식이 없는 노드
- 크기(size): 트리에 포함된 모든 노드의 개수
- 깊이(depth): 루트 노드부터의 거리
- 높이(height): 깊이 중 최댓값
- 차수(degree): 각 노드의 (자식방향) 간선 개수
이진 탐색 트리(Binary Search Tree)
-
이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종이다.
-
이진 탐색 트리의 특징: 왼쪽 자식노드 < 부모 노드 < 오른쪽 자식노드
사진 예시)
-
트리의 순회(Tree Traversal)
트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법.
1) 전위 순회(pre-order travesrse):루트를 먼저 방문
2) 중위 순회(in-order traverse): 왼쪽 자식을 방문한 뒤에 루트 방문
3) 후위 순회(post-order traverse): 오른쪽 자식을 방문한 뒤에 루트를 방문.
아래 예시를 코드로 작성한다면
먼저 트리를 하기 위해 class Node 선언을한다.
그 뒤 init 메서드로 멤버(data, left_node, right_node)
변수들을 정의 한다.
n은 노드의 개수 이고 노드의 정보를 담기 위한 tree 딕셔너리를 초기화한다. for 문을 통해 n개의 노드에 대한 노드별 정보를 tree 에 초기화
각 pre_order, in_order, post_order [A] 값을 출력 하려할때
전위 순회, 중위 순회, 후위 순회는 다음와 같다.
먼저 전위순회 는 루트->왼쪽->오른쪽 방문 순서이다.
따라서 먼저 데이터 값을 먼저 처리한다(A 입력)
왼쪽 노드가 None 값이 아니기 때문에 if문 실행
A 의 left_node 인 pre_oder(tree[B]) 를 실행
B를 입력(현재 A-B) 이렇게 계속 반복하면 모든 노드를 방문하게된다.
다음은 중위 순회 이다.
중위 순회는 왼쪽 자식 노드를 방문 후에 루트를 방문하는 순회이다.
왼쪽노드가 None값이 아니라면, in_order(트리[왼쪽노드]) 를 실행
위 예시에서 가장 왼쪽 노드인 D가 출력, 그다음 부모노드인B 출력
(현재 D-B) 왼쪽 노드와 left_node 가 출력 됐으니 다음은 A의 left_node에서의 right_node 인 E 출력 (D-B-E) 계속 방문 하게되면 모든 노드를 위 의 예시와 같이 방문하게 될 것 이다.
후위 순회
후위 순회는 왼쪽자식노드, 오른쪽 자식노드 , 루트노드 순으로 방문하는 순회이다.
코드를 보면 left_node 의 값이 None 이 아니면 post_order의 왼쪽노드로 실행 하고 오른쪽도 마찬가지로 실행한 뒤에 본인의 데이터 값을 처리하는 것을 알수있다.
이렇게 코드를 작성하면 하고 위의 예시의 입력 값 을 입력하면
아래와 같이 출력 된다는 것 을 알수있다.
