트리, 이진 트리

트리란?

트리라는 용어는 아서 케일리의 논문에서 처음으로 사용

“A theorem on trees”. 《The Quarterly Journal of Pure and Applied Mathematics》

스택과 큐, 데크 등의 선형 자료구조로는 표현할 수 없는 자료를 표현하기 위해 만들어진 것

그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조

즉, 부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조를 말한다.

💡 부모노드 : 루트 노드 방향으로 직접 연결된 노드

    자식노드 : 루트 노드 반대방향으로 직접 연결된 노드

    루트노드 : 트리에서 부모가 없는 최상위 노드, 트리의 시작점

트리의 종류

• 이진트리
  • 이진트리
  • 이진탐색트리
  • 완전이진트리
  • 포화 이진 트리
• B-트리
  • 2-3-4 트리
  • B+ 트리

트리의 사용 예

• 유닉스/윈도우의 디렉토리
• 허프만 코드 등

 

 

이진트리란?

부모 노드 밑의 자식 노드 개수(=차수, degree)를 최대 2개로 제한하는, 트리의 가장 간단한 형태

이진트리의 순회 방법

전위 순회 : 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문

 

preorder(node)
  print node.value
  if node.left ≠ null then preorder(node.left)
  if node.right ≠ null then preorder(node.right)

중위 순회 : 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문

이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다.

 

 

inorder(node)
  if node.left  ≠ null then inorder(node.left)
  print node.value
  if node.right ≠ null then inorder(node.right)

후위 순회 : 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문

 

postorder(node)
  if node.left  ≠ null then postorder(node.left)
  if node.right ≠ null then postorder(node.right)
  print node.value

레벨 순서 순회 : 노드를 레벨 순서로 방문

= 너비 우선 순회

위의 세 가지 방법은 스택을 활용하여 구현할 수 있는 반면 레벨 순서 순회는 큐를 활용해 구현할 수 있다.

levelorder(root)
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    visit(node)
    if node.left ≠ null
      q.enqueue(node.left)
    if node.right ≠ null
      q.enqueue(node.right)

각각 순회들은 서로 다른 동작을 정의하는 서로 다른 기능 → 각각의 장단점이 아닌 활용이 다르다

ex) 후위순회는 폴더 용량을 계산할때 사용