[개발지식] 트리
1. 트리
계층적으로 데이터를 표현하기 위해 사용하는 자료구조
- 루트노드(parent node) : 부모가 없는 최상위 노드
- 단말노드(leaf node) : 자식이 없는 노드
- 크기(size) : 노드개수
- 루트노드로부터의 특정 노드까지의 거리(depth) : 깊이
- 깊이 중 최대값(height) : 높이
※ 트리크기가 N일때 간선개수는 N-1이다.
2. 이진탐색트리
Binary search tree, 이진탐색이 효과적으로 동작할 수 있도록 고안된 트리구조이다.
위와 같이 왼쪽자식<부모<오른쪽자식의 관계로 이루어져 있다.
3. 이진탐색트리에서의 데이터 조회
찾고자 하는 원소와 노드 원소를 서로 비교해가면서 순차적으로 탐색한다.
위 트리에서 37을 찾는다고 할때
- 루트노드에서 부터 방문하여 탐색진행, 최초 30보다 더 크므로 오른쪽 노드 방문
- 오른쪽 노드인 48과 비교하여, 왼쪽노드로 탐색 진행(더 작으므로)
- 37원소 탐색완료
4. 트리순회(Tree traversal)
- 전위순회 : 루트를 먼저 방문하고, 그 후 왼쪽 오른쪽 노드 순으로 방문한다.
- 중위순회 : 왼쪽자식을 먼저 방문하고, 루트 오른쪽 노드 순으로 방문한다.
- 후위순회 : 왼쪽자식을 먼저 방문하고, 오른쪽 루트 순으로 방문한다.
5. 알고리즘 구현
유의사항
- class 구축하기
- print 순서에 유의하기
#트리순회
#class
#print 순서에 유의
class Node:
def __init__(self, data, left_node, right_node):
self.data = data
self.left_node = left_node
self.right_node = right_node
#전위 순회(root>left>right)
def pre_order(node):
print(node.data, end=' ')
if node.left_node != None:
pre_order(tree[node.left_node])
if node.right_node != None:
pre_order(tree[node.right_node])
#중위 순회(left>root>right)
def in_order(node):
if node.left_node != None:
in_order(tree[node.left_node])
print(node.data, end=' ')
if node.right_node != None:
in_order(tree[node.right_node])
#후위 순회(left>right>root)
def post_order(node):
if node.left_node != None:
post_order(tree[node.left_node])
if node.right_node != None:
post_order(tree[node.right_node])
print(node.data, end=' ')
import sys
n = int(input())
tree = {}
for i in range(n):
#node 개수 n개
data, left_node, right_node = map(str, sys.stdin.readline().split())
if left_node == "None":
left_node = None
if right_node == "None":
right_node = None
tree[data] = Node(data, left_node, right_node)
#결과출력
pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])
6. 참조자료
이코테 2021 - 이진트리/이진탐색
https://www.youtube.com/watch?v=i5yHkP1jQmo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=12
Author And Source
이 문제에 관하여([개발지식] 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gyrbs22/개발지식-트리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)