Tree - 트리

기본적인 트리 자료구조다.

트리는 비선형 자료구조다. 즉, 계층 구조를 이루는 형태

Node: 트리에 데이터를 저장하는 기본 요소

Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄.

Leaf Node(Terminal Node): Child Node가 하나도 없는 노드

Sibling(Brother Node): 동일한 Parent Node를 가진 노드

Depth: Node가 가질 수 있는 최대 Level

 

 

이진 트리와 이진 탐색 트리(Binary Search Tree)

-이진 트리: 노드의 최대 Branch가 2인 트리

-이진 탐색 트리: 왼쪽 노드는 해당 노드보다 작은값, 오른쪽은 큰 값

https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node

이진 트리에도 종류가 있다

-포화 이진 트리

모든 레벨의 노드들이 꽉 차 있는 모습의 이진 트리

노드의 개수는 레벨이 h일때 (2^h+1 -1)

-완전 이진 트리

오른쪽 노드들 일부가 연속으로 비어 있는 형태

트리의 높이가 h, 노드가 n개 라면 (n+1)부터 (2^h+1 -1 ) 번의 노드가 비어 있는 형태

-편향 이진 트리

왼쪽은 왼쪽편향, 오른쪽은 오른쪽 편향 이진 트리라고한다.

일반 트리에서 이진트리로 변환하기

이것을 이진트리로 변환해보자

파이썬에서 트리구조 만들기

class Node:
  def __init__(self,data):
      self.left=None
      self.right=None
      self.data=data

      
root =Node(10)
root.left=Node(34)
root.right=Node(89)
root.left.left=Node(45)
root.left.right=Node(50)
    10
    / \
  34   89
 /  \
45  50
      
def preorder(node):
  if node:
    print(node.data)
    preorder(node.left)
    preorder(node.right)
결과는 10 34 45 50 89
    
def inorder(node):
  if node:
    inorder(node.left)
    print(node.data)
    inorder(node.right)
   
결과는 45 34 50 10 89
    
def postorder(node):
  if node:
    postorder(node.left)
    postorder(node.right)
    print(node.data)
    
결과는 45 50 34 89 10

 

 

트리의 운행법

전위 순회법: 자기자신출력 -> 왼쪽 서브트리 -> 오른쪽 서브트리

중위 순회법: 왼쪽 서브트리 -> 자기자신 출력 -> 오른쪽 서브트리

후위 순회법: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 자기자신 출력

 

 

[참고]

https://www.delftstack.com/ko/howto/python/trees-in-python/

Python에서 트리 데이터 구조 구현

https://www.fun-coding.org/Chapter10-tree.html

파이썬과 컴퓨터 사이언스(자료구조): 대표적인 자료구조: 트리 - 잔재미코딩