프로그래머스 자료구조 강의와 각종 인터넷 자료를 참고하여 재구성한 내용입니다.

트리 (Trees)

  • 비선형적 자료 구조 (배열, linked lists, stacks, queues는 선형적 구조)
  • 트리는 root와 leaf로 이루어진다
  • 더 이상 가지를 칠 수 없는 node를 leaf라고 한다
  • 둘 다 아닌 노드를 internal node라고 한다
  • 트리는 비어있거나 root 원소 하나일 수도 있음
  • 노드가 거쳐야 하는 간선의 수를 Level이라고 한다.
  • 트리의 높이 (Height) = level + 1
  • 노드의 차수 (Degree) = 자식의 수 (leaf node는 degree가 0)

tree

이진 트리 (Binary Tree)

  • 모든 노드의 차수가 2 이하인 트리

포화 이진 트리 (Full Binary Tree)

  • 모든 레벨에서 노드들이 모두 채워져있는 이진 트리

완전 이진 트리 (Complete Binary Tree)

  • 마지막 레벨을 제외하고는 모든 노드가 자식 노드를 2개 가진 이진 트리
  • 높이가 k일때 레벨 k-2까지는 모든 노드가 2개의 자식을 가지고 레벨 k-1부터는 왼쪽부터 노드가 순차적으로 채워짐

trees

이진 트리의 구현

노드

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

트리

class BinaryTree:
	def __init__(self, r):
    	self.root = r

size

class Node: 
    def size(self):
        l = self.left.size if self.left else 0
        r = self.right.size if self.right else 0
        return l + r + 1

class BinaryTree:
	def size(self):
    	if self.root:
        	return self.root.size()
        else:
        	return 0

depth

class Node:
	def depth(self):
    	l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return l+1 if l>r else r+1
        
class BinaryTree:
	def depth(self):
    	if self.root:
        	return self.root.depth()
        else:
        	return 0

이진 트리의 순회 (Traversal)

깊이 우선 순회

  1. in-order (중위 순회): 왼쪽 자식노드(L), 내 노드(P), 오른쪽 자식노드(R) 순서로 방문한다.
  2. pre-order (전위 순회): 내 노드(P), 왼쪽 자식노드(L), 오른쪽 자식노드(R) 순서로 방문한다.
  3. post-order (후위 순회): 왼쪽 자식노드(L), 오른쪽 자식노드(R), 내 노드(P) 순서로 방문한다.

넓이 우선 순회

  • level이 낮은 노드를 우선 방문
  • 같은 수준의 노드들 사이에서는
    • 부모 노드의 방문 순서에 따라 방문
    • 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문

참조